logo头像

不破不立

《程序员代码面试指南》两个栈实现队列

这是一道面试很常见的算法题,首先要熟悉栈和队列的特点,栈是先进后出,队列是先进先出。

编写一个类,用两个栈实现队列,支持队列的基本操作(add,poll,peek)

  栈和队列的特点,栈是先进后出,队列是先进先出

题目

编写一个类,用两个栈实现队列,支持队列的基本操作(add,poll,peek)

#实现思想

  用两个栈A,B;
  A用来存储进行add操作的元素;每次add都将元素压入A栈中;
  B则是用来存储进行poll和peek操作的元素,这些元素都是从A栈中来的;每次进行poll和peek操作时,先判断B栈是否为空;若不为空,则将栈顶元素pop出来或者peek出来;若为空,则将A栈中的元素一一push到B栈中,直到A栈为空时,停止push操作,然后将B栈栈顶元素pop出来或peek出来;这样实现的顺序正好是队列先进先出的情况。
  如下图解释
TwoStacksQueue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package site.sixteen.stack_queue;

import java.util.Stack;

/**
* TowStackQueue
*
* @author panhainan@yeah.net(@link https://sixteen.site)
* @version 1.0
* @use 两个栈实现队列
* @date 2018/8/22
**/
public class TowStackQueue<T> {


/**
* 入队栈
*/
private Stack<T> stackIn;
/**
* 出队栈
*/
private Stack<T> stackOut;

public TowStackQueue() {
stackIn = new Stack<>();
stackOut = new Stack<>();
}

/**
* @param t 入队元素
* @use 入队
*/
public void add(T t) {
stackIn.push(t);
}

/**
* @return 出队元素
* @use 出队
*/
public T poll() {
stackInToStackOut();
return stackOut.pop();
}


/**
* 取队头元素
*
* @return 队头元素
*/
public T peek() {
stackInToStackOut();
return stackOut.peek();
}

/**
* 判断队列是否为空
*
* @return
*/
public boolean empty() {
return stackOut.empty() && stackIn.empty();
}

/**
* 获取队列大小
*
* @return 队列大小
*/
public int size() {
return stackOut.size() + stackIn.size();
}

private void stackInToStackOut() {
if (empty()) {
throw new RuntimeException("Queue is empty!");
} else if (stackOut.empty()) {
while (!stackIn.empty()) {
stackOut.push(stackIn.pop());
}
}
}
}
上一篇

评论系统未开启,无法评论!

如果有好的建议或疑问等可以发送邮件至:panhainan@yeah.net,或者添加QQ:1016593477,将你的建议或者疑问告诉作者,作者会对你的建议进行处理并补充到文章的尾部,谢谢大家的谅解!