对于线性表,我们可能要执行下列操作:访问表的第k个结点、在k这个结点之前或者之后插入一个新结点,抑或是删除第k个结点等等操作,其中我们会遇到值对第一个或者最后一个结点插入、删除、和访问值的线性表,我们给它们以特殊的名称:
一、栈与队列以及双端队列的概念
1.1 栈的概念及结构
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶
1.2 队列的概念及结构
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO(First In First Out)
入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头
1.3 双端队列的概念及结构
双端队列:是一种线性表,又称为双向队列,所有的插入和删除(通常还有所有的访问)都在表的两端进行。
二、栈的实现和模拟栈
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小。、
2.1 实现一个支持动态增长的栈
头文件:
源文件: