算法

堆栈和队列

Posted by 令德湖周杰伦 on 02-22，2024

1. 定义和特性

1.1 堆栈

1.1.1 定义

堆栈（stack）简称为栈，它是一种只允许在表的一端进行操作插入和删除操作的的线性表，允许操作的一端称为栈顶，另一段称为栈底，当表中没有元素时，称之为空栈。
栈的插入操作简称为入栈或出栈，删除操作简称为出栈或退栈

1.1.2 特性

根据栈的定义，每次删除的元素总是栈中当前的栈顶元素，即此前最后进入的栈的元素。而最先进入的栈的元素一定在栈底，最后进入的元素一定在栈顶。也就是后进先出（Last In First Out,LIFO）原则

若n个元素的进栈顺序为1，2，3，....n, 那么有多少种可能的输出序列：
答案：(2n)! / ((n+1)(n!)^2)

1.2 队列

1.2.1 定义

队列（queue）简称，简称为队，它是一种允许在表的一端进行插入操作，而在表的另一段进行删除操作的线性表，允许进入插入的一端称为队尾，允许删除操作的的一端称为队头，没有元素的队列称为空队。
队列的插入操作简称为入队，删除操作简称为出队。

1.2.2 特性

根据定义，先进入队列的元素，在队头会先被删除掉，反映的是“先来先服务”的处理原则，也就是元素进入队列或者推出队列是按照先进先出（First In First Out,FIFO）原则

2. 数据结构

2.1 栈

2.1.1 顺序存储结构

底层使用数组来实现arr[0,1...n-1]代表有n个元素的栈，由于栈是一个动态结构，而数组是一个静态结构，所以存在可能溢出（overflow）的问题，所以就需要进行判断和扩容的操作。

java中栈Stack，是在Vector上实现了“后进先出”的特性，所以底层就是数组实现的。

public class Stack<E> extends Vector<E> {
   
    public Stack() {
    }

    /**
     * 向栈顶压入一个项
     */
    public E push(E item) {
        addElement(item);
        return item;
    }

    /**
     * 移走栈顶对象，将该对象作为函数值返回
     */
    public synchronized E pop() {
        E obj;
        int len = size();
        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

    /**
     * 查找栈顶对象，而不从栈中移走。
     */
    public synchronized E peek() {
        int len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

    /**
     * 测试栈是否为空
     */
    public boolean empty() {
        return size() == 0;
    }

    /**
     * 返回栈中对象的位置，从1开始。
     */
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);

        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }
}

2.1.2 链式存储结构

底层使用线性链表来实现，对于链表来说，向头部或者尾部添加和删除元素的时间复杂度相同，所以向头部或者尾部操作时间复杂度是相同的，都是O(1)级别的


public void push(E e) {
    list.addFirst(e);
}

public E pop() {
    return list.removeFirst();
}

2.2 队列

2.2.1 顺序存储结构

底层使用数组来实现arr[0,1...n-1]代表有n个元素的的队列，还需使用head和tail 两个变量来记录队头元素和队尾元素的位置，由于栈是一个动态结构，而数组是一个静态结构，所以也需要进行判断和扩容的操作。

java中 Deque 接口是（Double Ended Queue） 的缩写，即双端队列。Deque 继承 Queue 接口，并扩展支持在队列的两端插入和删除元素。
其中：ArrayDeque是底层是使用数组来实现的。

补充ArrayDeque的源码

2.2.2 链式存储结构

底层使用线性链表来实现队列

java中LinkedList 实现Deque接口，并通过链表来实现。

简单补充LinkedList源码

3. 应用

3.1 用栈实现队列

思路：

  1. 2个栈，一个接受数据栈，一个吐出数据栈
  2. 每次push到接受数据栈后，都需要进行从接受数据栈 【倒dao】 吐出数据栈的操作
  3. 每次从吐出数据栈pop之前，都需要进行先从接受数据栈 【倒dao】 吐出数据栈的操作，然后再pop
  4. 每次peek之前，都需要进行先从接受数据栈 【倒dao】 吐出数据栈的操作，然后再peek
  5. 倒dao操作准守2个原则：
    1. 只有 吐出数据栈 为空时才能 dao 数据
    2. 从接受数据栈dao数据时，要dao就要一次dao干净

代码：

class MyQueue2 {

    Stack<Integer> ins;
    Stack<Integer> ous;

    public MyQueue2() {
        ins = new Stack<>();
        ous = new Stack<>();
    }

    public void push(int x) {
        //先push在dao
        ins.push(x);
        dao();
    }


    public int pop() {
        //先倒在pop
        dao();
        return ous.pop();
    }

    public int peek() {
        //先倒在pop
        dao();
        return ous.peek();
    }


    private void dao(){
        //只有 吐出数据栈 为空时才能 dao 数据
        if(ous.isEmpty()){
            //要dao就要一次dao干净
            while (!ins.isEmpty()){
                ous.push(ins.pop());
            }
        }
    }

    public boolean empty() {
        return ins.isEmpty() && ous.isEmpty();
    }
}

3.2 用队列实现栈

