单向队列、双端队列、栈的模型实现

矫情吗；* 2022-10-22 04:30 123阅读 0赞

# 引言 #

自己实现简单的队列、栈的逻辑结构。

队列都包含头和尾两个指针，简单的单向队列只能在一端（如：head端）入列，在另一端（如：tail 端）出列；双端队列可以在 head 进出，也可以在 tail 进出。

栈的模型更加简单，它分为 top 和 bottom 两个指针，只能在 top 端进出。

经典的模型结构包含几个主要方法，进、出、isEmpty、size 等。

# 一、队列的实现 #

不论是单向队列还是双端队列，始终都是在操作 head 和 tail 两个指针。它们的实现没有什么本质区别，实际上，掌握了双端队列，单向队列就易如反掌。

在手动实现队列的时候，需要在脑海中模拟出队列的构造，左侧为 head ，右侧为 tail：

![20210404114112167.png][]

因此，队列中一定需要两个特殊的成员变量：head 和 tail。

其次，由于队列和栈都属于逻辑结构，因此，我们必须考虑使用哪种底层数据结构来实现，一般有两个最典型的结构可供使用：双向链表、数组。

## 1.1 双端队列的实现 ##

首先，我们需要敲定队列中的节点的数据结构，双向链表是个不错的选择，它不受空间的约束，这是相对于数组实现的一个明显的有点。

经典的**双向链表结构**：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70][]

private static class Node<T> {
            public T value;
            private Node<T> prev;
            private Node<T> next;
    
            public Node(T value) {
                this.value = value;
            }
    
            @Override
            public String toString() {
                return value.toString();
            }
        }

建议把Node设计为**私有静态内部类**，作为队列内部的存储对象 T 的容器，它不需要被外界感知。

双端队列需要四个进出方法：头进，头出，尾进，尾出。

以**头进为例**，当接收到一个入列对象时，我们需要先封装为 Node 类型的 cur ，然后判断队列是否为空，即是否 head == null，如果为空，那么当前元素即是 head 也是 tail：

if (head == null) {
        // 如果是第一个元素，则头尾都指向cur
        head = cur;
        tail = cur;
    }

如果不为空，那么，需要建立 cur 与 head 之间的链表关系，即 cur.next = head，head.prev = cur。然后head角色变为 cur，就完成了入列操作：

else {
        // 如果不是第一个元素
        // cur在前，head在后，建立链表关系
        cur.next = head;
        head.prev = cur;
        // head更新
        head = cur;
    }

再以**尾出为例**，返回值为泛型 T，首先同样是要判断队列是否为空（head == null?），如果空，则直接返回null。若存在元素，首先我们要拿到 tail 元素，将它保存下来。

然后关键要判断是否队列中仅存在一个元素，即 head == tail，如果只有一个元素，那么取出后需要将 head 和 tail 都变为 null：

if (head == tail) {
        head = null;
        tail = null;
    }

若不是最后一个，那么和入列相反，我们需要**斩断 Node 之间的引用关系**，刚刚我们已经将原来的 tail 并保存到了一个新的 Node 局部变量里，此时已经可以将其成功返回，但除此之外，还需要释放一些指针空间，并改变 tail 的指向：

else {
        // tail 前移
        tail = tail.prev;
        // 释放空间
        cur.prev = null;
        tail.next = null;
    }
    return cur.value;

剩下的方法逻辑大同小异，一定不要搞混 Node 节点的 prev 和 next，与 head 和 tail，明确并牢记这些概念的含义，以及链表**左头右尾**的方向，入列时要建立两个节点之间的对应关系，出列时要切断两个节点之间的关系。以下是**完整代码示例**：

