数据结构之栈和队列

女爷i 2024-04-08 09:41 81阅读 0赞

#### 栈和队列 ####

*  1.栈
 *   *  1.1栈的定义
     *  1.2栈的主要操作
     *  1.3 栈的存储结构
 *  2.队列
 *   *  2.1 队列的定义
     *  2.2 队列的主要操作
     *  2.3 队列的存储结构
 *  3.Java中的线性表

## 1.栈 ##

### 1.1栈的定义 ###

（1）栈又称为堆栈，它是**运算受限**的线性表。其限制是仅允许在表的一端进行插入和删除操作，不允许其他任何位置进行插入、查找和删除等操作。  
（2）表中进行插入、删除操作的一端称为栈顶，栈顶保存的元素称为栈顶元素。相对的，表的另一端称为栈底。  
（3）当栈中没有数据元素时称为空栈；  
（4）向一个栈插入元素又称为进栈或入栈，从一个栈中删除元素又称为出栈或退栈。  
（5）由于栈的插入和删除操作仅在栈顶进行， 后进栈的元素必定先出栈；所以又把堆栈称为**后进先出表**  
![在这里插入图片描述][49e00e0004b044f4a79432960d679bf1.png]

### 1.2栈的主要操作 ###

![在这里插入图片描述][b5af40b2e97547c5b7f2a7e9dc96dee8.png]

### 1.3 栈的存储结构 ###

（1）顺序栈  
顺序栈是使用顺序存储结构实现的堆栈，即利用一组地址连续的存储单元一次存放堆栈中的数据元素  
（2）链栈  
链栈即采用链表做为存储结构实现的栈

## 2.队列 ##

### 2.1 队列的定义 ###

（1）队列简称队，它同堆栈一样，也是一种运算受限的线性表  
（2）其限制是仅允许在表的一端进行插入，而在表的另一端进行删除  
（3）在队列中把插入数据元素的一端称为队尾，删除数据的一端称为队首  
（4）向对尾插入元素称为进队或入队，新元素入队后成为新的对尾元素；从队列中删除元素称为离队或出对，元素出对后，其后续元素成为新的队首元素  
（5）由于队列的插入和删除操作分别在对尾和对首进行，每个元素必须按照进入的次序离队，也就是说先进队的元素必然先离队，所以称队列为**先进先出表**。

### 2.2 队列的主要操作 ###

![在这里插入图片描述][fa399743bd444a70a06b4c15ffd8bffe.png]

### 2.3 队列的存储结构 ###

（1）顺序队列  
![在这里插入图片描述][6070e5834e6b4712a96eb0040ea3ca64.png]

![在这里插入图片描述][e2698af33b41444c9cb6ed21037a0374.png]

（2）链式队列  
队列的链式存储可以使用单链表来实现

![在这里插入图片描述][d585d311cd33400ab9f142befe6cc424.png]

![在这里插入图片描述][0eafb7d015df47c78a989772fb471024.png]

## 3.Java中的线性表 ##

![在这里插入图片描述][9cab204ec4724b998b1d6f0206cf677e.png]  
注意：LinkedList可以当做栈，队列以及线性表来用

[49e00e0004b044f4a79432960d679bf1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/272aa6d141004160a313ca09c7d01011.png
[b5af40b2e97547c5b7f2a7e9dc96dee8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/ad292f40c12d4aa5a2d653c2e5fbf49a.png
[fa399743bd444a70a06b4c15ffd8bffe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/a8e619a7881548948489fb01db4ed53a.png
[6070e5834e6b4712a96eb0040ea3ca64.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/06fbb0817765410e95b25845baaaaba0.png
[e2698af33b41444c9cb6ed21037a0374.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/13eb318f08714de1be9fac6bbe70d6b2.png
[d585d311cd33400ab9f142befe6cc424.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/2c077d2c9363414eb4a0329eae6050ed.png
[0eafb7d015df47c78a989772fb471024.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/cc6c53e202a54c9dba5f4ed4a41eeeaa.png
[9cab204ec4724b998b1d6f0206cf677e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/1684faa139d746338d54f9b98310e944.png