栈和队列

选择题

1、一个栈的输入序列为：a，b，c，d，e，则栈的不可能输出的序列是（ ）。
A. a,b,c,d,e
B. d,e,c,b,a
C. d,c,e,a,b
D. e,d,c,b,a

2、判断一个循环队列Q（最多n个元素）为满的条件是（ ）。
A. Q->rear==Q->front
B. Q->rear==Q->front+1
C. Q->front==(Q->rear+1)%n
D. Q->front==(Q->rear-1)%n

设数组Data[n]作为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则执行入队操作的语句为( )。
A Q->rear=(Q->rear+1)%(n+1)
B Q->front=(Q->front+1)%n
C Q->rear=(Q->rear+1)%n
D Q->front=(Q->front+1)%(n+1)

3、设计一个判别表达式中括号是否配对的算法，采用（ ）数据结构最佳。
A. 顺序表
B. 链表
C. 队列
D. 栈

4、带头结点的单链表head为空的判定条件是（ ）。
A. head==NULL　
B. head->next==NULL
C. head->next!=NULL
D. head!=NULL

5、一个栈的输入序列为：1,2,3,4，则栈的不可能输出的序列是（ ）。
A. 1243
B. 2134
C. 1432
D. 4312
E. 3214

6、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0，3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）。
A. 1和5
B. 2和4
C. 4和2
D. 5和1

7、队列的插入操作是在（ ）。
A. 队尾
B. 队头
C. 队列任意位置
D. 队头元素后

8、循环队列的队头和队尾指针分别为front和rear，则判断循环队列为空的条件是（ ）。
A. front==rear
B. front==0
C. rear==0
D. front=rear+1

9、一个顺序栈S，其栈顶指针为top，则将元素e入栈的操作是（ ）。
A. *S->top=e;S->top++;
B. S->top++;*S->top=e;
C. *S->top=e
D. S->top=e;

10、表达式a*(b+c)-d的后缀表达式是（ ）。
A. abcd±　
B. abc+d-
C. abc+d-
D. -+*abcd

11、将递归算法转换成对应的非递归算法时，通常需要使用（ ）来保存中间结果。
A. 队列
B. 栈
C. 链表
D. 树

12、栈的插入和删除操作在（ ）。
A. 栈底
B. 栈顶
C. 任意位置
D. 指定位置

13、五节车厢以编号1，2，3，4，5顺序进入铁路调度站（栈），可以得到（ ）的编组。
A. 3，4，5，1，2
B. 2，4，1，3，5
C. 3，5，4，2，1
D. 1，3，5，2，4

14、判定一个顺序栈S（栈空间大小为n）为空的条件是（ ）。
A. S->top==0
B. S->top!=0
C. S->top==n
D. S->top!=n

15、在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（ ）。
A. front=front->next
B. s->next=rear;rear=s
C. rear->next=s;rear=s;
D. s->next=front;front=s;

16、一个队列的入队序列是1，2，3，4，则队列的出队序列是（ ）。
A. 1，2，3，4　
B. 4，3，2，1
C. 1，4，3，2
D. 3，4，1，2

17、依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操作，此时的队头元素是（ ）。
A. a
B. b
C. c
D. d

18、正常情况下，删除非空的顺序存储结构的堆栈的栈顶元素，栈顶指针top的变化是（ ）。
A. top不变
B. top=0
C. top=top+1
D. top=top-1

19、判断一个循环队列Q（空间大小为M）为空的条件是（ ）。
A. Q->front==Q->rear
B. Q->rear-Q->front-1==M
C. Q->front+1=Q->rear
D. Q->rear+1=Q->front

20、设计一个判别表达式中左右括号是否配对出现的算法，采用（ ）数据结构最佳。
A. 线性表的顺序存储结构
B. 队列
C. 栈
D. 线性表的链式存储结构

21、当用大小为N的数组存储顺序循环队列时，该队列的最大长度为（ ）。
A. N　
B. N+1
C. N-1
D. N-2

22、队列的删除操作是在（ ）。
A. 队首　
B. 队尾
C. 队前
D. 队后

23、若让元素1，2，3依次进栈，则出栈次序不可能是（ ）。
A. 3，2，1　
B. 2，1，3
C. 3，1，2
D. 1，3，2

24、循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（ ）。
A. (rear-front+m)%m
B. rear-front+1
C. rear-front-1
D. rear-front

循环队列是空队列的条件是( )。
A Q->rear= =Q->front
B （Q->rear+1）%maxsize= =Q->front
C Q->rear= =0
D Q->front= =0

25、在解决计算机主机和打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（ ）结构。
A. 堆栈
B. 队列
C. 数组
D. 线性表

26、栈和队列都是（ ）。
A. 链式存储的线性结构
B. 链式存储的非线性结构
C. 限制存取点的线性结构
D. 限制存取点的非线性结构

27、在一个链队列中，假定front和rear分别为队头指针和队尾指针，删除一个结点的操作是（ ）。
A. front=front->next
B. rear= rear->next
C. rear->next=front
D. front->next=rear

28、队和栈的主要区别是（ ）。
A. 逻辑结构不同
B. 存储结构不同
C. 所包含的运算个数不同
D. 限定插入和删除的位置不同

在作退栈运算时应先判别栈是否( )。
A 空
B 满
C 上溢
D 下溢

在作进栈运算时，应先判别栈是否( )。
A 空
B 满
C 上溢
D 下溢

若栈采用顺序存储方式存储，现两栈共享空间V[1…m]，top[1]、top[2]分别代表第1和第2个栈的栈顶，栈1的底在V[1]，栈2的底在V[m]，则栈满的条件是( )。
A |top[2]－top[1]|＝0
B top[1]＋1＝top[2]
C top[1]＋top[2]＝m
D top[1]＝top[2]

一个队列的入列序列是1234，则队列的输出序列是( )。
A 4321
B 1234
C．1432
D 3241

以数组Q[0,…,m-1]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是( )。
A rear-qulen
B rear-qulen+m
C m-qulen
D 1+(rear+m-qulen)%m

已知队列(4,41,5,7,18,26,15)，第一个进入队列的元素是4，则第5个出队列的元素是( )。
A 5
B 41
C 18
D 7

栈结构通常采用的两种存储结构是( )
A 顺序存储结构和链式存储结构
B 散列方式和索引方式
C 链表存储结构和数组
D 线性存储结构和非线性存储结构

设长度为n的链队列单循环链表表示，若只设头指针，则入队操作的时间复杂度为( )
A O(1)
B O(log2n)
C O(n)
D O(n2)

在栈中，存取数据的原则是( )
A 先进先出
B 先进后出
C 后进后出
D 随意进出

在栈中，出栈操作的时间复杂度是( )
A O(1)
B O(log2n)
C O(n)
D O(n2)

在顺序栈中删除一个元素，至少要移动( )元素。
A 0
B 1
C n/2
D n

插入和删除只能在一端进行的线性表，称为( )
A 队列
B 循环队列
C 栈
D 循环栈

表示一个栈ST(最多元素为m0)为栈空的条件是( )。
A ST->top!=0
B ST->top==0

C ST->top!=m0
D ST->top==m0

最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是( )
A (rear+1)%n==front
B rear==front
C rear+1==front
D (rear-l)%n==front

链栈与顺序栈相比，比较明显的优点是( )。
A 插入操作更加方便
B 删除操作更加方便
C 不会出现下溢的情况
D 不会出现上溢的情况

在作退栈运算时应先判别栈是否( )。
A 空
B 满
C 上溢
D 下溢

若栈顶指针指向栈顶元素，当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为( )
A n-1
B n
C n+1
D n/2

以下( )不是队列的基本运算
A 从队尾插入一个新元素
B 从队列中删除第i个元素
C 判断一个队列是否为空
D 读取队头元素的值

填空题