/**
     * 使用链表实现的双端队列
     */
    public class MyDoubleEndsQueue<T> {
    
        private Node<T> head;
        private Node<T> tail;
        private int size = 0;
    
        private static class Node<T> {
            T value;
            Node<T> prev;
            Node<T> next;
    
            public Node(T value) {
                this.value = value;
            }
    
            @Override
            public String toString() {
                return value.toString();
            }
        }
    
        public void addFromHead(T value) {
            size++;
            Node<T> cur = new Node<T>(value);
            if (head == null) {
                // 如果是第一个元素，则头尾都指向cur
                head = cur;
                tail = cur;
            } else {
                // 如果不是第一个元素
                // cur在前，head在后，建立链接关系
                cur.next = head;
                head.prev = cur;
                // head更新
                head = cur;
            }
        }
    
        public void addFromTail(T value) {
            size++;
            Node<T> cur = new Node<>(value);
            if (tail == null) {
                head = cur;
                tail = cur;
            } else {
                tail.next = cur;
                cur.prev = tail;
                tail = cur;
            }
        }
    
        public T popFromHead() {
            if (head == null) return null;
            size--;
            Node<T> cur = head;
            if (head == tail) {
                // 只有一个元素
                head = null;
                tail = null;
            } else {
                head = head.next;
                cur.next = null;
                head.prev = null;
            }
            return cur.value;
        }
    
        public T popFromTail() {
            if (tail == null) return null;
            size--;
            Node<T> cur = tail;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                // tail 前移
                tail = tail.prev;
                // 释放空间
                cur.prev = null;
                tail.next = null;
            }
            return cur.value;
        }
    
        public boolean isEmpty() {
            return head == null;
        }
    
        public int size() {
            return size;
        }
    }

## 1.2 单向队列 ##

### 1.2.1 双向链表实现 ###

单向队列的实现可以建立在双端队列的基础之上，直接调用其方法，或使用相同的逻辑来完成实现，完整代码如下：

/**
     * 使用链表实现的单向队列
     */
    public class MyQueue<T> {
        private Node<T> head;
        private Node<T> tail;
        private int size = 0;
    
        private static class Node<T> {
            Node<T> prev;
            T value;
            Node<T> next;
    
            public Node(T value) {
                this.value = value;
            }
    
            @Override
            public String toString() {
                return value.toString();
            }
        }
    
        /**
         * 头进
         *
         * @param t
         */
        public void push(T t) {
            Node<T> cur = new Node<>(t);
            size++;
            if (isEmpty()) {
                head = cur;
                tail = cur;
            } else {
                head.prev = cur;
                cur.next = head;
                head = cur;
            }
        }
    
        /***
         * 尾出
         * @return
         */
        public T pop() {
            if (isEmpty()) return null;
            size--;
            Node<T> cur = tail;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                tail = tail.prev;
                cur.prev = null;
                tail.next = null;
            }
            return cur.value;
        }
    
        public boolean isEmpty() {
            return head == null;
        }
    
        public int size() {
            return size;
        }
    }

### 1.2.2 数组实现队列 ###

数组实现队列相对复杂一些，由于数组是定长结构，因此，需要在创建之初设定大小，且这一大小如果不涉及扩容，在使用过程中是不可变更的。

另一方面，由于数组的大小被限定，因此，必须循环使用数组空间，如果数组满了再添加元素，以及数组空了再取元素，这两种情况都需要报错。

为了不陷入头尾追赶的怪圈逻辑，在使用数组实现队列时，需要特别小心，不要去考虑收尾追击的问题，只需要通过 size 来控制，首尾自然不会出现“交叉”的情况。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70 1][]

/**
     * 环形数组队列
     */
    public class RingArrayQueue<T> {
        private T[] arr;
        private int pushIdx;
        private int popIdx;
        private int size;
        private final int limit;
    
        public RingArrayQueue(Class<T> type, int limit) {
            this.arr = (T[]) Array.newInstance(type, limit);
            this.pushIdx = 0;
            this.popIdx = 0;
            this.size = 0;
            this.limit = limit;
        }
    
        public void push(T t) {
            if (size == limit)
                throw new RuntimeException("队列满了，不能再加了");
            size++;
            arr[pushIdx] = t;
            pushIdx = nextIndex(pushIdx);
        }
    
        public T pop() {
            if (size == 0)
                throw new RuntimeException("队列空了！");
            size--;
            T t = (T) arr[popIdx];
            popIdx = nextIndex(popIdx);
            return t;
        }
    
        public boolean isEmpty() {
            return size == 0;
        }
    
        public int size() {
            return size;
        }
    
        // 如果现在的下标是i，返回下一个位置
        private int nextIndex(int i) {
            return i < limit - 1 ? i + 1 : 0;
        }
    }

# 二、栈的实现 #

有了双端队列的逻辑铺垫，栈的实现完全可以照搬，完整代码如下：

