[数据结构与算法]数据结构之栈和队列

1. 栈

栈是一种特殊的线性表，只能够在一端进行操作。特点是后进先出LIFO。
每加入一个元素会放在栈顶，将之前的元素往栈顶的位置移动。
出栈的元素也只能是栈顶元素。

1.1 接口设计

1. int size()：返回元素数量；
2. boolean isEmpty()：栈是否为空；
3. void push(E e)：元素入栈；
4. E pop()：元素出栈；
5. E top()：返回栈顶元素。

1.2 方法实现

栈中的方法实际上可以直接运用ArrayList或者是LinkedList中的方法，这里没有使用。

1.2.1 成员变量

这里的成员变量跟ArrayList一样。

	private E[] elements;

    private int size;

    // 默认容量
    private static final int DEFAULT_CAPACITY = 10;

1.2.2 方法实现

    /**
     * 入栈
     * @param e
     */
    public void push(E e){
        if (size >= elements.length){
            ensureCapacity(size + 1);
        }
        elements[size++] = e;
    }

	 /**
     * 出栈
     * @return
     * @throws IndexOutOfBoundsException
     */
    public E pop() throws IndexOutOfBoundsException {
        if (size < 1){
            throw new IndexOutOfBoundsException("Size:" + size);
        }
        return elements[--size];
    }

    /**
     * 查看栈顶元素
     * @return
     */
    public E top(){
        if (size < 1){
            throw new IndexOutOfBoundsException("Size:" + size);
        }
        return elements[size - 1];
    }

    /**
     * 保证要有capacity的容量
     * @param capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) {
            return;
        }
        // 新容量为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
    }

1.3 力扣题目

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
https://leetcode-cn.com/problems/valid-parentheses/

整体思路就是：将左括号的值加入到栈中，如果是右括号就弹出栈顶判断是否与左括号符合。

	public static boolean isValid(String s) {
        if (s == null || s.length() % 2 != 0 || s.length() == 0) {
            return false;
        }
        int len = s.length();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c == '(' || c== '[' || c == '{' ){
                stack.push(c);
            }else {
                if (stack.isEmpty()) {
                    return false;
                }
                char left = stack.pop();
                if (left == '{' && c!= '}'){
                    return false;
                }
                if (left == '[' && c!= ']'){
                    return false;
                }
                if (left == '(' && c!= ')'){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

2. 队列

队列是一种特殊的线性表，只能在头尾两端进行操作。
只能从队尾添加元素，在对头移除元素。
先进先出原则，FIFO

2.2 LinkedList实现队列

因为栈中队列中只能对头元素和尾元素进行操作，所以使用双向链表来实现是最合适的，这里直接选用Java官方的LinkedList来实现队列。Java官方的Queue接口也是由LinedList来实现的。

接口实现：

1. int size()：队中元素数量；
2. boolean isEmpty()：队列是否为空；
3. void enQueue(E e)：入队；
4. E deQueue()：出队；
5. E front()：返回队头元素；
6. void clear()：清空。

 /**
 * @Description 用双向链表实现队列
 * @date 2022/4/7 15:46
 */
public class Queue<E> {

    LinkedList<E> list = new LinkedList<>();

    /**
     * 返回队列元素数量
     * @return
     */
    public int size(){
        return list.size();
    }

    /**
     * 判断队列是否为空
     * @return
     */
    public boolean isEmpty(){
        return list.isEmpty();
    }

    /**
     * 入队
     * @param e
     */
    public void enQueue(E e){
        list.add(e);
    }

    /**
     * 出队
     * @return
     */
    public E deQueue(){
        return list.remove(0);
    }

    /**
     * 查看队中最前方元素
     * @return
     */
    public E front(){
        return list.get(0);
    }

    /**
     * 清空队列
     */
    public void clear(){
        list.clear();
    }
}

2.3 Stack实现队列

因为栈是在一端进行操作，而队列是在两端进行操作的，因此可以使用两个栈来实现队列。
相同与力扣题目：用栈实现队列。

实现思路：