向量、栈和队列都是 线性 结构，可以在向量的 ==任何 == 位置插入和删除元素；对于栈只能在 栈顶 == 插入和删除元素；对于队列只能在 == 队尾 == 插入和 == 队首 删除元素。
一个顺序栈一旦被声明，其占用空间的大小（ ）。
答案：已固定

链栈和顺序栈相比，有一个比较明显的缺点，即（ ）。
答案：通常不会出现栈满的情况

用单链表表示的链式队列的队头在链表的（ ）位置。
答案：链头

在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是
一个（ ）结构。
答案：队列

循环队列 A[m] 存放其元素，用 front 和 rear 分别表示队头及队尾，则循环队列满的条件是（ ）。
答案：（rear+1)%m=front

在一个栈顶指针为 top 的链栈中，将一个 p 指针所指的结点入栈，应执行（ ）。
答案：p->next=top; top=p;

在一个栈顶指针为 top 的链栈中删除一个结点时，用 x 保存被删结点的值，则执行（ ）。
答案：x=top->data; top=top->next;

在一个链队中，设 front 和 rear 分别为队首和队尾指针，则插入 p 所指结点时，应执行（ ）。
答案：rear->next=p;rear=p;

在链队列中，f 和 r 分别为队头和队尾指针，要把 s 所指结点入队，应执行（ ）。
答案：r->next=s;r=s;

设 top 是一个链栈的栈顶指针，栈中每个结点由一个数据域 data 和指针域 next 组成，设用 x 接收栈顶元素，则取栈顶元素的操作为（ ）。
答案：x=top->data;

一个队列的入队序列是 2，4，6，8，则队列的输出序列是（ ）。
答案：2，4，6，8

一个栈的进栈序列是 5，6，7，8，则栈的不可能的出栈序列是（ ）。（进出栈操作可以交替进行）

5，8，6，7

栈的插入删除操作在（ ）进行。
答案：栈顶

栈和队列的相同点是（ ）。

逻辑结构与线性表相同，都是操作规则受到限制的线性表

以下说法正确的是（ ）。

栈的特点是先进后出，队列的特点是先进先出

设有一个带头结点的链队列，队列中每个结点由一个数据域 data 和指针域 next 组成，front 和 rear 分别为链队列的头指针和尾指针。设 p 指向要入队的新结点(该结点已被赋值)，则入队操作为（ ）。
答案：rear->next=p;rear=p;

设有一个带头结点的链队列，队列中每个结点由一个数据域 data 和指针域 next 组成，front 和 rear 分别为链队列的头指针和尾指针，要执行出队操作，用 x 保存出队元素的值，p 为指向结点类型的指针，可执行如下操作：p=front->next;x=p->data;然后指行（ ）。
答案：front->next=p->next;

以下说法不正确的是（ ）。

顺序队列中，当尾指针已经超越队列存储空间的上界，则一定是队列已满

一个递归算法必须包括（ ）。

终止条件和递归部分

假定一个链式队列的队头和队尾指针分别为 front 和 rear，则判断队空的条件为（ ）。

front=rear

向顺序栈中压入新元素时，应当（ ）。

应当先移动栈顶指针，再存入元素

判断一个循环队列 Q（最多元素为 m）为满的条件是（ ）。

答案：Q->front==(Q->rear+1)%m

判断栈满（元素个数最多 n 个）的条件是（ ）。

答案：top=-1

队列的删除操作是在（ ）。

答案：队前

一个队列的入队序列是 a,b,c,d,按该队列的可能输出序列使各元素依次入栈，该栈的可能输
出序列是 （ ）。（进栈出栈可以交替进行）。

答案：d,c,b,a

带表头结点的空循环双向链表的长度等于 0

判断题

队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。( )
正确的答案是“错”

两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片空间的两端。( )
正确的答案是==“对”==。

没有元素的堆栈称为空栈，空栈用不着栈顶指针。( )

正确

对采用链式存储结构的堆栈进行操作不必判断溢出。( )

