栈

栈是一种操作受限的线性表，限定只能在表尾部进行插入和删除操作。
最大特点是 后进先出（LIFO）
表尾这一端被称之为栈顶，另一端叫栈底。
将一个新元素插入到栈中叫做 进栈 入栈或压栈。
将一个元素从栈中删除叫做 出栈。

栈.jpg

LeetCode 20 有效的括号

class Solution {
    HashMap<Character, Character> map = new HashMap<Character, Character>() {{
        put('}', '{');
        put(')', '(');
        put(']', '[');
    }};

    public boolean isValid(String s) {
        Character[] stack = new Character[100];
        int tail = -1;

        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                if (tail < 0 || stack[tail--] != map.get(s.charAt(i))) {
                    return false;
                }
            } else {
                stack[++tail] = s.charAt(i);
            }
        }
        if (tail < 0)
            return true;
        else
            return false;
    }
}

LeetCode 232 用栈实现队列

队列下篇讲

class MyQueue {

    int[] stackA = new int[100];
    int[] stackB = new int[100];
    int tailA = -1;
    int tailB = -1;

    /** Initialize your data structure here. */
    public MyQueue() {

    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        stackA[++tailA] = x;

    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (tailB < 0) {
            while (tailA >= 0) {
                stackB[++tailB] = stackA[tailA--];
            }
        }
        if (tailB < 0)
            return -1;
        return stackB[tailB--];
    }

    /** Get the front element. */
    public int peek() {
        if (tailB < 0) {
            while (tailA >= 0) {
                stackB[++tailB] = stackA[tailA--];
            }
        }
        if (tailB < 0)
            return -1;
        return stackB[tailB];
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        if (tailA < 0 && tailB < 0)
            return true;
        return false;
    }
}