数据结构 栈实现队列

发布于:2024-05-06 ⋅ 阅读:(29) ⋅ 点赞:(0)

题目描述:

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpoppeekempty):

实现 MyQueue 类:

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空,返回 true ;否则,返回 false

在做这道题目前要明白什么是栈什么是队列

栈就是后进先出的一个容器

队列就是先进先出的一个容器

然后了解栈的创建:stack<int>  jinzihao;这样就创建了一个int类型名为jinzihao的栈了

下面是对栈中元素的操作:

jinzihao.push(x);表示往jinzihao这个栈里面尾部插入一个元素值为x

jinzihao.top(x);表示查找jinzihao这个栈的顶部元素值

jinzihao.pop(x); 表示弹出栈中最顶部的元素,此时栈的大小 - 1

jinzihao.empty(x);表示判断jinzihao这个栈中是否为空,如果空返回true

有了上面的知识,下面我们来看看思路:

为了模拟队列,我们要用两个栈来实现

首先写函数

void push(int x) 将元素 x 推到队列的末尾

直接使用push将x值放入stin的栈中

下面是函数

int pop() 从队列的开头移除并返回元素

注意要返回并且移除,如果我们直接使用pop只能删除stin中的最后进入的元素

所以我们要使用另外一个栈

两个栈分别为stin和stout

pop的操作分为两个情况

一:pop前函数里面没有内容(需要把stin的内容转移到stout中)

操作:stout.push(stin.top());表示把in最上面的数导入stout中

然后删除最上面的数

后面的操作和步骤二一样

二:首先找到stout.top()  并且保存到变量中

然后通过stout.pop()删除

最后把变量返回

    int pop() {
        // 只有当stOut为空的时候,再从stIn里导入数据(导入stIn全部数据)
        if (stOut.empty()) {
            // 从stIn导入数据直到stIn为空
            while(!stIn.empty()) {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;
    }

 三:函数peek 查找列表首个元素

这个函数的实现就需要用到我们刚刚写的pop函数,

思路:首先 int    a   =  this -> pop;

这样可以把a赋值最上面的值

但是为了不影响内容要通过push把a重新放回去

最后return a;

代码:

    int peek() {
        int res = this->pop(); // 直接使用已有的pop函数
        stOut.push(res); // 因为pop函数弹出了元素res,所以再添加回去
        return res;
    }