How to implement a queue with two stacks?

Java基础教程栏目介绍如何用两个栈实现一个队列。

队列和栈是计算机中两个非常重要的数据结构，经过前面的学习（《队列》、《栈》）我们知道了它们各自的特点，队列是先进先出（FIFO）的，而栈是先进后出（FILO）的，那如何用栈来实现队列呢？这可是一道经典的面试题，所以本文我们就来实现一下。

在正式开始之前，我们先来回顾一下栈和队列的常用方法。

栈（Stack）的常用方法包含以下这些：

• push()：入栈方法，向栈顶添加元素；
• pop()：出栈方法，将栈顶的元素移除并返回元素；
• peek()：查询栈顶元素，并不会移除元素。

队列（Queue）的常用方法包含以下这些：

• offer()：入队方法，向队尾添加元素；
• poll()：出队方法，从队头移除并返回元素；
• peek()：查询队头元素，并不会移除元素。

有了这些前置知识，接下来我们来看今天的题目。

题目描述

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead，分别完成在队列尾部插入整数和在队列头部删除整数的功能，若队列中没有元素，deleteHead 操作返回 -1。

示例 1：

输入：

["CQueue","appendTail","deleteHead","deleteHead"]

[[],[3],[],[]]

输出：[null,null,3,-1]

示例 2：

输入：

["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]

[[],[],[5],[2],[ ],[]]

Output: [null,-1,null,null,5,2]

Prompt:

1

Up to 10000 calls to appendTail and deleteHead will be made

leetcode: leetcode-cn.com/problems/yo…

Solution Question idea

The meaning of this question is actually easy to understand, which is to change the first-in-last-out stack to a first-in-first-out queue. In fact, the question also gives some tips, "Use two stacks to Implement a queue". The core idea of ​​​​this question is "a negative makes a positive". We first use a stack to store elements (the first element to enter is at the bottom of the stack), and then add the elements in the first stack Move to the new stack. At this time, the first entered element is on the top of the stack. Then when the second stack is used to pop it out, the entire execution order becomes first-in, first-out.

Next, let’s implement the entire process graphically.

Step 1

First push the element into the first stack, as shown in the following figure:

Step 2

Push the element into the first stack The elements in one stack are moved to the second stack, as shown in the following figure:

Step 3

All elements are popped from the second stack, as shown in the following figure Shown:

Summary

As can be seen from the above picture, the order of adding elements is 1, 2, 3, and the final order of popping out the stack after passing through two stacks is also 1, 2 , 3, so that we implement the queue (first in, first out) through two stacks.

Implementation code

Next we will use code to implement the above ideas:

class CQueue {
    Stack<integer> inputStack; // 入栈的容器（添加时操作)
    Stack<integer> outputStack; // 出栈和查询的栈容器

    public CQueue() {
        inputStack = new Stack();
        outputStack = new Stack();
    }    // 添加操作
    public void appendTail(int value) {
        inputStack.push(value);
    }    // 删除操作
    public int deleteHead() {        if (!outputStack.isEmpty()) {            // 出栈容器不为空
            return outputStack.pop();
        } else if (!inputStack.isEmpty()) {            // 入栈 stack 全部转移到出栈 stack
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop());
            }
        }        return outputStack.isEmpty() ? -1 : outputStack.pop();
    }
}复制代码</integer></integer>

We submit the above test code in LeetCode, and the execution results are as follows:

Notes

There are two small details that require special attention during the entire implementation process:

1. The first stack is only responsible for pushing into the stack (temporarily Store data), the second stack is only responsible for popping (the final queue execution sequence);
2. Every time stack 2 is popped, all elements must be popped out before appending from stack 1 (Add) new data. When all the data in stack 2 are not pushed out of the stack, the elements from stack 1 cannot be pushed into stack 2. This will cause the execution order of the elements to be confused.

Summary

In this article, we use two first-in-last-out stacks and implement the first-in-first-out feature of the queue through the idea of ​​​​"negatives make positives", but special attention is required. When the second stack, which is the pop-up container, is not empty (stack), the elements in the first stack cannot be added to the second stack to avoid confusing the program execution order.

Related free learning recommendations: java basic tutorial

The above is the detailed content of How to implement a queue with two stacks?. For more information, please follow other related articles on the PHP Chinese website!