学习交流加

  • 个人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