【数据结构】栈与队列（一）

2022-09-22 191

版权

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

简介： 栈与队列

3.栈与队列

3.1 概述

比较重要，且应用广泛的两种线性结构：栈 Stack、队列 Queue。
栈和队列与线性表不同之处：栈和队列可被看成是两种操作受限的特殊线性表。

3.2 栈

3.2.1 定义

栈是一个特殊的线性表，插入和删除只允许在栈顶Top(线性表的尾端)进行操作。
术语：
栈顶Top：允许进行插入和删除的一端。
栈底Bottom
入栈push：栈的插入操作。
出栈pop：栈的删除操作。

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

3.2.2 出入栈练习（卡特兰数）

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

// 入栈个数 1/2/3/4AinAoutBinBoutCinCoutDinDout-->ABCDAinAoutBinBoutCinDinDoutCout-->ABDCAinAoutBinCinCoutDinDoutBout-->ACDBAinAoutBinCinCoutBoutDinDout-->ACBDAinAoutBinCinDinDoutCoutBout-->ADCBAinBinBoutAoutCinCoutDinDout-->BACDAinBinBoutAoutCinDinDoutCout-->BADCAinBinBoutCinCoutAoutDinDout-->BCADAinBinBoutCinCoutDinDoutAout-->BCDAAinBinBoutCinDinDoutCoutAout-->BDCAAinBinCinCoutDinDoutBoutAout-->CDBAAinBinCinCoutBoutDinDoutAout-->CBDAAinBinCinCoutBoutAoutDinDout-->CBADAinBinCinDinDoutCoutBoutAout-->DCBA

3.3 顺序栈

3.3.1 定义

顺序栈：使用数组实现的栈。
约定：

空栈：top == 0
满栈：top == stackElem.length
长度：top
栈顶元素：stackElem[top - 1]

3.3.2 栈类

publicclassSqStack {
privateObject[] stackElem;         //栈对象数组privateinttop;                    //长度、下一个存储位置 等}

3.3.3 算法：入栈【重点】

算法1：publicvoidpush(Objectx) {
if(top==stackElem.length) {           //栈满thrownewRuntimeException("栈满");
    } else {
stackElem[top] =x;
top++;
    }
}
算法2：publicvoidpush(Objectx) {
if(top==stackElem.length) {           //栈满thrownewRuntimeException("栈满");
    } else {
stackElem[top++] =x;
    }
}

3.3.4 算法：出栈【重点】

算法1：publicObjectpop() {
if(top==0) {
returnnull;            //空栈    } else {
top--;
returnstackElem[top];
    }
}
算法2：publicbooleanisEmpty() {      //是否为空returntop==0;
}
publicObjectpop() {
if(isEmpty()) {
returnnull;            //空栈    } else {
returnstackElem[--top];
    }
}

3.4 链栈

3.4.1 定义

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

3.4.2 栈类

public class LinkStack {

private Node top; //栈顶指针

}

3.4.3 算法：入栈

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

publicvoidpush(Objectx) {
Nodep=newNode(x);       // 创建新结点pp.next=top;               // 1.p的指针域指向栈顶元素top=p;                    // 2.栈顶指针top指向新结点p}

3.4.4 算法：出栈

需求：弹出栈顶元素，需要返回数据

publicObjectpop() {
if(top==null) {           //空栈 isEmpty()returnnull; 
    } else {
Nodep=top;           // 1 存放栈顶元素top=top.next;         // 2 将top指向栈顶的下一个元素returnp.data;          // 3 返回栈顶元素数据    }
}