1.栈的基本概念
只允许在一端进行插入或删除操作的线性表，先进后出
结构：
栈顶（Top）：线性表允许进行插入和删除的那一端
栈低（Bottom）：固定的，不允许进行插入和删除的另一端
卡特兰数：n个不同元素进栈，出栈元素不同排列的个数为
2.栈的顺序存储结构
顺序栈：采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈低到栈顶的数据元素，同时附设一个指针(top）指示当前栈顶元素的位置
共享栈：让两个顺序栈共享一个一维数组空间，将两个栈的栈低分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸
3.栈的链式存储结构
采用单链表实现，并规定所有操作都是在单链表的表头进行
优点：便于多个栈共享存储空间和提高效率，且不存在栈满上溢的情况
4.队列的基本概念
队列的定义：是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除，先进先出
结构：
队头Front：允许删除的一端又称队首
队尾Rear：允许插入的一端
空队列：不含任何元素的空表
5.队列的顺序存储结构
队列的顺序存储：分配一端连续的存储单元存放队列中的元素，并附设两个指针
循环队列：把存储队列元素的表从逻辑上视为一个环
6.队列的链式存储结构
队列的链式表示称为链队列，是一个同时带有队头和队尾的单链表
优点：适合于数据元素变动比较大的情形，不存在队列满且产生溢出的问题
7.双端队列
概述：双端队列是指允许两端都可以进行入队和出对操作的队列，逻辑结构仍是线性结构，将队列的两端分别称为前端和后端，两端都可以入队和出对
分类：
输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列
输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列
网友评论