1. 准备两个栈：inStack和outStack；
2. 入队时将元素添加到inStack中；
3. 出队时如果outStack为空，就将inStack中的元素加入到outStack中，然后outStack弹出；如果outStack不为空，直接弹出。

    private Stack<Integer> inStack;
    private Stack<Integer> outStack;

    public StackQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }


    /**
     * 入队
     * @param x
     */
    public void push(int x) {
        inStack.push(x);
    }

    /**
     * 出队
     * @return
     */
    public int pop() {
        checkStack();
        return outStack.pop();
    }

    /**
     * 查看队头元素
     * @return
     */
    public int peek() {
        checkStack();
        return outStack.peek();
    }

    /**
     * 队列是否为空
     * @return
     */
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    /**
     * 检查outStack是否有元素。
     */
    private void checkStack(){
        if (outStack.isEmpty()){
            while (!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
        }
    }

2.3 双端队列

双端队列是能在头尾两端进行添加、删除的队列。Java官方中也是使用LinkedList来实现的Deque接口。

接口实现：

1. int size()：队中元素数量；
2. boolean isEmpty()：队列是否为空；
3. void enQueueFront(E e)：从队头入队；
4. void enQueueRear(E e)：从队尾入队；
5. E deQueueRear()：从队尾出队；
6. E deQueueFront()：从队头出队；
7. E front()：返回队头元素；
8. E rear()：返回队尾元素；
9. void clear()：清空。

/**
 * @Description 双端队列实现
 * @date 2022/4/8 9:05
 */
public class Deque<E> {

    LinkedList<E> list = new LinkedList<>();

    /**
     * 返回队列元素数量
     * @return
     */
    public int size(){
        return list.size();
    }

    /**
     * 判断队列是否为空
     * @return
     */
    public boolean isEmpty(){
        return list.isEmpty();
    }

    /**
     * 队尾入队
     * @param e
     */
    public void enQueueRear(E e){
        list.add(e);
    }

    /**
     * 队头入队
     * @param e
     */
    public void enQueueFront(E e){
        list.add(0,e);
    }

    /**
     * 队尾出队
     * @return
     */
    public E deQueueRear(){
        return list.remove(list.size() - 1);
    }

    /**
     * 队头出队
     * @return
     */
    public E deQueueFront(){
        return list.remove(0);
    }

    /**
     * 查看队中头元素
     * @return
     */
    public E front(){
        return list.get(0);
    }

    /**
     * 查看队中尾元素
     * @return
     */
    public E rear(){
        return list.get(list.size() - 1);
    }

    /**
     * 清空队列
     */
    public void clear(){
        list.clear();
    }
}

2.4 循环队列

其实就是将一个模拟成环形，加入一个就在尾端新增一个元素，出队一个就修改front的指向。实现环形

要加入节点：将新节点放到尾部

删除节点：front指向下一个元素

1. int size()：队中元素数量；
2. boolean isEmpty()：队列是否为空；
3. void enQueue(E e)：入队；
4. E deQueue()：出队；
5. E front()：返回队头元素；
6. void clear()：清空。

• 成员变量&构造方法：

    // 队列长度
    private int size;

    // 存储元素数组
    private E[] elements;

    // 存储队头下标
    private int front;

    // 默认容量
    private static final int DEFAULT_CAPACITY = 10;

    public CircleQueue(){
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

• void enQueue(E e)：因为如果时的元素放到队的尾部，直接使用front + size在对数组长度进行取模可以实现。

	/**
     * 入队
     * @param e
     */
    public void enQueue(E e){
        ensureCapacity(size + 1);
        elements[(front + size) % elements.length] = e;
        size++;
    }

• E deQueue()：出队时只需要将front下标的数组元素返回，并且赋值为空，再将front指向下一元素，为防止下标溢出所以需要对长度取模。

	/**
     * 出队
     * @return
     */
    public E deQueue(){
        E e = elements[front];
        elements[front] = null;
        front = (front + 1) % elements.length;
        size--;
        return e;
    }

• 扩容方法：直接将front指向数组中第一个元素，剩余元素按顺序放到其后面。
  

	/**
     * 保证要有capacity的容量
     * @param capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity){
            return;
        }
        // 变成原先容量的 1.5 倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[capacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[(i + front) % elements.length];
        }
        elements = newElements;
        front = 0;
    }

2.5 双端循环队列

可以从两端进行添加和删除的循环队列。

接口实现：

1. int size()：队中元素数量；
2. boolean isEmpty()：队列是否为空；
3. void enQueueFront(E e)：从队头入队；
4. void enQueueRear(E e)：从队尾入队；
5. E deQueueRear()：从队尾出队；
6. E deQueueFront()：从队头出队；
7. E front()：返回队头元素；
8. E rear()：返回队尾元素；
9. void clear()：清空。

因为从队尾入队和从队头出队等没有变化，这里直接就不写了。

• 从队头入队：

    /**
     * 从头部入队
     * @param e
     */
    public void enQueueFront(E e){
        ensureCapacity(size + 1);
        front = getIndex(-1);
        elements[front] = e;
        size++;
    }

• 从队尾出队：

	/**
     * 从尾部出队
     * @return
     */
    public E deQueueRear(){
        int rear = getIndex(size - 1);
        E e = elements[rear];
        elements[rear] = null;
        size--;
        return e;
    }

• 获取队尾元素：

  	/**
     * 查看队中尾部元素
     * @return
     */
    public E rear(){
        return elements[getIndex(size - 1)];
    }

• getIndex()：根据传入的索引，计算出新的索引值：因为使用取模运算%时CPU消耗内存过大，因此这里使用三元运算符来代替。循环队列也可以修改。

    /**
     * 针对front和index进行取模运算
     * @param index
     * @return
     */
    private int getIndex(int index){
        index += front;
        // 如果出现 -1 的情况，直接加上数组的长度，变成数组的最后一个元素。
        if (index < 0){
            return index + elements.length;
        }
        return index - (index >= elements.length ? elements.length : 0);
    }

• 清空队列：这里的清空需要使用getIndex()方法转换索引才能实现真正的清空。

    /**
     * 清空队列
     */
    public void clear(){
        for (int i = 0; i < elements.length; i++) {
            elements[getIndex(i)] = null;
        }
        size = 0;
        front = 0;
        elements = null;
    }

《新程序员》：云原生和全面数字化实践

50位技术专家共同创作，文字、视频、音频交互阅读