- 栈和队列是限定插入和删除的只能在表“端点”进行的线性表
- 普通线性表的插入和删除操作
栈的定义和特点
-
栈（stack）是一个特殊的线性表，是限定的仅在一端（通常是表尾）进行插入和删除操作线性表
-
又称为后进后出（Last In First Out）的线性表，简称LIFO结构
-
栈的相关概念
栈是仅想表尾进行插入、删除操作的线性表。
表尾 称为栈顶Top；表头称为栈底Base
插入元素到栈顶（即表尾）的操作，称为入栈。
从栈顶(即表尾)删除最后一个元素的操作，称为出栈。 -
栈的示意图
-
栈的操作特性：后进先出
-
【思考】假设有3个元素a,b,c，入栈顺序是a,b,c则它们的出栈顺序有几种可能？
首先是a,b,c依次入栈，c,b,a依次出栈即可。
第二种是a先入栈，然后出栈，同样b也如此，c也是一样，得到出栈顺序a,b,c等， -
栈与一般线性表有什么不同
栈与一般线性表的区别：仅在于运算规则不同。
队列的定义和特点
- 队列（queue）是一种先进先出（Frist In Frist Out FIFO）的线性表。在表一端插入（表尾），在另一端（表头）删除
- 队列相关概念
- 定义 ： 只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表（头删尾插）
- 逻辑结构：与同线性表相同，仍为一对一关系。
- 存储结构：顺序对或链队，以循环队列更常见
- 运算规则：只能在队首和队尾运算， 且访问结点是依照先进先出（FIFO）的原则。
- 实现方式：关键是掌握入队和出队操作，具体实现依顺序对或链队的不同而不同。