两个队列实现一个栈+两个栈实现一个队列（Java 实现）

浅浅的花香味﹌ 2022-03-06 03:18 321阅读 0赞

#### 两个队列实现一个栈 ####

1.  现有两个队列 q1 和 q2，入栈则将元素加到 q1
2.  出栈的时候先判读 q1 是否为空，因为 q1 中的元素总是后进来的，后进先出，除了队列的最后一个元素，将其它元素添加到 q2，q1 的最后一个元素出队
3.  出栈的时候如果在 2 中判断 q1 为空，除了 q2 的最后一个元素，将 q2 中其它元素添加到 q1，然后 q2 中的最后一个元素出队

完整 Java 代码：

public class MyStack { 
    
        private Queue<Integer> q1 = new LinkedList<>();
        private Queue<Integer> q2 = new LinkedList<>();
    
        public MyStack() { 
        }
    
        public boolean push(Integer num) { 
            return q1.offer(num);
        }
    
        public Integer pop() { 
            if (q1.isEmpty() && q2.isEmpty()) { 
                return null;
            }
            // 先判断 q1 是否为空 
            if (!q1.isEmpty()) { 
                int size = q1.size();
                for (int i = 0; i < size - 1; i++) { 
                    q2.offer(q1.poll());
                }
                return q1.poll();
            } else { 
                int size = q2.size();
                for (int i = 0; i < size - 1; i++) { 
                    q1.offer(q2.poll());
                }
                return q2.poll();
            }
        }
    
        public Integer size() { 
            return q1.size() + q2.size();
        }
    
    
        public static void main(String[] args) { 
            MyStack stack = new MyStack();
            stack.push(1);
            stack.push(2);
            stack.push(3);
            stack.push(4);
            stack.push(5);
    
            int size = stack.size();
            for (int i = 0; i < size; i++) { 
                System.out.print(stack.pop() + " ");
            }
            System.out.println();
            stack.push(6);
            System.out.println(stack.pop());
        }
    }

#### 两个栈实现队列 ####

跟队列实现差不多，但比起两个队列实现栈来说却简单多了。

1.  有两个栈 stack1 和 stack2
2.  入队列的时候只往 stack1 添加元素就行
3.  出队列的时候先判断 stack2 是否为空，stack2 中的元素都是先进来的，先进先出。如果 stack2 不为空，则直接弹出 stack2 的栈顶元素。如果为空，则将 stack1 的元素添加到 stack2 中，然后弹出 stack2 的栈顶元素

看 Java 代码：

public class MyQueue { 
        private Stack<Integer> stack1 = new Stack<>();
        private Stack<Integer> stack2 = new Stack<>();
    
        /** * 添加元素到队列 * * @param num * @return */
        public Integer add(Integer num) { 
            return stack1.push(num);
        }
    
        /** * 队列弹出元素 * * @return */
        public Integer poll() { 
            if (stack1.isEmpty() && stack2.isEmpty()) { 
                return null;
            }
            // 先判断 stack2
            if (!stack2.isEmpty()) { 
                return stack2.pop();
            }
            // 将 stack1 的元素放入 stack2
            int size = stack1.size();
            for (int i = 0; i < size; i++) { 
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
    
        public int size() { 
            return stack1.size() + stack2.size();
        }
    
    
        public static void main(String[] args) { 
            MyQueue queue = new MyQueue();
            queue.add(1);
            queue.add(2);
            queue.add(3);
            queue.add(4);
            queue.poll();
            queue.add(5);
            int size = queue.size();
    
            for (int i = 0; i < size; i++) { 
                System.out.print(queue.poll() + " ");
            }
            System.out.println();
        }
    }