数据结构小记｜Wavy's blog

【声明】图源：牛客网

栈和队列的基本性质

栈：先进后出
队列：先进先出
栈和队列在实现结构上可以有数组和链表两种形式
- 数组结构实现较容易
- 用链表结构较复杂，因为牵扯很多指针操作
栈和队列的基本操作，时间复杂度O(1)
双端队列结构为首尾都可以压入和弹出元素
优先级队列根据元素的优先级值，决定元素的弹出顺序。优先级队列的结构为堆结构，并不是线性结构
两种相关的遍历方式：深度优先遍历(DFS)、宽度优先遍历(BFS)
- 深度优先遍历可以用栈实现
深度优先遍历的结果：1 2 4 5 3 6 7
- 宽度优先遍历可以用队列实现

宽度优先遍历的结果：1 2 3 4 5 6 7
平时使用的递归函数实际上用到了系统提供的函数栈，所以递归的处理过程可以看作时函数入栈出栈的过程。所以用递归函数实现的过程都可以用非递归的方式实现。

栈的基本操作

pop操作
top或peek操作
push操作
size操作

队列的基本操作

与栈操作不同的是，push操作为在队尾加入元素
pop操作是从队列头部弹出一个元素

经典案例

案例一

题目

可查询最值的栈

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作getmin

要求：

1、pop、push、getMin操作的时间复杂度都是O(1)

2、设计的栈类型可以使用现成的栈结构

分析

定义两个栈：

StackData用来保存当前栈中的元素，功能与正常的栈无异

StackMin用来保存每次入栈的最小值

方法一

只有当前数小于等于StackMin的栈顶时，该数放入StackMin。
弹出时，先在StackData中弹出栈顶元素value，然后比较StackMin栈顶元素与value哪个更小。
- 当value=StackMin的栈顶元素时，StackMin弹出当前的栈顶元素。
- 当value>StackMin的栈顶元素时，StackMin不弹出当前的栈顶元素。

实现

import java.util.Stack;

public class Solution {

    Stack<Integer> stackData = new Stack<Integer>();
    Stack<Integer> stackMin = new Stack<Integer>();

    public void push(int node) {
        stackData.push(node);
        if(stackMin.isEmpty() || node < stackMin.peek())
            stackMin.push(node);
    }

    public void pop() {
        if(stackData.pop()==stackMin.peek())
            stackMin.pop();
    }

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

    public int min() {
        return stackMin.peek();
    }
}

方法二

当前数和StackMin栈顶元素比较，较小的压入StackMin。
弹出时，StackData和StackMin同步弹出。

实现

import java.util.Stack;

public class Solution {

    Stack<Integer> stackData = new Stack<Integer>();
    Stack<Integer> stackMin = new Stack<Integer>();

    public void push(int node) {
        stackData.push(node);
        if(stackMin.isEmpty() || node < stackMin.peek())
            stackMin.push(node);
        else
            stackMin.push(stackMin.peek());
    }

    public void pop() {
        stackData.pop();
        stackMin.pop();
    }

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

    public int min() {
        return stackMin.peek();
    }
}

总结

方法一和方法二都是利用第二个栈StackMin来保存每一步的最小值。
两者时间复杂度都为O(1)，空间复杂度都为O(n)。
区别：前者StackMin压入时稍省空间，弹出时略费时间。后者StackMin压入时稍费空间，弹出时略省时间。

案例二

题目

双栈队列

编写一个类，只能用两个栈结构实现队列，支持队列的基本操作（add、poll、peek）

分析

定义两个栈：

StackPush只往此栈中压入数据

StackPop作为弹出栈，只从这个栈中拿数据

将StackPush中的数据倒入StackPop中，就将数据的顺序反过来了。此时从StackPop栈顶取元素就相当于从队列首部取元素。

注意

如果StackPush要往StackPop中倒入数据，那么必须保证要把StackPush中所有数据一次性倒完。
- 错误情况举例
如果StackPop中有数据，则不能发生倒数据的行为。
- 错误情况举例
从StackPush倒向StackPop这个行为，可以选择在很多方法中包含该逻辑，但要保证倒入数据的两个注意点不被违反。

实现

import java.util.ArrayList;
import java.util.Stack;

/**
 * 编写一个类,只能用两个栈结构实现队列,支持队列的基本操作(push，pop)。
 * 给定一个操作序列ope及它的长度n，其中元素为正数代表push操作，为0代表pop操作，
 * 保证操作序列合法且一定含pop操作，请返回pop的结果序列。
 *
 * 测试样例：
 * [1,2,3,0,4,0],6
 * 返回：[1,2]
 */
class Queue{
    Stack<Integer> stackPush = new Stack<Integer>();
    Stack<Integer> stackPop = new Stack<Integer>();

    public void push(int node){
        stackPush.push(node);
    }
    public int pop(){
        if(stackPop.isEmpty())
            while(!stackPush.isEmpty()){
                stackPop.push(stackPush.pop());
            }
        return stackPop.pop();
    }
}
public class TwoStack {

