手写栈和队列面试专项

这节课我们学习栈和队列。 栈和队列都是非常基础的数据结构，使用场景非常广泛。比如栈是实现函数调用的基础；队列是实现生产者消费者模型的基础。关于栈和队列，难度不高，但是重要性很高。也有一些巧妙的算法，是基于栈和队列的，比如说表达式的解析。这节课我们就一起来学习栈和队列。

关联的面试题：

1. 栈和队列的基本概念：什么是栈、队列？
2. 栈和队列的实现和基本操作接口？
3. 栈实现队列？队列实现栈？
4. 括号匹配问题？
5. 表达式解析问题？

栈(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相关的技巧，可以学习一下下一堂课——用栈和队列实现表达式解析。