/**
     * 使用链表实现的栈
     */
    public class MyStack<T> {
        private Node<T> top;
        private Node<T> bottom;
        private int size = 0;
    
        private static class Node<T> {
            Node<T> prev;
            T value;
            Node<T> next;
            public Node(T value) {
                this.value = value;
            }
            @Override
            public String toString() {
                return value.toString();
            }
        }
    
        public void push(T t) {
            Node<T> cur = new Node<>(t);
            if (isEmpty()) {
                top = cur;
                bottom = cur;
            } else {
                top.next = cur;
                cur.prev = top;
                top = cur;
            }
        }
    
        public T pop() {
            if (isEmpty()) {
                return null;
            }
            size--;
            Node<T> cur = top;
            if (top == bottom) {
                top = null;
                bottom = null;
            } else {
                top = top.prev;
                top.next = null;
                cur.prev = null;
            }
            return cur.value;
        }
    
        public boolean isEmpty() {
            return top == null;
        }
    
        public int size() {
            return size;
        }
    }

# 三、测试 #

使用jdk自带的数据结构来对照测试自定义的队列和栈，完整代码如下：

import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    public class Checker {
        public static void main(String[] args) {
            int oneTestDataNum = 100;
            int value = 10000;
            int testTimes = 100000;
            for (int i = 0; i < testTimes; i++) {
                MyStack<Integer> myStack = new MyStack<>();
                MyQueue<Integer> myQueue = new MyQueue<>();
                // 对照组
                Stack<Integer> stack = new Stack<>();
                Queue<Integer> queue = new LinkedList<>();
                for (int j = 0; j < oneTestDataNum; j++) {
                    int nums = (int) (Math.random() * value);
                    if (stack.isEmpty()) {
                        myStack.push(nums);
                        stack.push(nums);
                    } else {
                        if (Math.random() < 0.5) {
                            myStack.push(nums);
                            stack.push(nums);
                        } else {
                            if (!isEqual(myStack.pop(), stack.pop())) {
                                System.out.println("oops!");
                            }
                        }
                    }
                    int numq = (int) (Math.random() * value);
                    if (stack.isEmpty()) {
                        myQueue.push(numq);
                        queue.offer(numq);
                    } else {
                        if (Math.random() < 0.5) {
                            myQueue.push(numq);
                            queue.offer(numq);
                        } else {
                            if (!isEqual(myQueue.pop(), queue.poll())) {
                                System.out.println("oops!");
                            }
                        }
                    }
                }
            }
            System.out.println("finish!");
        }
    
        public static boolean isEqual(Object o1, Object o2) {
            if (o1 == null) {
                return o1 == o2;
            }
            return o1.equals(o2);
        }
    }

# 四、实现一个查找最小值的时间复杂度是 O(1) 的栈 #

设计思路：使用一个单独的栈，用于存储数据栈的最小值，在每次push 的时候，判断是否为最小值，如果是，则如 minStack，如果不是，则继续压入上一次的最小值。完整代码如下：

import java.util.Stack;
    
    public class GetMinStack {
        public static class MyMinStack {
            private Stack<Integer> dataStack;
            private Stack<Integer> minStack;
    
            public MyMinStack() {
                this.dataStack = new Stack<>();
                this.minStack = new Stack<>();
            }
    
            public void push(Integer num) {
                if (minStack.isEmpty()) {
                    minStack.push(num);
                } else if (getMin() >= num) {
                    minStack.push(num);
                } else {
                    minStack.push(getMin());
                }
                dataStack.push(num);
            }
    
            public Integer pop() {
                if (dataStack.isEmpty()) {
                    return null;
                }
                minStack.pop();
                return dataStack.pop();
            }
    
            public Integer getMin() {
                if (minStack.isEmpty())
                    return null;
                return minStack.peek();
            }
        }
    
        public static void main(String[] args) {
            MyMinStack stack1 = new MyMinStack();
            stack1.push(3);
            System.out.println(stack1.getMin());
            stack1.push(4);
            System.out.println(stack1.getMin());
            stack1.push(1);
            System.out.println(stack1.getMin());
            System.out.println(stack1.pop());
            System.out.println(stack1.getMin());
        }
    
    }

# 五、只使用栈实现队列 #

只使用栈实现队列和只使用队列实现栈在面试中还比较常见，例如，用栈来实现一个图的**宽度优先**遍历，或用队列来实现图的**深度优先**遍历，但图的宽度优先遍历一定需要用队列来实现，而深度优先遍历也一定要用栈来实现，因此，我们可以通过**栈与队列的转化**来完成类似这样的面试题。

使用栈来实现队列的思路是，用两个栈，分别存储入栈的顺序，和出栈的顺序，因为栈的出栈顺序是入栈时的反向，因此，只要两个栈互倒就可以实现队列的结构。