正确

采用循环链表作为存储结构的队列称为循环队列。( )

错误

链接队列不存在溢出问题。( )

错误

栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。( )

正确

没有元素的堆栈称为空栈，空栈用不着栈顶指针。( )

错误

线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。

在表结构中最常用的是线性表，栈和队列不太常用。

错，不一定吧？调用子程序或函数常用，CPU中也用队列。

栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

对

对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

栈和链表是两种不同的数据结构。

错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项

栈和队列是一种非线性数据结构。

错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

答：对

简答题

说明线性表、栈与队的异同点。

答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。
不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。
② 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。

设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。

答：至少有14种。
① 全进之后再出情况，只有1种：4，3，2，1 ② 进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1
3,2,1,4 ③ 进2个之后再出的情况，有5种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3
2,1,3,4 ④ 进1个之后再出的情况，有5种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3

顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？

答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。
采用循环队列是解决假溢出的途径。 另外，解决队满队空的办法有三： ① 设置一个布尔变量以区别队满还是队空；
② 浪费一个元素的空间，用于区别队满还是队空。 ③ 使用一个计数器记录队列中元素个数（即队列长度）。
我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。
判断循环队列队空标志是： f=rear
队满标志是：f=(r+1)%N

设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有
① front=11，rear=19; ② front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？

答：用队列长度计算公式： (N＋r－f)% N
① L=（40＋19－11）% 40=8
② L=（40＋11－19）% 40=32

写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。

void main( ){
Queue Q;  Init Queue (Q);
Char x=’e’; y=’c’;
EnQueue (Q,’h’); EnQueue (Q,’r’);  EnQueue (Q, y);
DeQueue (Q,x); EnQueue (Q,x); 
DeQueue (Q,x); EnQueue (Q,’a’); 
while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y); };
Printf(x);
}

答：输出为“char”。

目录

一 概述

二 栈

2.1 栈的基本概念

2.2 进栈和出栈

2.3 栈的具体实现

2.4 栈的应用

3 队列

3.1 队列的基本概念

栈和队列不要混淆，栈结构是一端封口，特点是"先进后出"；而队列的两端全是开口，特点是"先进先出"。数据从表的一端进，从另一端出，且遵循 "先进先出" 原则的线性存储结构就是队列。3.2 队列的实现

3.3 队列的应用

---

一 概述

栈和队列，严格意义上来说，也属于线性表，因为它们也都用于存储逻辑关系为 "一对一" 的数据，但由于它们比较特殊，因此将其单独作为一篇文章，做重点讲解。既然栈和队列都属于线性表，根据线性表分为顺序表和链表的特点，栈也可分为顺序栈和链表，队列也分为顺序队列和链队列，这些内容都会在本章做详细讲解。

使用栈结构存储数据，讲究“先进后出”，即最先进栈的数据，最后出栈；使用队列存储数据，讲究 "先进先出"，即最先进队列的数据，也最先出队列。

---

二 栈

2.1 栈的基本概念

同顺序表和链表一样，栈也是用来存储逻辑关系为 "一对一" 数据的线性存储结构，如下图所示。 

  
从上图我们看到，栈存储结构与之前所了解的线性存储结构有所差异，这缘于栈对数据 "存" 和 "取" 的过程有特殊的要求：

1. 栈只能从表的一端存取数据，另一端是封闭的；
2. 在栈中，无论是存数据还是取数据，都必须遵循"先进后出"的原则，即最先进栈的元素最后出栈。拿图 1 的栈来说，从图中数据的存储状态可判断出，元素 1 是最先进的栈。因此，当需要从栈中取出元素 1 时，根据"先进后出"的原则，需提前将元素 3 和元素 2 从栈中取出，然后才能成功取出元素 1。

因此，我们可以给栈下一个定义，即栈是一种只能从表的一端存取数据且遵循 "先进后出" 原则的线性存储结构。通常，栈的开口端被称为栈顶；相应地，封口端被称为栈底。因此，栈顶元素指的就是距离栈顶最近的元素，拿下图中的栈顶元素为元素 4；同理，栈底元素指的是位于栈最底部的元素，下 中的栈底元素为元素 1。

