预习篇之栈和队列

限定性线性表——栈和队列

栈

栈是一种具有线性结构的数据结构，是操作受限的线性表

栈的特点是后进先出，只能在栈顶进行插入和删除操作，入栈、出栈

顺序栈中，栈空标志：S.top=S.base;

栈满标志：S.top-S.base>=S.stacksize;

链栈中，不设头结点，头结点就是栈顶指针，栈空S=NULL。

用于：数值转换，括号匹配检验、行编辑程序，迷宫问题、算数表达式求值（2个栈），递归的实现

队列

一种具有线性结构的数据结构，是操作受限的线性表；

先进先出，只能在队尾插入元素和队头删除元素，称为入队列和出队列；

队满标志：（Q.rear+1）%MAXOQSIZE==Q.front

链队列中，队空标志：Q.front=Q.rear

空间范围内不会出现队满的情况。

其他，了解定义：双端队列、输出受限的双端队列，输入受限的双端队列