数据结构--队列实现（顺序循环队列、链式队列）

雨点打透心脏的1/2处 2021-08-13 11:32 673阅读 0赞

### 队列 ###

队列（queue）是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。

![在这里插入图片描述][20200117113402259.png]

### 队列的抽象数据类型 ###

package pers.zhang.queue;
    
    /** * @author zhang * @date 2020/1/17 - 11:35 * * 队列的接口 */
    public interface QQueue<T> { 
    
        //判断队列是否为空
        boolean isEmpty();
    
        //元素x入队
        void enqueue(T x);
    
        //出队，返回队头元素
        T dequeue();
    }

### 队列的实现 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70]

### 顺序队列 ###

存在假溢出问题！不建议使用  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 1]

### 顺序循环队列 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 2]  
使用模拟循环的方式避免假溢出：  
![在这里插入图片描述][20200117114456629.png]  
实现：

package pers.zhang.queue;
    
    /** * @author zhang * @date 2020/1/17 - 11:45 * * 顺序循环队列 */
    public class SeqQueue<T> implements QQueue<T> { 
    
        //存储队列数据的Object数组
        private Object element[];
    
        //队头和队尾引用
        private int front, rear;
    
        //构造
        public SeqQueue(int length){ 
            if(length < 64)
                length = 64;
            this.element = new Object[Math.abs(length)];//设置队列容量最小值
            this.front = this.rear = 0;//构造空队列
        }
    
        //默认构造
        public SeqQueue(){ 
            this(64);
        }
    
        //判断队列是否为空
        @Override
        public boolean isEmpty() { 
            return this.front == this.rear;
        }
    
        //元素x入队，空对象不能入队
        @Override
        public void enqueue(T x) { 
            if(x == null)
                return;
            if(this.front == (this.rear + 1) % this.element.length){ //队满，扩容
                Object[] temp = this.element;
                this.element = new Object[temp.length * 2];//重新申请一个数组
                int j = 0;
                for(int i = this.front; i != this.rear; i = (i + 1) % temp.length)
                    this.element[j++] = temp[i];
            }
            this.element[this.rear] = x;//插入数据
            this.rear = (this.rear + 1) % this.element.length;//移动队尾
        }
    
        //出队，返回队头元素
        @Override
        public T dequeue() { 
            if(isEmpty())//空队列返回null
                return null;
            T temp = (T) this.element[this.front];
            this.front = (this.front + 1) % this.element.length;
            return temp;
        }
    
        @Override
        public String toString(){                      //返回队列所有元素的描述字符串，形式为“(,)”，按照队列元素次序
            String str = "(";
            if (!isEmpty()){ 
                str += this.element[this.front].toString();
                int i = (this.front+1) % this.element.length;
                while(i != this.rear){ 
                    str += ", "+this.element[i].toString();
                    i = (i + 1) % this.element.length;
                }
            }
            return str + ")";
        }
    }

### 链式队列 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 3]

package pers.zhang.queue;
    
    import pers.zhang.linearList.Node;
    
    /** * @author zhang * @date 2020/1/17 - 12:48 * * 链式队列 */
    public class LinkedQueue<T> implements QQueue<T> { 
    
        //头节点和尾节点引用
        private Node<T> front, rear;
    
        //构造空队列
        public LinkedQueue(){ 
            this.front = this.rear = null;
        }
    
        //判断队列是否为空
        @Override
        public boolean isEmpty() { 
            return this.front == null && this.rear == null;
        }
    
        //元素x入队，空对象不操作
        @Override
        public void enqueue(T x) { 
            if(x == null)
                return;
            Node<T> q = new Node<T>(x, null);
            if(this.front == null)
                this.front = q;//空队插入
            else
                this.rear.next = q;//插入队尾
            this.rear = q;
        }
    
        //出队，返回队头元素
        @Override
        public T dequeue() { 
            if(isEmpty())
                return null;
            T temp = this.front.data;
            this.front = this.front.next;//删除队头节点
            if(this.front == null)
                this.rear = null;
            return temp;
        }
    
        //返回队列所有元素的描述字符串，形式为“(,)”
        @Override
        public String toString(){ //算法同不带头结点的单链表
            String str = "(";
            for (Node<T> p=this.front;  p!=null;  p=p.next){ 
                str += p.data.toString();
                if (p.next != null)
                    str += ", ";                               //不是最后一个结点时后加分隔符
            }
            return str + ")";                                    //空表返回()
        }
    }

### 测试 ###

package pers.zhang.queue;
    
    /** * @author zhang * @date 2020/1/17 - 12:55 */
    public class Queue_ex { 
        public static void main(String args[])
        { 
            SeqQueue<Integer> que = new SeqQueue<Integer>(5);
            que.enqueue(new Integer(10));
            que.enqueue(new Integer(20));
            System.out.println("dequeue : "+que.dequeue().toString()+" "+que.dequeue().toString()+" ");
            System.out.println(que.toString());
            que.enqueue(new Integer(30));
            que.enqueue(new Integer(40));
            que.enqueue(new Integer(50));
            que.enqueue(new Integer(60));
            System.out.println(que.toString());
            que.enqueue(new Integer(70));
            System.out.println(que.toString());
    
            LinkedQueue<Integer> q = new LinkedQueue<Integer>();
            System.out.print("enqueue: ");
            for (int i=1; i<=5; i++)
            { 
                Integer intobj = new Integer(i);
                q.enqueue(intobj);
                System.out.print(intobj+" ");
            }
            System.out.println("\n"+q.toString());
    
            System.out.print("dequeue : ");
            while (!q.isEmpty())
                System.out.print(q.dequeue().toString()+" ");
            System.out.println();
        }
    }
    /* dequeue : 10 20 () (30, 40, 50, 60) (30, 40, 50, 60, 70) enqueue: 1 2 3 4 5 (1, 2, 3, 4, 5) dequeue : 1 2 3 4 5 */

[20200117113402259.png]: /images/20210813/ba942fcb61d742c38b7f262937cf976e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70]: /images/20210813/600e8c3e81ec4895b155cc0fcd6b4fc8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 1]: /images/20210813/1f9989a2030142d195145ecca8b7c8d5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 2]: /images/20210813/14b5e94b6b5c47d99e3d16275d7b6c88.png
[20200117114456629.png]: /images/20210813/3d8f9cfab4ff49d4b97bbb03de7ec558.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 3]: /images/20210813/e54fd37dc966427c8e0ce162e30e1f59.png