2.2 进栈和出栈

基于栈结构的特点，在实际应用中，通常只会对栈执行以下两种操作：

• 向栈中添加元素，此过程被称为"进栈"（入栈或压栈）；
• 从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）；

2.3 栈的具体实现

栈是一种 "特殊" 的线性存储结构，因此栈的具体实现有以下两种方式：

1. 顺序栈：采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构。使用顺序表模拟栈存储结构常用的实现思路，即在顺序表中设定一个实时指向栈顶元素的变量（一般命名为 top），top 初始值为 -1，表示栈中没有存储任何数据元素，及栈是"空栈"。一旦有数据元素进栈，则 top 就做 +1 操作；反之，如果数据元素出栈，top 就做 -1 操作。
2. 链栈：采用链式存储结构实现栈结构。通常我们将链表的头部作为栈顶，尾部作为栈底，如下图所示。将链表头部作为栈顶的一端，可以避免在实现数据 "入栈" 和 "出栈" 操作时做大量遍历链表的耗时操作。因此，链栈实际上就是一个只能采用头插法插入或删除数据的链表。

   
   

两种实现方式的区别，仅限于数据元素在实际物理空间上存放的相对位置，顺序栈底层采用的是数组，链栈底层采用的是链表。有关顺序栈和链栈的具体实现会在后续章节中作详细讲解。

2.4 栈的应用

基于栈结构对数据存取采用 "先进后出" 原则的特点，它可以用于实现很多功能。
例如，我们经常使用浏览器在各种网站上查找信息。假设先浏览的页面 A，然后关闭了页面 A 跳转到页面 B，随后又关闭页面 B 跳转到了页面 C。而此时，我们如果想重新回到页面 A，有两个选择：

• 重新搜索找到页面 A；
• 使用浏览器的"回退"功能。浏览器会先回退到页面 B，而后再回退到页面 A。

浏览器 "回退" 功能的实现，底层使用的就是栈存储结构。当你关闭页面 A 时，浏览器会将页面 A 入栈；同样，当你关闭页面 B 时，浏览器也会将 B入栈。因此，当你执行回退操作时，才会首先看到的是页面 B，然后是页面 A，这是栈中数据依次出栈的效果。
不仅如此，栈存储结构还可以帮我们检测代码中的括号匹配问题。多数编程语言都会用到括号（小括号、中括号和大括号），括号的错误使用（通常是丢右括号）会导致程序编译错误，而很多开发工具中都有检测代码是否有编辑错误的功能，其中就包含检测代码中的括号匹配问题，此功能的底层实现使用的就是栈结构。
同时，栈结构还可以实现数值的进制转换功能。例如，编写程序实现从十进制数自动转换成二进制数，就可以使用栈存储结构来实现。
以上也仅是栈应用领域的冰山一角，这里不再过多举例。在后续的学习中，我们会大量使用到栈结构。

---

3 队列

3.1 队列的基本概念

队列，和栈一样，也是一种对数据的"存"和"取"有严格要求的线性存储结构。与栈结构不同的是，队列的两端都"开口"，要求数据只能从一端进，从另一端出，如下图所示：

通常，称进数据的一端为 "队尾"，出数据的一端为 "队头"，数据元素进队列的过程称为 "入队"，出队列的过程称为 "出队"。

不仅如此，队列中数据的进出要遵循 "先进先出" 的原则，即最先进队列的数据元素，同样要最先出队列。拿图 1 中的队列来说，从数据在队列中的存储状态可以分析出，元素 1 最先进队，其次是元素 2，最后是元素 3。此时如果将元素 3 出队，根据队列 "先进先出" 的特点，元素 1 要先出队列，元素 2 再出队列，最后才轮到元素 3 出队列。

