算法通关 - 栈和队列

栈（stack）

栈是一种线性存储结构，它有以下几个特点：

• 栈中数据是按照"后进先出（LIFO, Last In First Out）"方式进出栈的。

• 向栈中添加/删除数据时，只能从栈顶进行操作。

栈通常包括的三种操作：push、peek、pop

push : 向栈中添加元素
peek : 返回栈顶元素
pop : 返回并删除栈顶元素的操作

通过数组（Array）和链表（LinkedList）都可以实现栈，下面是数组实现栈的方式 :

/**
 *Java : 数组实现的栈，能存储任意类型的数据
 */

import java.lang.reflect.Array;
public class GeneralArrayStack<T> {
    private static final int DEFAULT_SIZE = 12;
    private T[] mArray;
    private int count;

    public GeneralArrayStack(Class<T> type) {
        this(type, DEFAULT_SIZE);
    }
    public GeneralArrayStack(Class<T> type, int size) {
        // 不能直接使用mArray = new T[DEFAULT_SIZE];
        mArray = (T[]) Array.newInstance(type, size);
        count = 0;
    }
    // 将val添加到栈中
    public void push(T val) {
        mArray[count++] = val;
    }
    // 返回“栈顶元素值”
    public T peek() {
        return mArray[count-1];
    }
    // 返回“栈顶元素值”，并删除“栈顶元素”
    public T pop() {
        T ret = mArray[count-1];
        count--;
        return ret;
    }
    // 返回“栈”的大小
    public int size() {
        return count;
    }
    // 返回“栈”是否为空
    public boolean isEmpty() {
        return size()==0;
    }
    // 打印“栈”
    public void PrintArrayStack() {
        if (isEmpty()) {
        System.out.printf("stack is Empty\n");
        }
        System.out.printf("stack size()=%d\n", size());
        int i=size()-1;
        while (i>=0) {
            System.out.println(mArray[i]);
            i--;
        }
    }
}

1.有效的括号（LeetCode - 20）

例如：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

输入: "()"                输出: true
输入: "()[]{}"            输出: true
输入: "([{})]"            输出: false
输入: "{[{()}]}"          输出: true

思路：初始化栈 Stack，依次处理表达式的每个括号。如果第一个括号就是右括号（或者叫闭括号），那么直接判断为非法。如果遇到左括号（开括号），我们只需将其推到栈上即可，这意味着我们将稍后处理它。接下来当我们遇到一个右括号，那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的左括号，那么我们将它从栈中弹出并继续处理。如果是左括号但是类型不同，则意味着表达式无效。最后所有的括号都处理完了，我们看栈中是否仍然有元素，还有剩余元素意味着表达式无效。一个匹配的字符串，最终栈中所有的括号都会得到匹配并出栈，所以不会有剩余元素。

方法一：