思路：

  1. 使用2个双端队列inq,outq
  2. push时，将inq的最后元素加入到ouq的最前面，把所有inq元素按照这个原则放入到outq中
  3. pop时，从outq.pop即可
  4. peek时，从outq.peek即可

代码

class MyStack {

        ArrayDeque<Integer> inq;
        ArrayDeque<Integer> ouq;

        /** Initialize your data structure here. */
        public MyStack() {
            inq = new ArrayDeque<>();
            ouq = new ArrayDeque<>();
        }

        /** Push element x onto stack. */
        public void push(int x) {
            inq.add(x);
	    //inq的所有元素
            while(!inq.isEmpty()){
		//将inq的最后元素加入到ouq的最前面，把所有inq元素按照这个原则放入到outq中
                ouq.addFirst(inq.pollLast());
            }
        }

        /** Removes the element on top of the stack and returns that element. */
        public int pop() {
            return ouq.poll();
        }

        /** Get the top element. */
        public int top() {
            return ouq.peek();
        }

        /** Returns whether the stack is empty. */
        public boolean empty() {
            return inq.isEmpty() && ouq.isEmpty();
        }
    }

3.3 栈中元素排序

题目1：将一个栈的元素（无序的），从栈顶到底，按照从大到小顺序进行排序。要求只能额外使用一个栈，不能使用其他数据结构。

思路：

  1. 要始终保持辅助栈中的顺序：从顶到底是从小到大的，只有这样才能在最后依次出栈到原始栈时是按照从大到小顺序
  2. 从原始栈中弹出cur元素进入到辅助栈时，要看下是否小于栈顶元素，如果不是需要将辅助栈中的所有小于cur的元素重新加入到原始栈
  3. 至到为空，或者辅助栈中栈顶元素大于cur时，将cur加入到辅助栈
  4. 重复2～3操作
  5. 最后原始栈中元素为空时，将辅助栈的元素依次pop，并push到原始栈即可

题目2:
栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1

思路：

  1. stack1为数据栈，stack2为辅助栈，
  2. push时，
    1. 判断插入的元素cur是否小于栈顶元素，如果不是需要将元素放入到辅助栈
    2. 至到为空，或者栈顶元素大于cur时，将cur加入
    3. 同时将辅助栈的元素放回来, stack1就是有序的
  3. push完，始终保持push完stack1中元素时排好序的

代码

class SortedStack {
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public SortedStack() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    /**
     * push时，始终保持push完stack1中元素时排好序的
     *
     * @param val
     */
    public void push(int val) {
       if(!stack1.isEmpty()){
           sortStack(stack1, stack2, val);
       }else{
           stack1.push(val);
       }
    }


    public void pop() {
        if(!stack1.isEmpty()){
            stack1.pop();
        }
    }

    public int peek() {
        return stack1.isEmpty() ? -1 : stack1.peek();
    }

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


    private void sortStack(Stack<Integer> stack1, Stack<Integer> stack2, int cur){
        //cur是否小于栈顶元素，如果不是需要将元素放入到辅助栈
        while (cur > stack1.peek() && !stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
        //至到为空，或者栈顶元素大于cur时，将cur加入
        stack1.push(cur);
        //同时将辅助栈的元素放回来, stack1就是有序的
        while (!stack2.isEmpty()){
            stack1.push(stack2.pop());
        }
    }
}

3.4 特殊的最小栈

实现一个特殊的栈，要求在实现栈的基础操作后，再实现一个返回栈中最小元素的方法。要求：pop、push、getMin 操作是O(1)

思路：

  1. 使用2个栈，其中stack1用来实现pop和push等原生操作，使用stack2来保存当前stack1中最小元素，以此来实现getMin操作
  2. 加入cur元素时
    1. stack1 push cur，如果stack2中栈顶元素为null，代表空栈，stack2 push cur
    2. stack1 push cur，同时看stack2中栈顶元素是否大于cur，如果大于，stack2 push cur
    3. stack1 push cur，如果stack2中栈顶元素小于cur，stack2 重新push 一个栈顶元素
  3. 弹出元素时，stack1 pop ，stack2 也 pop即可

代码：

class MinStack {

    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public MinStack() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int val) {
        stack1.push(val);
        //如果stack2中栈顶元素为null，代表空栈，stack2 push cur
        if(stack2.isEmpty()){
            stack2.push(val);
        }else{
            Integer peek = stack2.peek();
            //栈顶元素是否大于cur，如果大于，stack2 push cur
            if(peek > val){
                stack2.push(val);
            }else{
                //如果stack2中栈顶元素小于cur，stack2 重新push 一个栈顶元素
                stack2.push(peek);
            }
        }
    }

    public void pop() {
        stack1.pop();
        stack2.pop();
    }

    public int top() {
        return stack1.peek();
    }

    public int getMin() {
        return stack2.peek();
    }
}
CATALOG
    FEATURED TAGS
    认知 微服务 复盘总结 机器学习原理 AI LLM 分布式 数据库 技术架构 缓存 算法 投资 上层建筑 Linux 数据库系统概论 英语经典短文 计算机网络 软件工程 编译原理 数据结构 OS Java Mysql Redis
    FRIENDS