【数据结构与算法】-- 5. 如何实现一个队列（顺序队列和链式队列）

队列跟栈一样， 也是一种操作受限的线性表数据结构。
它具有先进先出的特性， 支持在队尾插入元素， 在队头删除元素， 那究竟该如何实现一个队列呢？
跟栈一样， 队列可以用数组来实现， 也可以用链表来实现。 用数组实现的栈叫作顺序栈， 用链表实
现的栈叫作链式栈。 同样， 用数组实现的队列叫作顺序队列， 用链表实现的队列叫作链式队列。

顺序队列

package com.anomalous.array;

/**
 * 基于数组实现的队列
 *
 * @author 天赋吉运-杨晓慧
 * @create 2019-04-27 15:27
 */
public class ArrayQueue {

    //定义数组，数组大小，两个指针（头和尾）
    private String items[];     // 队列
    private int n;          // 队列内元素数量
    private int head;       // 队列内头指针位置
    private int tail;       // 队列内尾指针位置

    /**
     * 构造一个基于数组实现的队列
     * @param n 容量
     */
    public ArrayQueue(int n){
        //定义长度为n的数组
        this.items=new String[n];

        this.n=n;
        // 数组中头指针和尾指针
        this.head=0;
        this.tail=0;
    }

    /**
     * 入队操作
     * @param item 入队元素
     * @return 是否入队成功
     */
    public boolean inqueue(String item){

        // 判断队列是否满了，如果队列已满不能再进行入队操作
        if (this.tail==n) {
           if (head==0) {
               // tail=n && head=0表示整个队列都已经满了，前后都没有空位置了
               return false;
            }
            // 只有tail=0表示队尾已经满了，但队首还有空位置
            // 需要数据搬移，将后面的数据往前移动，为队列腾出位置，然后新入队的数据才能放入队尾
            for (int i = head; i < tail; i++) {
                //从队首开始，依次往前移动head位
                 this.items[i-head]= this.items[i];
            }

            // 数据搬移完之后需要更新head和tail指针的位置
            // head指向0位，tail往前移动head个位置；
            head=0;
            tail-=head;
        }

        // 放在队列的最后一位
        this.items[tail]=item;
        // 头指针不变，尾指针的位置后移一位
        ++tail;
        return true;
    }

    /**
     * 出队操作
     * @return 出队元素
     */
    public String outqueue(){
        //判断对内是否有元素
        if (this.head==this.tail) {
            // 队首指针与队尾指针在同一位置表示队列为空
            return null;
        }
        // 取出队首元素放入临时变量
        String temp=items[head];

        // 从head指针部分出队，head后移一位
        ++head;
        return temp;
    }
}

链式队列

下面是链式的实现，也是实现了基本的入队和出队操作

/**
 * 基于链表实现的队列
 *
 * @author 天赋吉运-杨晓慧
 * @create 2019-04-30 9:39
 */
public class LInkedListQueue {

    //定义队列的队首和队尾（队首出队，队尾入队）
    private Node head;
    private Node tail;

    /**
     * 入队操作
     * @param value  待入队元素
     */
   public void inQueue(int value){
       // 判断队列是否为空
       if (this.tail==null) {
           // 队列为空时
           Node node =new Node(value,null);
           // 当前节点既是队首也是队尾
           this.head = node;
           this.tail = node;
       } else {
           // 队列不为空，新节点入队从队尾入
           this.tail.next=new Node(value,null);
           // 尾指针后移一位
           this.tail=this.tail.next;
       }
   }

    /**
     * 出队操作
     * @return 返回队首节点data
     */
   public Integer outQueue(){
       // 队列为空时
       if (head == null) return null;

       // 出队从队首出
       Integer value=this.head.data;
       // 队首指针后移一位
       this.head=this.head.next;
       if (this.head==null) {
           // 只有一个节点时候,出队后队列为空
           this.tail =null;
       }
       return value;

   }

    /**
     * 定义链表结构
     */
    private static class Node {
        private int data;
        private Node next;

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }

        public Integer getData() {
            return data;
        }
    }
}

最后

以上就是高挑音响为你收集整理的【数据结构与算法】-- 5. 如何实现一个队列（顺序队列和链式队列）的全部内容，希望文章能够帮你解决【数据结构与算法】-- 5. 如何实现一个队列（顺序队列和链式队列）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。