232.用栈实现队列
题目描述:
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push
、pop
、peek
、empty
):
实现 MyQueue
类:
void push(int x)
将元素 x 推到队列的末尾int pop()
从队列的开头移除并返回元素int peek()
返回队列开头的元素boolean empty()
如果队列为空,返回true
;否则,返回false
说明:
- 你 只能 使用标准的栈操作 —— 也就是只有
push to top
,peek/pop from top
,size
, 和is empty
操作是合法的。 - 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
思路:使用栈来模式队列的行为,如果仅仅用一个栈,是一定不行的,所以需要两个栈一个输入栈,一个输出栈,这里要注意输入栈和输出栈的关系。
在push数据的时候,只要数据放进输入栈就好。
但在pop的时候,操作就复杂一些,输出栈如果为空,就把进栈数据全部出栈,然后全部导入进输出栈(注意是全部导入),再从出栈栈顶弹出数据;如果输出栈不为空,则直接从出栈弹出数据就可以了。
我们用C++容器中的stack来作为栈的实现。其常用接口如下:
构造函数:
stack<T> stk; //stack采用模板类实现,stack对象的默认构造形式
stack(const stack &stk); //拷贝构造函数
赋值操作:
stack& operator=(const stack &stk); //重载等号操作符
数据存取:
push(elem); //向栈顶添加元素,注意无返回值
pop(); //从栈顶移除第一个元素,注意无返回值
top(); //返回栈顶元素
大小操作:
empty(); //判断堆栈是否为空
size(); //返回栈的大小
class MyQueue {
private:
stack<int> stack_in; //输入栈,用于入队
stack<int> stack_out; //输出栈,用书出队
int size; //维护了一个size表示队列长度
public:
MyQueue() {
size=0;
}
void push(int x) {
stack_in.push(x);
size++;
}
int pop() {
//如果输出栈为空,则先将输入栈的数据全部依次出栈,并入栈到输入栈
if(stack_out.empty())
{
while(!stack_in.empty())
{
stack_out.push(stack_in.top());
stack_in.pop();
}
}
int tmp = stack_out.top(); //记录栈顶的值作为出队数据
stack_out.pop();
size--;
return tmp;
}
int peek() { //获取队头数据,不能删除,
if(!stack_out.empty())
{
return stack_out.top();//用来读取栈顶元素,而不是出栈
}
else{
while(!stack_in.empty())
{
int tmp = stack_in.top();
stack_out.push(tmp);
stack_in.pop();
}
return stack_out.top();
}
}
bool empty() {
if(size>0)
{
return false;
}
else
return true;
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
如果不想维护队列的size属性,则empty()函数实现如下:
bool empty()
{
return stack_in.empty() && stack_out.empty();
}
如果接的peek()函数还要在判断输出栈是否为空,比较复杂,可以使用上面实现好的pop函数,也提高了代码的复用率。代码如下:
int peek()
{
int tmp = this->pop(); //用tmp记录出队元素,也就是队首元素。本质是stack_out出栈了栈顶元素
stack_out.push(tmp); //所以还要再给stack_out入栈回去
return tmp;
}
225. 用队列实现栈
题目描述:
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push
、top
、pop
和 empty
)。
实现 MyStack
类:
void push(int x)
将元素 x 压入栈顶。int pop()
移除并返回栈顶元素。int top()
返回栈顶元素。boolean empty()
如果栈是空的,返回true
;否则,返回false
。
注意:
- 你只能使用队列的基本操作 —— 也就是
push to back
、peek/pop from front
、size
和is empty
这些操作。 - 你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
思路分析:
队列是先进先出的规则,把一个队列中的数据导入另一个队列中,数据的顺序并没有变,并没有变成先进后出的顺序。
所以用栈实现队列, 和用队列实现栈的思路还是不一样的,这取决于这两个数据结构的性质。
但是依然还是要用两个队列来模拟栈,只不过没有输入和输出的关系,而是另一个队列完全用来备份的!
用两个队列que1和que2实现队列的功能,que2其实完全就是一个备份的作用,把que1最后面的元素以外的元素都备份到que2,然后出队最后面的元素,再把其他元素从que2导回que1。
我们用c++容器中的单向queue来作为两个队列的基本实现,如果是双端队列deque没啥意义,因为两端都能出队入队,一端进,另一端出,直接就能当栈使用。
queue的常用接口如下:
构造函数:
queue<T> que; //queue采用模板类实现,queue对象的默认构造形式
queue(const queue &que); //拷贝构造函数
赋值操作:
queue& operator=(const queue &que); //重载等号操作符
数据存取:
push(elem); //往队尾添加元素,入队操作,无返回值。
pop(); //从队头移除第一个元素,出队操作,无返回值。出队的元素不会被返回
back(); //返回最后一个元素
front(); //返回第一个元素
大小操作:
empty(); //判断堆栈是否为空
size(); //返回栈的大小
代码实现:
class MyStack {
private:
queue<int> que1;
queue<int> que2;//做备份用
public:
MyStack() {
}
void push(int x) {
que1.push(x); //入队
}
int pop() {
//需要que1中除最后一个元素之外的所有元素出队,然后入队到que2中,这时候que1中还剩的最后一个就是该出栈的元素。
int size = que1.size();
while(size>1)
{
que2.push(que1.front());
que1.pop();//出队
size--;
}
int res = que1.front(); //记录这最后一个元素
que1.pop();
//然后再将que2中的元素按顺序入队到que1中,由两种思路
//方法1.
while(!que2.empty())
{
que1.push(que2.front());
que2.pop();
}
//方法2
/*que1 = que2; // 再将que2赋值给que1
while (!que2.empty()) { // 清空que2
que2.pop();
}*/
return res;
}
int top() {
//方法1.利用刚刚实现的pop简化代码
int tmp = this->pop();
this->que1.push(tmp);
return tmp;
//方法2.或者用back() 返回队尾元素
//return que1.back();
}
bool empty() {
return que1.empty();
}
};
优化:
其实这道题目就是用一个队列就够了。
一个队列在模拟栈弹出元素的时候只要将队列头部的元素(除了最后一个元素外) 重新添加到队列尾部,此时再去弹出元素就是栈的顺序了。代码如下着重看一下pop()函数:
class MyStack {
public:
queue<int> que;
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
que.push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int size = que.size();
while (size>1) { // 将队列头部的元素(除了最后一个元素外) 重新添加到队列尾部
que.push(que.front());
que.pop();
}
int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
que.pop();
return result;
}
/** Get the top element. */
int top() {
return que.back();
}
/** Returns whether the stack is empty. */
bool empty() {
return que.empty();
}
};