[数据结构与算法]08 队列( Queue )以及队列实现的三种方式( Java 版)

- 日理万妓 2023-06-28 11:29 13阅读 0赞

# 队列 #

说队列的时候,常常会想到栈,因为栈是后进先出,而队列则是先进先出.  
关于栈,前面已经写过了:[\[数据结构与算法\]05 Stack 经典面试题之判断字符串是否合法( Java 版)][05 Stack _ Java]  
这篇文章的主要焦点就在队列上了.

队列,你的第一反应是不是排队?不管是在食堂买饭,还是在银行办理业务,或者进高铁站的时候,都会排队.  
排队有一个很明显的特点:早来的人,就会早点儿办完事情.  
这就是队列:先进先出.

队列可以用数组实现,叫做顺序队列.也可以用链表实现,叫做链式队列.  
在这里,分别用数组和链表来实现一下.

# 数组实现队列 #

使用数组来实现队列,相对来说还是比较简单的,因为数组和队列一样都是线性表结构.  
废话不多说,咱们直接看代码

/** * 用数组实现队列 * @author 郑璐璐 * @date 2020-1-29 15:51:32 */
    public class ArrayQueue { 
        /** 数组：items，数组大小：n */
        private String[] items;
        private int n = 0;
        /** head表示队头下标，tail表示队尾下标 */
        private int head = 0;
        private int tail = 0;
    
        /** 申请一个大小为capacity的数组 */
        public ArrayQueue(int capacity) { 
            items = new String[capacity];
            n = capacity;
        }
    
        /** 入队 */
        public boolean enqueue(String item) { 
            // 如果tail == n 表示队列已经满了
            if (tail == n) return false;
            items[tail] = item;
            tail++;
            return true;
        }
    
        /** 出队 */
        public String dequeue() { 
            // 如果head == tail 表示队列为空
            if (head == tail) return null;
            String ret = items[head];
            head++;
            return ret;
        }
    
        public void printAll() { 
            for (int i = head; i < tail; i++) { 
                System.out.print(items[i] + " ");
            }
            System.out.println();
        }
    
        public static void main(String[] args) { 
            ArrayQueue queue=new ArrayQueue(5);
            queue.enqueue("1");
            queue.enqueue("2");
            queue.enqueue("3");
            queue.enqueue("4");
            queue.enqueue("5");
            queue.dequeue();
            queue.enqueue("6");
    
            queue.printAll();
        }
    }

使用数组实现队列有个问题,就是删除不是真的删除,只是在打印的时候将 i 的值指向了 head 而已,但是要删除的数据,仍然在数组中.

# 链表实现队列 #

使用链表实现队列也较为简单:

/** * 用链表实现队列 * @author 郑璐璐 * @date 2020-1-30 09:20:41 */
    public class LinkListQueue { 
        /** 队列的队首和队尾 */
        private Node head = null;
        private Node tail = null;
    
        /** 入队 */
        public void enqueue(String value) { 
            if (tail == null) { 
                Node newNode = new Node(value, null);
                head = newNode;
                tail = newNode;
            } else { 
                tail.next = new Node(value, null);
                tail = tail.next;
            }
        }
    
        /** 出队 */
        public String dequeue() { 
            if (head == null) return null;
    
            String value = head.data;
            head = head.next;
            if (head == null) { 
                tail = null;
            }
            return value;
        }
    
        public void printAll() { 
            Node p = head;
            while (p != null) { 
                System.out.print(p.data + " ");
                p = p.next;
            }
            System.out.println();
        }
    
        private static class Node { 
            private String data;
            private Node next;
    
            public Node(String data, Node next) { 
                this.data = data;
                this.next = next;
            }
    
            public String getData() { 
                return data;
            }
        }
    
        public static void main(String[] args) { 
            LinkListQueue queue=new LinkListQueue();
            queue.enqueue("3");
            queue.enqueue("2");
            queue.dequeue();
            queue.printAll();
        }
    }

# 栈实现队列 #

除了使用数组和链表实现,还有一种方法就是使用栈来实现队列.  
使用栈来实现队列,顾名思义就是只能使用栈的操作: pop , push , peek 等,其他操作不允许出现,否则就不是使用栈来实现队列了.  
使用数组和链表来实现栈都较为简单,因为在读取数据时,只需要按照顺序读取即可.  
但是对于栈来说,顺序读取行不通,为什么呢?假设我的队列数据为 1,2,3,4 依次存入栈中之后再读取的话,则是 4,3,2,1 因为栈是后进先出.  
如果使用栈来实现队列的话,需要用到两个栈.一个栈的输出顺序就是 4,3,2,1 在读取之前,我们把读取出来的数据存入到另外一个栈中,然后从后面这个栈读取,那么输出顺序就是 1,2,3,4 和原来队列的数据一致.  
在这里要注意一点:当后面的栈中有数据,前面的栈中也有数据时,要先将后面的栈中数据读取完毕,再将前面的数据放到后面的数据中.  
接下来看下代码实现:

/** * 使用栈实现队列 * @author 郑璐璐 * @date 2020-1-30 17:21:19 */
    public class StackQueue { 
        private  static Stack<Integer> stackTemp = new Stack<Integer>();
        private static Stack<Integer> stackQueue = new Stack<Integer>();
    
        /** 入队 */
        public void push(int x){ 
            stackTemp.push(x);
        }
    
        /** 出队 */
        public int pop(){ 
            // 整个队列不为空时
            if (empty()!=0){ 
                // 如果 stackQueue 为空时,则将 stackTemp 中的数据放入 stackQueue 中
                // 如果 stackQueue 不为空,直接输出即可
                if (stackQueue.isEmpty()){ 
                    backFill();
                }
                return stackQueue.pop();
            }else { 
                // 整个队列为空,则返回 -1 ,代表队列中没有值
                System.out.println("队列为空");
                return -1;
            }
        }
        public int empty(){ 
            // 判断队列是否为空,如果返回值为 0 ,则代表队列为空
            // 注意,两个栈均为空时,队列才为空
            return stackQueue.size() + stackTemp.size();
        }
        /** 将 stackTemp 中的数据放入 stackQueue 中 */
        public void backFill(){ 
            while (!stackTemp.isEmpty()){ 
                stackQueue.push(stackTemp.pop());
            }
        }
        public static void main(String[] args){ 
            StackQueue stack = new StackQueue();
            stack.push(1);
            stack.push(2);
            stack.push(3);
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            stack.push(4);
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
        }
    }

以上,就是想要分享的内容了  
感谢您的阅读哇~

[05 Stack _ Java]: https://blog.csdn.net/zll_0405/article/details/103233482