【数据结构真不难】栈与队列——五一专属|向所有热爱分享的“技术劳动者”致敬（一)

2022-05-30 97

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【数据结构真不难】栈与队列——五一专属|向所有热爱分享的“技术劳动者”致敬(一）

1.概述

比较重要，且应用广泛的两种线性结构：栈 Stack、队列 Queue。

栈和队列与线性表不同之处：栈和队列可被看成是两种操作受限的特殊线性表。

2.栈

2.1定义

栈是一个特殊的线性表，插入和删除只允许在栈顶Top(线性表的尾端)进行操作。

术语：

栈顶Top：允许进行插入和删除的一端。

栈底Bottom

入栈push：栈的插入操作。

出栈pop：栈的删除操作。微信图片_20220530205018.png

栈特点：后进先出（Last In First Out、LIFO）、先进后出（First In Last Out、FILO）。

2.2出入栈练习(卡特兰数)

需求：若将ABCD依次入栈，则出栈的序列是？（进出栈可以交替进行）

// 入栈个数 1/2/3/4
Ain Aout Bin Bout Cin Cout Din Dout --> ABCD
Ain Aout Bin Bout Cin Din Dout Cout --> ABDC
Ain Aout Bin Cin Cout Din Dout Bout --> ACDB
Ain Aout Bin Cin Cout Bout Din Dout --> ACBD
Ain Aout Bin Cin Din Dout Cout Bout --> ADCB
Ain Bin Bout Aout Cin Cout Din Dout --> BACD
Ain Bin Bout Aout Cin Din Dout Cout --> BADC
Ain Bin Bout Cin Cout Aout Din Dout --> BCAD
Ain Bin Bout Cin Cout Din Dout Aout --> BCDA
Ain Bin Bout Cin Din Dout Cout Aout --> BDCA
Ain Bin Cin Cout Din Dout Bout Aout --> CDBA
Ain Bin Cin Cout Bout Din Dout Aout --> CBDA
Ain Bin Cin Cout Bout Aout Din Dout --> CBAD
Ain Bin Cin Din Dout Cout Bout Aout --> DCBA

进出栈是最经典的卡特兰数

3.顺序栈

3.1定义

顺序栈：使用数组实现的栈。
约定：
空栈：top == 0
满栈：top == stackElem.length
长度：top
栈顶元素：stackElem[top - 1]

3.2栈类

public class SqStack {
    private Object[] stackElem;     //栈对象数组
    private int top;          //长度、下一个存储位置 等
}

3.3算法：入栈【重点】

算法1：

public void push(Object x){
    if(top == stackElem.length){
        throw new RuntimeException("栈满");
    }else{
        stackElem[top] = x;
        top++;
    }
}

算法2：

public void push(Object x){
    if(top == stackElem.length){
        throw new RuntimeException("栈满");
    }else{
        stackElem[top++] = x;
    }
}

3.4算法：出栈【重点】

微信图片_20220530205035.png

算法1：

public Object pop(){
    if(top == 0){
        return null;
    }else{
        top--;
        return statckElem[top];
    }
}

算法2：

public boolean isEmpty(){
    return top == 0;
}
public Object pop(){
    if(isEmpty()){
        return null;
    }else{
        return statckElem[--top];
    }
}

4.链栈

4.1定义

使用链式存储的栈，就是链栈。进行插入和删除操作在栈顶进行，也就是链表的尾端。
存储单元2部分组成：数据域 data 和指针域 next。
使用top栈顶指针用于指向栈尾。

4.2栈类

public class LinkStack {
    private Node top;     //栈顶指针
}

4.3算法：入栈

需求：将新结点p，压入到栈顶

public void push(Object x){
    Node p = new Node(x);
    p.next = top;
    top = p;
}

4.4算法：出栈

需求：弹出栈顶元素，需要返回数据微信图片_20220530205944.png

public Object pop(){
    if(top == null){
        return null;
    }else{
        Node p = top;
        top = top.next;
        return p.data;
    }
}