    public static int[] twoStack(int[] ope, int n) {
        Queue queue = new Queue();
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        for(int num:ope){
            if(num > 0){
                queue.push(num);
            }else if(num == 0){
                tmp.add(queue.pop());
            }
        }
        int[] res = new int[tmp.size()];
        for(int i=0;i<tmp.size();i++){
            res[i] = tmp.get(i);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] ope = {1,2,3,0,4,0};
        int n = 6;
        int[] res = twoStack(ope,n);
        for(int num:res){
            System.out.print(num+" ");
        }
    }
}

案例三

题目

栈的反转

实现一个栈的逆序，但是只能用递归函数和这个栈本身的操作来实现，而不能自己申请另外的数据结构

分析

代码一

递归函数：移除栈底元素并返回
演示过程
实现

public int get(Stack<Integer> stack){
    int result = stack.pop();
    if(stack.isEmpty()){
        return result;
    }else{
        int last = get(stack);
        stack.push(result);
        return last;
    }
}

代码二

递归函数：将栈中元素逆序
演示过程
实现

public void reverse(Stack<Integer> stack){
    if(stack.isEmpty()){
        return;
    }
    int i = get(stack);
    reverse(stack);
    stack.push(i);
}

实现

方法一

public int[] reverseStack(int[] A, int n) {
    if(n == 0)
        return null;
    int node = A[n-1];
    reverseStack(A,n-1);
    A[A.length-n] = node;
    return A;
}

方法二

/**
 * 实现一个栈的逆序，但是只能用递归函数和这个栈本身的pop操作来实现，而不能自己申请另外的数据结构。
 * 给定一个整数数组A即为给定的栈，同时给定它的大小n，请返回逆序后的栈。
 * 测试样例：
 * [4,3,2,1],4
 * 返回：[1,2,3,4]
 */
public class StackReverse {
    public static int[] reverseStack(int[] A, int n) {
        int index = 0; //表示初始栈顶标记
        reverse(A, index, n);
        return A;
    }

    private static void reverse(int[] A, int index, int n) { //栈逆序
        if(index == n-1) {
            return;
        }

        int temp = getLast(A, index, n);
        index++;
        reverse(A, index, n);
        index--;
        A[index] = temp;
    }

    private static int getLast(int[] A, int index, int n) { //得到栈底元素
        if(index == n-1) {
            return A[index];
        }

        int temp = A[index];
        index++;
        int last = getLast(A, index, n);
        A[index] = temp;

        return last;
    }

    public static void main(String[] args) {
        int[] A = {4,3,2,1};
        int n = 4;
        A = reverseStack(A,n);
        for(int a:A){
            System.out.print(a+" ");
        }
    }
}

案例四

题目

双栈排序

一个栈中元素类型为整型，现在想将该栈从顶到底按从大到小排序，只许申请一个栈，除此之外可以申请新的变量，但不能申请额外的数据结构。如何完成排序？

分析

将想要排序的栈记为Stack，申请的辅助栈记为help。
在Stack上执行pop()操作，弹出的元素记为current。
- 如果current≤help栈顶元素，则将current直接压入help中；
- 如果current>help栈顶元素，则将help元素逐个弹出并重新压回Stack中，直到current≤help栈顶元素
一直执行上述操作，直到Stack中的元素都压入到help中。
最后将help中的元素再压回到Stack中就完成排序了。

演示

实现

public ArrayList<Integer> twoStacksSort(int[] numbers) {
    Stack<Integer> stack = new Stack<Integer>();// 原栈
    Stack<Integer> help = new Stack<Integer>(); // 辅助栈

    // 构建栈
    for(int num:numbers){
        stack.push(num);
    }

    while (!stack.isEmpty()){
        int current = stack.pop();
        if(help.isEmpty()) {
            help.push(current);
        }
        else{
            if(current <= help.peek()) {
                help.push(current);
            }
            else{
                // 注意这个地方要判断help是否为空，否则会抛出异常！！！
                while(!help.isEmpty() && current>help.peek()){
                    stack.push(help.pop());
                }
                help.push(current);
            }
        }
    }
    while (!help.isEmpty())
        stack.push(help.pop());
    ArrayList<Integer> res = new ArrayList<Integer>();
    while (!stack.isEmpty())
        res.add(stack.pop());
    return res;
}

案例五

题目

滑动窗口问题

有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。返回一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值。以数组为[4,3,5,4,3,3,6,7]，w=3为例。因为第一个窗口[4,3,5]的最大值为5，第二个窗口[3,5,4]的最大值为5，第三个窗口[5,4,3]的最大值为5，第四个窗口[4,3,3]的最大值为4，第五个窗口[3,3,6]的最大值为6，第六个窗口[3,6,7]的最大值为7。所以最终返回[5,5,5,4,6,7]。

分析

