|
leetcode中要求用栈实现队列的一下四个方法。
- push(x) -- Push element x to the back of queue.
- pop() -- Removes the element from in front of queue.
- peek() -- Get the front element.
- empty() -- Return whether the queue is empty.
思路1：有两个栈s1,s2。用s1存储队列元素，s2用作辅助操作。
// Push element x to the back of queue.
public void push(int x) {
s1.push(x); //s1的栈顶是队列尾，可以直接进行push操作
}
/**
* 为了去掉栈底的元素需要将S1都pop到s2中（其实就是调个头）
*/
// Removes the element from in front of queue.
public void pop() {
while(!s1.isEmpty()){
s2.push(s1.pop());
}
s2.pop();
while(!s2.isEmpty()){
s1.push(s2.pop());
}
}
// Get the front element.
public int peek() {
while(!s1.isEmpty()){
s2.push(s1.pop());
}
int tmp = s2.pop();
s1.push(tmp);
while(!s2.isEmpty()){
s1.push(s2.pop());
}
return tmp;
}
// Return whether the queue is empty.
public boolean empty() {
if(s1.isEmpty()){
return true;
}else{
return false;
}
}
这个思路比较大众，注释里也进行了讲解，应该不难理解。其存在的最大问题就是push操作比较简单，而pop操作则一定要将s1中所有的元素都转移到s2，操作完了还得再放回s1.即麻烦又耗时。
思路2：假设s1自栈顶到栈底存放队列的前半段，s2自栈底到栈顶存放队列的后半段。好比脑子里有两个杯子一样的栈，将两个杯子的低合在一起，水从一头进，从另一头出。这就形成了队列。
问题1:思路没问题，具体实现时需要考虑一个情况，当从s1（相当于前面一个杯子）pop数据时如果它为空怎么办，这可并不一定代表队列为空啊，因为s2里面可能有数据的。此时，需要将s2中的元素都放到s1中。
思路到这里应该是没问题的，代码如下
// Push element x to the back of queue.
public void push1(int x) {
if(s1.isEmpty()&&s2.isEmpty())
s1.push(x);
else
s2.push(x);
}
// Removes the element from in front of queue.
public void pop1() {
//考虑当s1为空时，要将s2的数据放到s1中。
if(s1.isEmpty()){
while(!s2.isEmpty()){
s1.push(s2.pop());
}
}
s1.pop();
}
// Get the front element.
public int peek1() {
int tmp;
if(s1.isEmpty()){
while(!s2.isEmpty()){
s1.push(s2.pop());
}
}
tmp = s1.pop();
s1.push(tmp);
return tmp;
}
// Return whether the queue is empty.
public boolean empty1() {
if(s1.isEmpty()&&s2.isEmpty()){
return true;
}else{
return false;
}
}
很显然思路2的效率是比思路1高的，push操作基本一致，pop操作并不一定要将s2的数据转移到s1，而且还省下了再把数据倒回去的操作，因此效率至少提升了50%（至少会少一次倒数据嘛）。
| 
转播