public boolean isValid(String s) {
     
        Stack<String> stack = new Stack<String>();
        for(int i = 0;i < s.length();i++){
            String word = String.valueOf(s.charAt(i));
            if("[".equals(word) ||"(".equals(word)||"{".equals(word)){
                stack.push(word);
            }else{
                if(stack.isEmpty()){
                    return false;
                }
                if(("]".equals(word) && "[".equals(stack.peek())) || ("}".equals(word) && "{".equals(stack.peek())) ||(")".equals(word) && "(".equals(stack.peek()))){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }                                                          
        return stack.isEmpty();
}

• 时间复杂度：O(n)，因为我们一次只遍历给定的字符串中的一个字符并在栈上进行 O(1) 的推入和弹出操作。

• 空间复杂度：O(n)，当我们将所有的开括号都推到栈上时以及在最糟糕的情况下，我们最终要把所有括号推到栈上。例如 ((((((((((

方法二：通过HashMap分别存入对应的括号，后面可以减少很多判断。

public boolean isValid(String s) {
        HashMap<Character, Character> mappings = new HashMap<Character, Character>();
        mappings.put(')', '(');
        mappings.put('}', '{');
        mappings.put(']', '[');

        Stack<Character> stack = new Stack<Character>();
        for(int i = 0;i < s.length();i++){
            char c = s.charAt(i);
            if(mappings.containsKey(c)){
                char topElement = stack.isEmpty() ? '#' : stack.pop();
                if(topElement != mappings.get(c)){
                    return false;
                }
            }else{
                stack.push(c);
            }
                                                                    
        }
        return stack.isEmpty();
}

时间复杂度和空间复杂度与方法一相同，只是方法二的方案更加巧妙和高效。

方法三：对字符串中相邻并且匹配的左右括号用空字符""消掉，最后判断字符串如果为空则合法

public boolean isValid(String s) {
        int length;
        do{
            length = s.length();
            s = s.replace("()","").replace("[]","").replace("{}","");
        }while(length != s.length());
        
        return s.length() == 0;
}

• 时间复杂度：O(n*n/2)，replace本身的操作是 o(n) 的，所以最坏情况下会有产生 n^2 的复杂度

• 空间复杂度：O(n)

用栈实现队列（LeetCode - 232）

思路：维护两个栈stack1和stack2，每次进行push操作都把元素放入stack1中，新元素总是入 stack1 的栈顶，同时我们会判断stack1是否为空，空的话把 stack1中压入的第一个元素赋值给作为队首元素的 front 变量。进行peek 操作时判断stack2是否为空，不为空直接进行stack2的peek操作,为空则返回stack1的front变量。进行pop 操作时判断stack2是否为空，不为空直接进行stack2的pop操作,为空则把stack1的中所有元素压入stack2栈中，这样stack2栈满足队列条件，通过stack2.pop() 将栈顶元素也就是队列的队首元素出栈。

class MyQueue {

    Stack<Integer> stack1;
    Stack<Integer> stack2;
    int front;
    
    public MyQueue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }
 
    public void push(int x) {
        if(stack1.empty()){
            front = x;
        }
        stack1.push(x);
    }

    public int pop() {
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int peek() {
        if(!stack2.empty()){
            return stack2.peek();
        }
        return front;
    }

    public boolean empty() {
        return stack1.empty() && stack2.empty();
    }
}

队列（Queue）

队列是一种线性存储结构。它的几个特点如下：

• 队列中数据是按照"先进先出（FIFO, First-In-First-Out）"方式进出队列的。

• 队列只允许在"队首"进行删除操作，而在"队尾"进行插入操作。

队列通常包括的两种操作：入队列和 出队列。

通过数组（Array）和链表（LinkedList）都可以实现队列，下面是数组实现队列的方式 :

/**
 *Java : 数组实现“队列”，只能存储int数据
 */
 
public class ArrayQueue {
    private int[] mArray;
    private int mCount;
    
    public ArrayQueue(int sz) {
        mArray = new int[sz];
        mCount = 0;
    }
    // 将val添加到队列的末尾
    public void add(int val) {
        mArray[mCount++] = val;
    }
    // 返回“队列开头元素”
    public int front() {
        return mArray[0];
    }
    // 返回“队首元素值”，并删除“队首元素”
    public int pop() {
        int ret = mArray[0];
        mCount--;
        for (int i=1; i<=mCount; i++)
            mArray[i-1] = mArray[i];
        return ret;
    }
    // 返回“栈”的大小
    public int size() {
        return mCount;
    }
    // 返回“栈”是否为空
    public boolean isEmpty() {
        return size()==0;
    }
}

用队列实现栈（LeetCode - 225）

使用队列实现栈的下列操作：

push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空

注意 : 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

【方法一】: 我们需要维护两个队列 q1 和 q2, push的时候，新元素永远从 q1 的后端入队，同时 q1 的后端也是栈的 栈顶（top）元素。pop的时候，需要把栈顶元素弹出，就是 q1 中最后入队的元素。因此我们需要维护另外一个队列 q2，这个队列用作临时存储 q1 中出队的元素。q2 中最后入队的元素将作为新的栈顶元素。接着将 q1 中最后剩下的元素出队。我们通过把 q1 和 q2 互相交换的方式来避免把 q2 中的元素往 q1 中拷贝。

private Queue<Integer> q1 = new LinkedList<>();
private Queue<Integer> q2 = new LinkedList<>();
private int top;

//push操作时间复杂度和空间复杂度都是O(1)
public void push(int x) {
    q1.add(x);
    top = x;
}

//让 q1 中的 n个元素出队，让n - 1个元素从 q2 入队，在这里 n 是栈的大小。这个过程总共产生了2n-1 //次操作，时间复杂度为 O(n)
public void pop(){
    if(q1.size() > 1){
        top = q1.remove();
        q2.add(top);
    }
    q1.remove();
    Queue<Integer> temp = q1;
    q1 = q2;
    q2 = temp;
}

【方法二】: 让每一个新元素从 q2 入队，同时把这个元素作为栈顶元素保存。当 q1 非空（也就是栈非空），我们让 q1 中所有的元素全部出队，再将出队的元素从 q2 入队。通过这样的方式，新元素（栈中的栈顶元素）将会在 q2 的前端。我们通过将 q1， q2 互相交换的方式避免把 q2 中的元素往 q1 中拷贝

//push操作时间复杂度：O(n)，q1 出队n个元素，同时入队n+1 个元素到 q2。这个过程会产生2n+1步操
//作，同时链表中插入操作和移除操作的时间复杂度为O(1)，因此时间复杂度为O(n)。空间复杂度：O(1)
public void push(int x) {
    q2.add(x);
    top = x;
    while (!q1.isEmpty()) {                
        q2.add(q1.remove());
    }
    Queue<Integer> temp = q1;
    q1 = q2;
    q2 = temp;
}

//pop操作的时间和空间复杂度都是O(1)
public void pop() {
    q1.remove();
    if (!q1.isEmpty()) {
        top = q1.peek();
    }
}

方法一和方法二的判空以及取栈顶元素的方法相同：

//判空：q1 里包含了栈中所有的元素，所以只需要检查 q1 是否为空就可以了,时间和空间复杂度都是O(1)
public boolean void isEmpty() {
    return q1.isEmpty();
}

//取栈顶元素：栈顶元素被保存在 top 变量里，每次我们 压入 或者 弹出 一个元素的时候都会随之更新这 //个变量。时间复杂度：O(1)，栈顶元素每次都是被提前计算出来的，同时只有 top 操作可以得到它的值。
//空间复杂度：O(1)
public int top() {
    return top;
}

【方法三】: 前两种方法都是用了两个队列来实现，接下来通过一个队列实现。每当入队一个新元素的时候，我们可以把队列的顺序反转过来。这样最后队列中的所有元素就达到了栈的先进后出的要求。

//时间复杂度：O(n),这个算法需要从q1中出队n个元素，同时还需要入队n个元素到q1，其中n是栈的大小。这个过程总共产生了2n+1步操作。链表中插入操作和移除操作的时间复杂度为O(1)，因此时间复杂度为 O(n)
//空间复杂度：O(1)
public void push(int x) {
    q1.add(x);
    int size = q1.size();
    while (size > 1) {
        q1.add(q1.remove());
        size--;
    }
}

//pop操作：最后一个压入的元素永远在q1的前端，我们就能在常数时间内让它出队。所以时间空间复杂的都是O(1)
public void pop() {
    q1.remove();
}

//判空：q1 中包含了栈中所有的元素，只需要检查q1 是否为空就可以
//时间和空间复杂的都是O(1)
public boolean empty() {
    return q1.isEmpty();
}

//取栈顶元素：栈顶元素永远在 q1 的前端，直接返回就可以了。时间和空间复杂的都是O(1)
public int top() {
    return q1.peek();
}

下面这个网站提供了一些常用数据结构和排序算法的时间复杂度：https://www.bigocheatsheet.com/