[编程题]用两个栈实现队列

```class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
if(stack2.empty()){
while(!stack1.empty()){
int top = stack1.top();
stack1.pop();
stack2.push(top);
}
}
int top = stack2.top();
stack2.pop();
}
private:
stack<int> stack1;
stack<int> stack2;
};```

```class Solution
{
public:
void push(int node) {
stack1.push(node);
}```
```    int pop() {
int a;
if(stack2.empty()){
while(!stack1.empty()){
a=stack1.top();
stack2.push(a);
stack1.pop();
}
}
a=stack2.top();
stack2.pop();
return a;

}```
```private:
stack<int> stack1;
stack<int> stack2;
};```

<分析>：

如果不为空，栈B直接出栈。

<分析>：

```这是左程云的《程序员代码面试指南》的答案：
import java.util.Stack;

public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node) {
stack1.push(node);
}

public int pop() {
if(stack1.empty()&&stack2.empty()){
throw new RuntimeException("Queue is empty!");
}
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}```

• 栈A用来作入队列
• 栈B用来出队列，当栈B为空时，栈A全部出栈到栈B,栈B再出栈（即出队列）
```# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stackA = []
self.stackB = []

def push(self, node):
# write code here
self.stackA.append(node)

def pop(self):
# return xx
if self.stackB:
return self.stackB.pop()
elif not self.stackA:
return None
else:
while self.stackA:
self.stackB.append(self.stackA.pop())
return self.stackB.pop()```

//每次psuh是时先将stack2清空放入stck1(保证选入的一定在栈底)，stack2始终是用来删除的
//在pop前，先将stack1中中的数据清空放入stack2（保存后入的在栈底），stack1始终用于push
```import java.util.Stack;

public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node) {
while(!stack2.isEmpty()){
stack1.push(stack2.pop());
}
stack1.push(node);
}

public int pop() {
while (!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.pop();
}
}```

Javascript 用来展示思路尤其方便。

```var inStack = [],
outStack = [];
function push(node) {
// write code here
inStack.push(node);
}
function pop() {
// write code here
if (!outStack.length) {
while (inStack.length) {
outStack.push(inStack.pop());
}
}
return outStack.pop();
}
```

```# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []

def push(self, node):
# write code here
if len(self.stack1) == 0:
while len(self.stack2):
self.stack1.append(self.stack2.pop())
self.stack1.append(node)

def pop(self):
# return xx
if not len(self.stack2) == 0:
return self.stack2.pop()
else:
while len(self.stack1) > 1:
self.stack2.append(self.stack1.pop())
return self.stack1.pop()```

```class Solution
{
public:
void push(int node) {
stack1.push(node);
}

int pop() {
//等待栈2出完后才能继续入栈不然，不然就会占据栈顶
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}
}
int t=stack2.top();
stack2.pop();
return t;
}

private:
stack<int> stack1;
stack<int> stack2;
};```

C++:
```void push(int node)
{
stack1.push(node);
}
int pop()
{
if(stack2.empty())
{
while(!stack1.empty())
{
stack2.push(stack1.top());
stack1.pop();
}
}
int result=stack2.top();
stack2.pop();
return result;
}```

```import java.util.Stack;

public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node) {
stack1.push(node);
}

public int pop() {

while(!stack2.isEmpty())
{
return stack2.pop();
}

while(!stack1.isEmpty())
{
stack2.push(stack1.pop());
}

return stack2.pop();
}
}```

```import java.util.Stack;

public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node) {
stack1.push(new Integer(node));
}

public int pop() {
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.pop());
}
}
if(stack2.empty())
System.out.println("stack1 is empty!");

return stack2.pop().intValue();

}
}

```

import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node) {
stack1.push(new Integer(node));
}

public int pop() {
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.pop().intValue();
}
}

``````class Solution
{
public:
void push(int node) {
stack1.push(node);
}

int pop() {
if(stack2.empty()){
while(!stack1.empty()){
int tmp = stack1.top();
stack1.pop();
stack2.push(tmp);
}
int a = stack2.top(); stack2.pop();
return a;
}else{
int a = stack2.top(); stack2.pop();
return a;
}
}

private:
stack<int> stack1;
stack<int> stack2;
};
``````

```class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, node):
# write code here
self.stack1.append(node)
def pop(self):
# return xx
if len(self.stack2) > 0:
return self.stack2.pop()
while self.stack1:
self.stack2.append(self.stack1.pop())
if len(self.stack2) > 0:
return self.stack2.pop()
```

# python solution:

```# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.arr=[]
def push(self, node):

self.arr.append(node)
def pop(self):

return self.arr.pop(0)```

```//栈的特点：后进先出。队列的特点：先进先出。所以在push方面是一样的，在pop方面需要一个stac//k来做辅助，可以想象成从一杯中把水倒到另一杯中。 import java.util.Stack;

public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node) {
}

public int pop() {
if(stack2.size()==0){
while (stack1.size()!=0){
stack2.push(stack1.pop());//stack1的第一个元素在stack2的末尾
}
return stack2.pop();
}else {//因为stack1的size是在改变的所以当stack2中有元素时需要放到stack1的末尾先输出
stack1.push(stack2.pop());
return stack1.pop();
}

}
} ```

## 我的答案

``````import java.util.Stack;

public class Solution{
//负责装元素
Stack<Integer> stack1 = new Stack<Integer>();
//负责出元素
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node) {
stack1.push(node);
}

//主要思想是：stack2有元素就pop，没有元素就将stack1中所有元素倒进来再pop
public int pop() throws Exception{
if(!stack2.isEmpty()){
int node = stack2.pop();
return node;
}else{
if(stack1.isEmpty()){
throw new Exception("no valid element");
}
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
}``````

```#Python   感觉讨论组里都是java啊
#无力吐槽了，感觉后台好傻逼，刚开始用随便取了两个变量名，说是越界啥子的，
#后来改成stack1，stack2就过了

class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, node):
self.stack1.append(node)
def pop(self):
if len(self.stack2) != 0:
return self.stack2.pop()
while len(self.stack1) !=0:
self.stack2.append(self.stack1.pop())

return self.stack2.pop()```

public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node) {
stack1.push(node);
}

public int pop() {
int len = stack1.size();
for(int i = 0;i < len - 1;i++)  //有一种错误写法,for(int i = 0;i < stack1.size();i++)
{
stack2.push(stack1.pop());
}
int result = stack1.pop();
while(!stack2.isEmpty())
{
stack1.push(stack2.pop());
}
return result;
}
}

import java.util.Stack;

public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
int temp,target;
public void push(int node) {
stack1.push(node);
}

public int pop() {
while (!stack1.isEmpty()){
temp = stack1.pop();
stack2.push(temp);
}
target = stack2.pop();
while(!stack2.isEmpty()){
temp = stack2.pop();
stack1.push(temp);
}

return target;

}
}

```    public void push(int node) {
stack1.push(node);
}

public int pop() {
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
```

1、如果s2不为空，则返回顶部数据，
2、如果s2为空，s1不为空，则将s1的数据复制到s2后，返回s2顶部数据
3、如果s1也为空，则抛出异常

import java.util.Stack;

public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node) {
stack1.push(node);
}

public int pop() throws Exception {
if (!stack2.isEmpty()){
return stack2.pop();
}else if (!stack1.isEmpty()){
while (!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.pop();
}else{
throw new Exception("the queue is empty");
}
}
}

1791条回答 198784浏览

# 通过挑战的用户

• 2019-10-21 12:48:59
• 2019-10-21 12:11:18
• 2019-10-21 12:05:07
• 2019-10-21 11:51:03
• 2019-10-21 11:46:28

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题