手写栈和队列面试专项
这节课我们学习栈和队列。 栈和队列都是非常基础的数据结构，使用场景非常广泛。比如栈是实现函数调用的基础；队列是实现生产者消费者模型的基础。关于栈和队列，难度不高，但是重要性很高。也有一些巧妙的算法，是基于栈和队列的，比如说表达式的解析。这节课我们就一起来学习栈和队列。
关联的面试题：
- 栈和队列的基本概念：什么是栈、队列？
- 栈和队列的实现和基本操作接口？
- 栈实现队列？队列实现栈？
- 括号匹配问题？
- 表达式解析问题？
栈(Stack)
栈(Stack)， 你可以想象成一打摆放整齐的书。只有两种操作，继续往上放书，称之为压栈(push)；把最上面的书拿下来，称之为出栈(pop)。
考虑现实意义，例如：子函数调用，压在父函数调用之上。子函数调用完成，父级函数才能返回。这样，函数调用，就可以使用压栈(push)来模拟；函数返回，就可以用出栈来模拟。构造起来是一个先入先出（First In First Out)的顺序。
栈的实现可以基于双向链表（LinkedList）或者数组（比如Array,ArrayList）。程序如下：
public class Stack<T> {
LinkedList<T> list = new LinkedList<>();
public void push(T e) {
list.addFirst(e);
// list.push(e);
}
public T pop() {
//list.removeFirst();
return list.pop();
}
public int size(){
return list.size();
}
@Test
public void test() {
var stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
assertEquals(4, stack.pop());
assertEquals(3, stack.pop());
assertEquals(2, stack.pop());
assertEquals(1, stack.pop());
}
}在上面的程序中push和pop两个操作都可以在O(1)完成。
队列(Queue)
队列（Queue）， 对应现实世界中的场景就是排队。在计算机领域举个例子，比如排队执行的线程、排队执行的任务。
排队会满足陷入先出的顺序，First In First Out（FIFO）。
排队也称作入队（enqueue)操作，离开队列也称为出队(dequeue)操作。这两个操作都可以用双向链表模拟，代码如下：
public class Queue<T> {
LinkedList<T> list = new LinkedList<>();
public void enqueue(T e){
list.add(e);
}
public T dequeue(){
return list.remove();
}
public int size(){
return list.size();
}
@Override
public String toString(){
return list.toString();
}
@Test
public void test(){
var queue = new Queue<>();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
assertEquals(1, queue.dequeue());
assertEquals(2, queue.dequeue());
assertEquals(3, queue.dequeue());
assertEquals(4, queue.dequeue());
}
}上面程序中，enqueue和dequeue都是O(1)的操作。
面试题：两个栈实现队列
问题：用两个栈实现队列
栈是FILO结构，如果一个FILO结构，再接上一个FILO结构。最先进去的元素，会最先通过两个栈。因此这个题目可以用这样的思路解决。
public class Queue2<T> {
Stack<T> s1 = new Stack<>();
Stack<T> s2 = new Stack<>();
public void enqueue(T e) {
s1.push(e);
}
public T dequeue() {
if(s2.size() > 0) {
return s2.pop();
}
while(s1.size() > 0) {
var item = s1.pop();
s2.push(item);
}
return s2.pop();
}
@Test
public void test(){
var queue = new Queue2<>();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
assertEquals(1, queue.dequeue());
assertEquals(2, queue.dequeue());
assertEquals(3, queue.dequeue());
assertEquals(4, queue.dequeue());
}
}面试题：括号匹配问题
问题描述：判断一个含有{}的表达式中括号是否匹配。例如：
{}{} ： ture
{123{a+b}} : true
}{ : false解析
遍历字符串:
- 遇到
{将它压栈 - 遇到其他字符，什么都不做
- 遇到
}出栈一个字符，看是不是{；如果不是，说明不匹配返回false
最后看栈中是否还有元素，如果还有，也说明不匹配。
程序如下：
public class Bracket {
public boolean isMatch(String str){
var stack = new Stack<Character>();
for(char c : str.toCharArray()) {
if(c == '{') {
stack.push(c);
continue;
}
if(c == '}') {
if(stack.size() == 0) {
return false;
}
var item = stack.pop();
if(item != '{') {
return false;
}
}
}
return stack.size() == 0;
}
@Test
public void test(){
var cases = new String[]{
"{1}{2}{3}",
"{{1+2}{{3+4}}}",
"1*{2+3*{4+5}}",
"",
"{",
"}}{{",
"{{{}",
};
var values = new Boolean[] {
true,
true,
true,
true,
false,
false,
false
};
for(int i = 0; i < cases.length; i++) {
var c = cases[i];
assertEquals(values[i], isMatch(c));
}
}
}总结
Queue是后续我们学习并发编程的基础；Stack是理解程序执行的基础——这只是冰山一角。作为最常见的两个数据结构，他们的使用范围非常广泛。
如果想进一步灵活运用Queue和Stack相关的技巧，可以学习一下下一堂课——用栈和队列实现表达式解析。