学习交流加

  • 个人qq：
    1126137994
  • 个人微信：
    liu1126137994
  • 学习交流资源分享qq群：
    962535112

牛客网题目链接：用两个栈实现队列

文章目录

题目描述：

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

1、题目分析

首先我们知道数据结构中栈与队列的特性是：

  • 栈：数据先进后出
  • 队列：数据先进先出

假设现在队列的两个基本操作为push与pop，两个辅助的栈为stack1与stack2。那么可以这实现队列的性质：

当我们push数据的时候，只把数据往stack1中压入。因为压入到stack1中的数据是先进后出，顺序是反的，所以当需要pop数据时，再将stack1中的数据全部倒入（弹出）到stack2，这样的话，数据的顺序就变回来了，此时再在stack2中弹出数据返回即可。例如往stack1中压入1-5，此时在stack1中由上往下是5-1，当想pop时，先将 stack1中的5-1倒入stack2，那么在stack2中由上往下就是1-5，此时再让stack2弹出1即可，这就模拟了先进先出规则。如下图所示：

以上只是很简单的情况（第一次倒数据）。还有这种情况，1-5已经倒入到stack2中，然后stcak1中没有数据了，如果现在push，就将数据压入到stack1中。如果再pop呢？首先需要判断stack2中还有没有数据，如果stack2中还有数据，则继续弹出stack2中的数据。如果stack2中没有数据了，则将stack1中的所有数据全部倒入stack2中，然后从stack2中弹出数据（自己想一下这个过程）。那么这就是一个完全模拟队列的过程。

2、代码

Java代码：

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node); //stack1 用于push数据
    }
    /* stack2用于pop数据 */
    public int pop() {
    	/* 对于题来说，可以不用判断异常情况也可以通过 */
        if(stack1.isEmpty() && stack2.isEmpty()){
            throw new RuntimeException("Queue is empty!");
        }
        /* 如果Stack2为空，则将stack1中的数据全部倒进stack2 */
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

C++代码

class Solution
{
public:
    void push(int node) {
        /* stack1作为插入数据的栈 */
        stack1.push(node);
    }
    int pop() {
        /* stack2作为pop数据的栈 */
        int tmp=0;
        if(stack2.empty()){
            while(!stack1.empty()){
                tmp=stack1.top();
                stack1.pop();
                stack2.push(tmp);
            }
        }
        tmp=stack2.top();
        stack2.pop();
        return tmp;
    }
private:
    stack<int> stack1;
    stack<int> stack2;
};

3、总结

理解栈与队列的push与pop操作。

学习探讨加：
qq：1126137994
微信：liu1126137994