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

# 1336个回答

## 就借助栈先入后出的特点，进行操作就好

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

int pop() {
int data = 0;
if(stack2.size() <= 0)
{
while(stack1.size() > 0)
{
data = stack1.top();
stack1.pop();
stack2.push(data);
}
}
if(stack2.size() == 0)
throw "";
data = stack2.top();
stack2.pop();
return data;
}
``````

`class Solution `
查看全部

```这是左程云的《程序员代码面试指南》的答案：
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();
}
}```

```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()
```

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();
}
```

```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() {
//等待栈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;
}```

```# -*- 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()```

```//栈的特点：后进先出。队列的特点：先进先出。所以在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();
}

}
} ```

# 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)```

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;
}
}

```    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");
}
}
}

```//补一个js版本

var stack1 = [], stack2 = [];
function push(node)
{
// write code here
stack1.push(node);
}
function pop()
{
// write code here
if(stack2.length === 0){
while(stack1.length !== 0){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
module.exports = {
push : push,
pop : 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()```

Q：自己想测试这种代码的话，输入该怎么测试？！

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

}

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

}

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

1336条回答 126969浏览

# 通过挑战的用户

• 2018-12-14 15:31:00
• 2018-12-14 15:25:24
• 2018-12-14 15:13:40
• 2018-12-14 15:08:29
• 2018-12-14 15:04:31

# 相关试题

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

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

• 公司地址：北京市朝阳区大屯路东金泉时代3-2708北京牛客科技有限公司