栈与队列

LeetCode: [20] 有效的括号、

栈：先进后出，队列：先进先出

java Stack

1	boolean empty()  测试堆栈是否为空。
2	Object peek( ) 查看堆栈顶部的对象，但不从堆栈中移除它。
3	Object pop( ) 移除堆栈顶部的对象，并作为此函数的值返回该对象。
4	Object push(Object element) 把项压入堆栈顶部。
5	int search(Object element) 返回对象在堆栈中的位置，以 1 为基数。
6	int size() 返回堆栈的大小与数量 （注意：不能再循环里使用stack.size()，因为pop会使size()变小）

Python Stack

python中没有确切的stack，但他的列表有pop，append(push)等栈的操作

具体可以查看https://docs.python.org/zh-cn/3/tutorial/datastructures.html

用两个栈实现队列

// LeetCode 232 用栈实现队列
class MyQueue {
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;
    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }
    
    public void push(int x) {
        stackIn.push(x);
    }
    
    public int pop() {
        dumpStack();
        return stackOut.pop();
    }
    
    public int peek() {
        dumpStack();
        return stackOut.peek();
    }
    
    public boolean empty() {
        return stackIn.empty() && stackOut.empty();
    }

    private void dumpStack(){
        if(!stackOut.empty()) return;
        while(!stackIn.empty()){
            stackOut.push(stackIn.pop());
        }
    }
}

Java Queue

 Queue<Integer> queue = new LinkedList<>();

	throw Exception	返回false或null
添加元素到队尾	add(E e)	boolean offer(E e)
取队首元素并删除	E remove()	E poll()
取队首元素但不删除	E element()	E peek()

优先队列

// 小顶堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a,b)->a-b);
// 大顶堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a,b)->b-a);