如果数组长度为N，窗口大小为w，普通解法的时间复杂度为O(N*w)，即每次对一个窗口遍历其中的w个数，选出最大值。

最优解时间复杂度O(N)。利用双端队列来实现最大值的更新，思路如下：

定义双端队列qmax={}，双端队列存放着数组中的下标值
假设当前数为arr[i]，放入规则如下：
- 如果qmax为空，直接把下标i放入qmax中。
- 如果qmax不为空，取出当前qmax队尾存放的下标j：
  - 如果arr[j]>arr[i]，直接把下标i放进qmax的队尾。
  - 如果arr[j]≤arr[i]，则一直从qmax的队尾弹出下标，直到某个下标在qmax中对应的值大于arr[i]，把i放入qmax队尾。
- 如果qmax队头的下标等于i-w，弹出qmax当前队头下标。
演示过程：

上述过程中，每个下标值最多进qmax一次，出qmax一次，所以整个过程中进出双端队列的时间复杂度为O(N)。

实现

import java.util.Deque;
import java.util.LinkedList;

public class SlideWindow {
    public int[] slide(int[] arr, int n, int w) {
        if(arr == null || n < w || w<1)
            return null;
        int[] res = new int[n-w+1];
        // 定义双端队列
        Deque<Integer> deque = new LinkedList<Integer>();
        int index=0;
        for(int i=0;i<n;i++){
            while (!deque.isEmpty() && arr[deque.peekLast()]<=arr[i])
                deque.pollLast();
            deque.addLast(i);
            // 队头已经超过滑动窗口范围
            if(deque.peekFirst() == i-w)
                deque.pollFirst();
            // 判断队列中最大值什么时候加入到结果数组
            if(i >= w-1)
                res[index++] = arr[deque.peekFirst()];
        }
        return res;
    }
}

案例六

题目

数组变树问题

给定一个没有重复元素的数组arr，写出生成这个数组的MaxTree的函数。要求如果数组长度为N，则时间复杂度为O(N)，额外空间复杂度为O(N)。MaxTree的概念如下：

1、MaxTree是一棵二叉树，数组的每一个值对应一个二叉树节点。

2、包括MaxTree树在内且在其中的每一棵子树上，值最大的节点都是树的头。

分析

建立树的规则：

每个数的父节点是它左边第一个比它大的数和它右边第一个比它大的数中较小的那一个
若两边都不存在比它大的数，即这个数是整个数组的最大值，那么这个数就作为整个MaxTree的树根
构建过程

证明该方法的正确性：

该方法可以生成一棵树，而不是森林。

证明

在数组中所有的数都不同，而一个较小的数肯定会以一个比它大的数作为父节点。那么最终所有的数向上都会找到这个数组的最大值。所以它们会有一个共同的头部。这样肯定是一棵树，而不是多棵树。

生成的这一棵树是二叉树，而不是多叉树。

证明

任何一个数在单独一侧，孩子的数量都不超过一个。
......A......K1......K2
A>K1，且A>K2
情况①：
假设K1<K2
根据A>K2，有K1<K2<A
所以根据上述方法，K1不可能以A为父节点

情况②：
假设K2<K1
根据A>K1，有K2<K1<A
所以根据上述方法，K2不可能以A为父节点

总之，K1和K2肯定有一个不是A的孩子，A在单独一侧不可能有超过一个孩子节点的情况，最多只能有一个。

如何更快得到每一个数左边和右边第一个比它大的数：

实现

import java.util.Stack;

public class MaxTree {
    public int[] buildMaxTree(int[] A, int n) {
        if(A == null || n<=0)
            return null;
        int[] res = new int[n];
        Stack<Integer> stack = new Stack<Integer>();
        // 找到当前节点左侧大于该节点值的下标
        for(int i=0;i<n;i++){
            while(!stack.isEmpty() && A[stack.peek()]<A[i])
                stack.pop();
            if(stack.isEmpty())
                res[i] = -1;
            else
                res[i] = stack.peek();
            stack.push(i);
        }
        stack.clear();
        // 找到当前节点左右两边比它大的值中较小的那一个
        for(int i=n-1;i>=0;i--){
            while(!stack.isEmpty() && A[stack.peek()]<A[i])
                stack.pop();
            // stack为空时，当前右侧没有比它大的值，直接采用左边找到比它大值的下标。
            // stack非空时，如果左边没有较大值，或者右边找到更小值，更新下标。
            if(!stack.isEmpty() && (res[i]==-1 || A[res[i]]>A[stack.peek()]))
                res[i] = stack.peek();
            stack.push(i);
        }
        return res;
    }
}

数据结构小记

队列和栈

栈和队列的基本性质

栈的基本操作

队列的基本操作

经典案例

案例一

题目

分析

方法一

方法二

总结

案例二

题目

分析

注意

案例三

题目

分析

代码一

代码二

实现

案例四

题目

分析

演示

实现

案例五

题目

分析

实现

案例六

题目

分析

实现

FEATURED TAGS