栈和队列不要混淆，栈结构是一端封口，特点是"先进后出"；而队列的两端全是开口，特点是"先进先出"。数据从表的一端进，从另一端出，且遵循 "先进先出" 原则的线性存储结构就是队列。
3.2 队列的实现

队列存储结构的实现有以下两种方式：

1. 顺序队列：在顺序表的基础上实现的队列结构。由于顺序队列的底层使用的是数组，因此需预先申请一块足够大的内存空间初始化顺序队列。除此之外，为了满足顺序队列中数据从队尾进，队头出且先进先出的要求，我们还需要定义两个指针（top 和 rear）分别用于指向顺序队列中的队头元素和队尾元素，如下图所示：

   
   

   
   由于顺序队列初始状态没有存储任何元素，因此 top 指针和 rear 指针重合，且由于顺序队列底层实现靠的是数组，因此 top 和 rear 实际上是两个变量，它的值分别是队头元素和队尾元素所在数组位置的下标。当有数据元素进队列时，对应的实现操作是将其存储在指针 rear 指向的数组位置，然后 rear+1；当需要队头元素出队时，仅需做 top+1 操作。
2. 链队列：在链表的基础上实现的队列结构。链式队列的实现思想同顺序队列类似，只需创建两个指针（命名为 top 和 rear）分别指向链表中队列的队头元素和队尾元素，如下图所示。

两者的区别仅是顺序表和链表的区别，即在实际的物理空间中，数据集中存储的队列是顺序队列，分散存储的队列是链队列。

3.3 队列的应用

实际生活中，队列的应用随处可见，比如排队买 XXX、医院的挂号系统等，采用的都是队列的结构。
拿排队买票来说，所有的人排成一队，先到者排的就靠前，后到者只能从队尾排队等待，队中的每个人都必须等到自己前面的所有人全部买票成功并从队头出队后，才轮到自己买票。这就不是典型的队列结构吗？

---

 

一、栈

1、描叙

栈和队列是计算机中基本的两个数据结构，栈可以达到后进先出，队列可以先进先出。在实际应用上，我们可以使用栈进行逆序遍历链表，非递归中序遍历二叉树，括号匹配，函数调用等等；可以使用队列对二叉树进行层次遍历，打印机的打印服务，通信中的消息队列等等。

栈的储存规则:
1，栈只能从表的一端存取数据，另一端是封闭的
2，在栈中，无论是存数据还是取数据，都必须遵循"先进后出"的原则，即最先进栈的元素最后出栈。

栈的使用案例1:
浏览器 “回退” 功能的实现，底层使用的就是栈存储结构。
当你关闭页面 A 时，浏览器会将页面 A 入栈；同样，当你关闭页面 B 时，浏览器也会将 B入栈。因此，当你执行回退操作时，才会首先看到的是页面 B，然后是页面 A，这是栈中数据依次出栈的效果。

栈的使用案例2:
栈存储结构还可以帮我们检测代码中的括号匹配问题。
多数编程语言都会用到括号（小括号、中括号和大括号），括号的错误使用（通常是丢右括号）会导致程序编译错误，而很多开发工具中都有检测代码是否有编辑错误的功能，其中就包含检测代码中的括号匹配问题，此功能的底层实现使用的就是栈结构。

2、图文示例

先进后出

3、代码示例

package stackAndQueue;

/**
 * TODO 栈，先进后出
 */
public class Stack {

    // 底层基于数组
    private int[] arr;
    // 数据长度, 最后一个数据的索引=数据长度-1
    private int size;

    // 容量设置
    public Stack() {
        arr = new int[16];
    }

    public Stack(int length) {
        arr = new int[length];
    }

    /**
     * 添加
     */
    public void plus(int val) {
        arr[size++] = val;
    }

    /**
     * 获取并弹出元素, 最后一个数据的索引=size-1
     */
    public int pop() {
        return arr[--size];
    }


    /**
     * 判断是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 容量是否满了，添加可先判断容量,进行扩容操作
     */
    public boolean isFull() {
        return size == arr.length;
    }
}

