题目描述:
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push
、pop
、peek
、empty
):
实现 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;
}