|
这是我在leetcode的正经八百的第二道题，思路还是没怎么又，所以膜拜了几个大佬和官方的答案，我发现答案看懂了以后就好简单呀，真不知道自己一开始为啥怎么都想不到！所以就简单记录一下。
题目：
请你仅使用两个队列实现一个后入先出（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（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
思路：这里可以先用两个队列，其中一个队列可以做类似备份的东西。有两种办法，一种是直接以队列方式存储，然后pop的时候进行相应的处理，另一种就是直接存成栈。然后，使用一个队列，直接将数据存成一个栈。
代码：
法一：
class MyStack {
private:
queue<int> first;
queue<int> second;
public:
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
first.push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int s = first.size();
while(--s){
int val = first.front();
first.pop();
second.push(val);
}
int anw = first.front();
first = second;
while(!second.empty()){
second.pop();
}
return anw;
}
/** Get the top element. */
int top() {
int size = first.size();
while(--size){
int val = first.front();
first.pop();
second.push(val);
}
int anw = first.front();
second.push(anw);
first = second;
while(!second.empty()){
second.pop();
}
return anw;
}
/** Returns whether the stack is empty. */
bool empty() {
return first.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
法二：
class MyStack {
private:
queue<int> main;
queue<int> minor;
public:
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
minor.push(x);
while(!main.empty()){
minor.push(main.front());
main.pop();
}
swap(main,minor);
//清空minor
while(!minor.empty()){
minor.pop();
}
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int x = main.front();
main.pop();
return x;
}
/** Get the top element. */
int top() {
return main.front();
}
/** Returns whether the stack is empty. */
bool empty() {
return main.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
法三：
class MyStack {
private:
queue<int> main;
public:
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
main.push(x);
int size = main.size();
while(--size){
main.push(main.front());
main.pop();
}
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int x = main.front();
main.pop();
return x;
}
/** Get the top element. */
int top() {
return main.front();
}
/** Returns whether the stack is empty. */
bool empty() {
return main.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
|