互倒是一种思路，还有一种思路是，只从push 栈往 pop 栈倒，这样的方式可以减少一定的性能开销，但需要保证两个原则：1、如果决定要倒数据，必须一定倒完；2、只要pop为空时，才可以倒入。

以下是两种实现代码，第一个是互倒的方式，第二个是**单向倒入**的方式：

import java.util.Stack;
    
    /**
     * 使用两个栈来实现队列
     */
    public class TwoStackQueue<T> {
    
        private Stack<T> pushStack;
        private Stack<T> popStack;
    
        public TwoStackQueue() {
            this.pushStack = new Stack<>();
            this.popStack = new Stack<>();
        }
    
        private synchronized void reverseStack(Stack<T> from, Stack<T> to) {
            while (!from.isEmpty()) {
                to.push(from.pop());
            }
        }
    
        public void push(T t) {
            if (!popStack.isEmpty()) {
                reverseStack(popStack, pushStack);
            }
            pushStack.push(t);
        }
    
        public T pop() {
            if (!pushStack.isEmpty())
                reverseStack(pushStack, popStack);
            if (!popStack.isEmpty())
                return popStack.pop();
            else
                return null;
        }
    }

import java.util.Stack;
    
    /**
     * 单向倒入双栈队列
     */
    public class SingleDirTwoStackQueue<T> {
        private Stack<T> pushStack;
        private Stack<T> popStack;
    
        public SingleDirTwoStackQueue() {
            pushStack = new Stack<>();
            popStack = new Stack<>();
        }
    
        private void pushToPop() {
            // 两点原则：
            // 1、pop栈必须为空时才倒入
            if (popStack.empty()) {
                // 2、要倒就一次性全倒完
                while (!pushStack.empty()) {
                    popStack.push(pushStack.pop());
                }
            }
        }
    
        public void push(T t) {
            pushStack.push(t);
            pushToPop();
        }
    
        public T pop() {
            if (popStack.empty() && pushStack.empty()) {
                return null;
            }
            pushToPop();
            return popStack.pop();
        }
    
        public T peek() {
            if (popStack.empty() && pushStack.empty()) {
                return null;
            }
            pushToPop();
            return popStack.peek();
        }
    
        public static void main(String[] args) {
            SingleDirTwoStackQueue<Integer> queue = new SingleDirTwoStackQueue<>();
            for (int i = 0; i < 100; i++) {
                // 多存少取
                if (Math.random() < 0.7) {
                    queue.push(i);
                } else {
                    System.out.print(queue.pop() + "\t");
                }
            }
            System.out.println("\n==================");
            while (true) {
                Integer tail = queue.pop();
                if (tail == null) break;
                System.out.print(tail + "\t");
            }
        }
    }

# 六、只使用队列实现栈 #

使用经典的单向队列实现栈结构。

思路是，使用两个队列，masterQueue和slaveQueue，放入的时候，正常放入，当要取出的时候，循环将元素从master放入到slave中，最后只留 1 个元素，并返回，然后将 slave 与 master 的引用互换。

完整代码如下：

import java.util.LinkedList;
    import java.util.Queue;
    
    /**
     * 双队列栈
     */
    public class TwoQueueStack<T> {
        private Queue<T> masterQueue;
        private Queue<T> slaveQueue;
    
        public TwoQueueStack() {
            this.masterQueue = new LinkedList<>();
            this.slaveQueue = new LinkedList<>();
        }
    
        public void push(T t) {
            masterQueue.offer(t);
        }
    
        public T poll() {
            while (masterQueue.size() > 1)
                slaveQueue.offer(masterQueue.poll());
            T ans = masterQueue.poll();
            Queue<T> tmp = masterQueue;
            masterQueue = slaveQueue;
            slaveQueue = tmp;
            return ans;
        }
    
        public T peek() {
            while (masterQueue.size() > 1)
                slaveQueue.offer(masterQueue.poll());
            T ans = masterQueue.poll();
            // peek 与 poll的区别就是取出后，再次放回
            slaveQueue.offer(ans);
            Queue<T> tmp = masterQueue;
            masterQueue = slaveQueue;
            slaveQueue = tmp;
            return ans;
        }
    
    }

[20210404114112167.png]: /images/20221022/828b6c7779fe4f7a84ddca8f32695d20.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70]: /images/20221022/1c919a37613d4a8094ea0af29fbf0d52.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70 1]: /images/20221022/a780a09401ac44caaea8ff4f8b05cd97.png