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

# 1113个回答

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

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

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

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

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

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

}
} ```

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

/**
* 用两个栈来实现队列的push()和pop()操作
* 注意这里的队列的特性：先进先出，并且，其中的push()操作为添加元素到队列末尾，pop()操作为弹出队首元素，并且将其删除
* 其中栈的特性为：先进后出
* 算法思想：这里利用了两个栈，来实现队列的操作，由队列和栈的特性可以知道，可以利用一个栈来作为过渡使用，即：
* 当向队列中插入数据时，实际上将其插入栈stack1中
* 当要从队列中弹出队首元素时，就可以将stack1中的元素依次写入到stack2中（由于在stack1中元素的顺序与队列中的正好相反，所以再次反即为正，反反得正）
* 所以这个时候，从栈stack2中弹出的栈顶元素即为队列中的队首元素
*/
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

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

public int pop() {
//注意这里不必每次都将stack2清空，因为再后面的逆转回去时，会将栈中的元素pop()掉,这个操作就相当于清空了stack2，stack1也是一样的
//注意这里是将stack1中的元素逆转（反反得正）
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
//这里将要返回的队首的值取到了
int getNumber = stack2.pop();
//在取到对应的队首元素之后，就需要将剩下的元素在返回到原本的栈stack1中去
while(!stack2.isEmpty()){
stack1.push(stack2.pop());
}
return getNumber;
`    }`

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

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

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

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.isEmpty()&&stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}

1113条回答 93352浏览

# 通过挑战的用户

• 2018-06-23 19:36:26
• 2018-06-23 19:34:56
• 2018-06-23 18:58:09
• 2018-06-23 18:47:02
• 2018-06-23 18:44:32

# 相关试题

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

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

QQ群：169195721