测试代码

// 测试
class Test {
    public static void main(String[] args) {
        Stack stack = new Stack(5);
        stack.plus(1);
        stack.plus(2);
        stack.plus(3);
        stack.plus(4);
        stack.plus(5);
        System.out.println("容量是否满了-->" + stack.isFull());
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}


// 输出
容量是否满了-->true
5
4
3
2
1

二、队列

1、描叙

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。 [1]

队列的实现
队列存储结构的实现有以下两种方式：
顺序队列：在顺序表的基础上实现的队列结构；
链队列：在链表的基础上实现的队列结构；

两者的区别仅是顺序表和链表的区别，即在实际的物理空间中，数据集中存储的队列是顺序队列，分散存储的队列是链队列。

队列的实际应用
实际生活中，队列的应用随处可见，比如排队买 XXX、医院的挂号系统等，采用的都是队列的结构。

拿排队买票来说，所有的人排成一队，先到者排的就靠前，后到者只能从队尾排队等待，队中的每个人都必须等到自己前面的所有人全部买票成功并从队头出队后，才轮到自己买票。这就不是典型的队列结构吗？

2、图文示例

普通队列

先进先出

循环队列

先进先出

3、代码示例

package stackAndQueue;


/**
 * TODO 队列，先进先出
 */
public class Queue {

    // 底层基于数组
    private int[] arr;
    // 数据长度
    private int size;
    // 开头元素索引 (每获取一次数据 front+1)
    private int front;
    // 结尾元素索引（每添加一次数据rear+1，每获取一次数据rear-1 ）--> 数据长度=rear+1
    private int rear;

    // 容量设置
    public Queue() {
        arr = new int[16];
        front = -1;
        rear = -1;
    }

    public Queue(int length) {
        arr = new int[length];
        front = -1;
        rear = -1;
    }

    /**
     * 获取当前数据长度
     */
    public int size() {
        return this.size;
    }

    /**
     * 插入元素
     */

    public void plus(int val) {
        // 判断数组是否满了
        if (isFull()) {
            System.out.println("插入["+val+"]失败,数组容量已满");
        } else {
            // 循环插入,--元素尾添加
            if (rear == arr.length - 1) {
                rear = -1;
            }
            size++;
            arr[++rear] = val;
        }
    }


    /**
     * 获取并弹出元素
     */
    public int pop() {
        // 循环读取--元素头开始读取
        if (front == arr.length - 1) {
            front = -1;
        }
        size--;
        return arr[++front];
    }

    /**
     * 判断元素是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 容量是否满了，添加可先判断容量,进行扩容操作
     */
    public boolean isFull() {
        return size == arr.length;
    }
}

测试代码

// 测试
class Test1 {
    public static void main(String[] args) {
        Queue queue = new Queue(5);
        queue.plus(1);
        queue.plus(2);
        queue.plus(3);
        queue.plus(4);
        queue.plus(5);
        System.out.println("容量是否满了-->" + queue.isFull() + "  当前数据长度:" + queue.size());
        //消费--> size=0
        while (!queue.isEmpty()) {
            System.out.println(queue.pop());
        }
        // 添加数据,size=0
        queue.plus(6);
        queue.plus(7);
        queue.plus(8);
        queue.plus(9);
        queue.plus(10);
        System.out.println("弹出--> " + queue.pop());
        queue.plus(11);
        //
        queue.plus(12);
        queue.plus(13);
        queue.plus(14);
        while (!queue.isEmpty()) {
            System.out.println(queue.pop());
        }
    }
}

// 打印
容量是否满了-->true  当前数据长度:5
1
2
3
4
5
弹出--> 6
插入[12]失败,数组容量已满
插入[13]失败,数组容量已满
插入[14]失败,数组容量已满
7
8
9
10
11

本文到此结束，如果觉得有用，劳烦各位点赞关注一下呗，将不定时持续更新更多的内容…，感谢大家的观看！