算法学习之栈与队列

蔚落 2022-05-14 10:23 106阅读 0赞

# 算法学习之栈与队列 #

## 一、栈 Stack ##

### 0x1 数组的子集 ###

*  栈也是一种线性结构
 *  相比数组，栈对应的操作是数组的子集
 *  只能从一端添加元素，也只能从一端取出元素
 *  这一端称为栈顶
 *  栈是一种后进先出的数据结构
    
     *  Last In First Out (LIFO)
 *  在计算机的世界里，栈拥有着不可思议的作用

![20180904170539.png][]

### 0x2 栈的应用 ###

*  无处不在的Undo操作(撤销)
 *  程序调用的系统栈  
    ![20180904171533.png][]
 *  括号匹配 - 编译器

//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
    有效字符串需满足：
    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
    注意空字符串可被认为是有效字符串。
    
    Code:
    import java.util.Stack;
    
    class Solution {
    
        public boolean isValid(String s) {
    
            Stack<Character> stack = new Stack<>();
            for(int i = 0 ; i < s.length() ; i ++){
                char c = s.charAt(i);
                if(c == '(' || c == '[' || c == '{')
                    stack.push(c);
                else{
                    if(stack.isEmpty())
                        return false;
    
                    char topChar = stack.pop();
                    if(c == ')' && topChar != '(')
                        return false;
                    if(c == ']' && topChar != '[')
                        return false;
                    if(c == '}' && topChar != '{')
                        return false;
                }
            }
            return stack.isEmpty();
        }
    
    
    //测试类：
        public static void main(String[] args) {
    
            System.out.println((new Solution()).isValid("()[]{}"));
            System.out.println((new Solution()).isValid("([)]"));
        }
    }

### 0x3 栈的实现 ###

Stack<E>
    void push(E) //入栈
    E pop()  //出栈
    E peek()  //查看
    int getSize()  //长度
    boolean isEmpty()  //是否为空

## 二、队列 Queue ##

### 0x1 站队 ###

*  队列也是一种线性结构
 *  相比数组，队列对应的操作是数组的子集
 *  只能从一端(队尾)添加元素，只能从另一端(队首)取出元素
 *  队列是一种先进先出的数据结构(先到先得) FIFO

### 0x2 队列的实现 ###

Interface Queue<E> 
    void enqueue(E) //入队
    E dequeue()   //出队
    E getFront()  //查看队首
    int getSize()  //长度
    boolean isEmpty()  //是否为空

### 0x3 数组队列 ###

public class ArrayQueue<E> implements Queue<E> {
    
        private Array<E> array;
    
        public ArrayQueue(int capacity){
            array = new Array<>(capacity);
        }
    
        public ArrayQueue(){
            array = new Array<>();
        }
    
        @Override
        public int getSize(){
            return array.getSize();
        }
    
        @Override
        public boolean isEmpty(){
            return array.isEmpty();
        }
    
        public int getCapacity(){
            return array.getCapacity();
        }
    
        @Override
        public void enqueue(E e){
            array.addLast(e);
        }
    
        @Override
        public E dequeue(){
            return array.removeFirst();
        }
    
        @Override
        public E getFront(){
            return array.getFirst();
        }
    
        @Override
        public String toString(){
            StringBuilder res = new StringBuilder();
            res.append("Queue: ");
            res.append("front [");
            for(int i = 0 ; i < array.getSize() ; i ++){
                res.append(array.get(i));
                if(i != array.getSize() - 1)
                    res.append(", ");
            }
            res.append("] tail");
            return res.toString();
        }
    
        public static void main(String[] args) {
    
            ArrayQueue<Integer> queue = new ArrayQueue<>();
            for(int i = 0 ; i < 10 ; i ++){
                queue.enqueue(i);
                System.out.println(queue);
                if(i % 3 == 2){
                    queue.dequeue();
                    System.out.println(queue);
                }
            }
        }
    }

### 0x4 循环队列 ###

数组队列的实现出队的操作的复杂度是O(n），为了使得效率更高，这里编写循环队列。底层的实现仍然是数组，此时复杂度是O(1)。

public class LoopQueue<E> implements Queue<E> {
    
        private E[] data;
        private int front, tail;
        private int size;  // 有兴趣的同学，在完成这一章后，可以思考一下：
                           // LoopQueue中不声明size，如何完成所有的逻辑？
                           // 这个问题可能会比大家想象的要难一点点：）
    
        public LoopQueue(int capacity){
            data = (E[])new Object[capacity + 1];
            front = 0;
            tail = 0;
            size = 0;
        }
    
        public LoopQueue(){
            this(10);
        }
    
        public int getCapacity(){
            return data.length - 1;
        }
    
        @Override
        public boolean isEmpty(){
            return front == tail;
        }
    
        @Override
        public int getSize(){
            return size;
        }
    
        @Override
        public void enqueue(E e){
    
            if((tail + 1) % data.length == front)
                resize(getCapacity() * 2);
    
            data[tail] = e;
            tail = (tail + 1) % data.length;
            size ++;
        }
    
        @Override
        public E dequeue(){
    
            if(isEmpty())
                throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
    
            E ret = data[front];
            data[front] = null;
            front = (front + 1) % data.length;
            size --;
            if(size == getCapacity() / 4 && getCapacity() / 2 != 0)
                resize(getCapacity() / 2);
            return ret;
        }
    
        @Override
        public E getFront(){
            if(isEmpty())
                throw new IllegalArgumentException("Queue is empty.");
            return data[front];
        }
    
        private void resize(int newCapacity){
    
            E[] newData = (E[])new Object[newCapacity + 1];
            for(int i = 0 ; i < size ; i ++)
                newData[i] = data[(i + front) % data.length];
    
            data = newData;
            front = 0;
            tail = size;
        }
    
        @Override
        public String toString(){
    
            StringBuilder res = new StringBuilder();
            res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity()));
            res.append("front [");
            for(int i = front ; i != tail ; i = (i + 1) % data.length){
                res.append(data[i]);
                if((i + 1) % data.length != tail)
                    res.append(", ");
            }
            res.append("] tail");
            return res.toString();
        }
    
        public static void main(String[] args){
    
            LoopQueue<Integer> queue = new LoopQueue<>();
            for(int i = 0 ; i < 10 ; i ++){
                queue.enqueue(i);
                System.out.println(queue);
    
                if(i % 3 == 2){
                    queue.dequeue();
                    System.out.println(queue);
                }
            }
        }
    }

[20180904170539.png]: /images/20220514/05a2e2f7279e4c9287ee9d859528a18d.png
[20180904171533.png]: /images/20220514/340401a29d8e41d6b1b600390824f82c.png