【java数据结构与算法学习】队列

女爷i 2022-05-30 05:16 255阅读 0赞

队列是一种先进先出的数据结构，和栈一样，是以线性表为基础的。队列可以用顺序存储结构或者是链式存储结构来实现，一般来说，我们都是用链式存储结构来实现的。

下面就是链式存储结构队列的基本实现。

public class MyQueue {
        private class Node{
            public Integer data;
            public Node next;
    
            public Node(Integer data, Node next) {
                this.data = data;
                this.next = next;
            }
        }
        private Node fear;
        private Node rear;
        private Node p;
    
        public MyQueue(){
            p = new Node(null, null);
            fear = rear = p;
        }
    
        public void insert(Integer e){
            p = new Node(e,null);
            rear.next = p;
            rear = p;
        }
    
        public Node delete(){
            //空队列
            if (fear.next == null){
                return null;
            }
            //记录将要删除的元素
            p = fear.next;
            //队列中只有一个元素的时候，删除只需要将rear移动到fear的位置就行了
            if (fear.next.next == null){
                rear = fear;
                fear.next = null;
                return p;
            }
            //队列中有多个元素
            fear.next = fear.next.next;
            p.next = null;
            return p;
        }
    
        public static void main(String[] args) {
            MyQueue myQueue = new MyQueue();
            for (int i = 0; i < 10; i++) {
                myQueue.insert(i);
            }
            for (int i = 0; i < 10; i++) {
                Node del = myQueue.delete();
                System.out.println(del.data);
            }
        }
    }

那么我们如何实现顺序存储结构的队列呢？

实际上，我们实现顺序存储结构的队列的时候使用循环数组实现的，TODO