1.栈:限定仅在表尾进行插入或删除操作的线性表。
栈的基本操作：在栈顶进行插入或删除，栈的初始化、判空及取栈顶元素等。
入栈口诀：堆栈指针top “先压后加”
出栈口诀：堆栈指针top “先减后弹”
top=0表示空栈。
2.栈的表示和实现
1)构造一个空栈S
Status InitStack(SqStack &S)
{
S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!S.base) exit (OVERFLOW); //存储分配失败
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
2)返回栈顶元素
Status GetTop(SqStack S, SElemType e)
{//若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR
if(S.top == S.base) return ERROR;
e = *(S.top-1);
return OK;
}//GetTop
3)顺序栈入栈函数PUSH（）
Status Push(SqStack &S, SElemType e)
{ //插入元素e为新的栈顶元素
if(S.top-S.base>=S.stacksize)//栈满，追加存储空间
{
s.base = (SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base) exit(OVERFLOW);//存储分配失败
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ =e;
return OK:
}//PUSH
4)顺序栈出栈函数POP()
status Pop( SqStack &S,SElemType &e)
{ //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK,否则返回ERROR
if(S.top == S.base) return ERROR;
e=* —S.top;
return OK;
}
3.栈的应用
数制转换，括号匹配的检验，行编辑程序，迷宫求解，表达式求值，递归实现。
4.队列：是一种先进先出的线性表，它只允许在表的一端进行插入，而在另一端删除元素。
允许插入的一端叫做队尾，允许删除的一端叫做队头。
除了栈和队列外，还有一种限定性数据结构是双端队列。双端队列是限定插入和删除操作在表的两端进行的线性表。
5.链队列结点类型定义：
typedef Struct QNode{
QElemType data; //元素
Struct QNode *next; //指向下一结点的指针
}Qnode , * QueuePtr ;
链队列类型定义：
typedef struct {
QueuePtr front ; //队首指针
QueuePtr rear ; //队尾指针
} LinkQueue;
① 空链队的特征：front=rear
② 链队会满吗？一般不会，因为删除时有free动作。除非内存不足！
③ 入队（尾部插入）：rear->next=S; rear=S;
出队（头部删除）：front->next=p->next;
6.顺序队
顺序队类型定义：
#define QUEUE-MAXSIZE 100 //最大队列长度
typedef struct {
QElemType *base; //队列的基址
int front; //队首指针
int rear; //队尾指针
}SqQueue
建队核心语句：
q.base=(QElemType *)malloc(sizeof (QElemType)* QUEUE_MAXSIZE); //分配空间
顺序队示意图：
7.循环队列：
队空条件 : front = rear (初始化时：front = rear )
队满条件： front = (rear+1) % N (N=maxsize)
队列长度（即数据元素个数）：L=（N＋rear－front）% N
1)初始化一个空队列
Status InitQueue ( SqQueue &q ) //初始化空循环队列 q
{
q.base=(QElemType *)malloc(sizeof(QElemType）* QUEUE_MAXSIZE); //分配空间
if (!q.base) exit(OVERFLOW);//内存分配失败，退出程序
q.front =q.rear=0; //置空队列
return OK;
} //InitQueue;
2)入队操作
Status EnQueue(SqQueue &q, QElemType e)
{//向循环队列 q 的队尾加入一个元素 e
if ( (q.rear+1) % QUEUE_MAXSIZE == q.front)
return ERROR ; //队满则上溢，无法再入队
q.rear = ( q.rear + 1 ) % QUEUE_MAXSIZE;
q.base [q.rear] = e; //新元素e入队
return OK;
}// EnQueue;
3)出队操作
Status DeQueue ( SqQueue &q, QElemType &e)
{//若队列不空，删除循环队列q的队头元素，
//由 e 返回其值，并返回OK
if ( q.front = = q.rear ) return ERROR;//队列空
q.front=(q.front+1) % QUEUE_MAXSIZE;
e = q.base [ q.front ] ;
return OK;
}// DeQueue
链队列空的条件是首尾指针相等，而循环队列满的条件的判定，则有队尾加1等于队头和设标记两种方法。
补充重点：
为什么要设计堆栈？它有什么独特用途？
什么叫“假溢出” ？如何解决？
① 调用函数或子程序非它莫属；
② 递归运算的有力工具；
③ 用于保护现场和恢复现场；
④ 简化了程序设计的问题。
2.为什么要设计队列？它有什么独特用途？
① 离散事件的模拟（模拟事件发生的先后顺序,例如 CPU芯片中的指令译码队列）；
② 操作系统中的作业调度（一个CPU执行多个作业）；
③ 简化程序设计。
答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。解决假溢出的途径———采用循环队列。
4.在一个循环队列中，若约定队首指针指向队首元素的前一个位置。那么，从循环队列中删除一个元素时，其操作是先 移动队首位置 ，后 取出元素。
5.线性表、栈、队的异同点：
相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。
不同点：① 运算规则不同：
线性表为随机存取；
而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；
队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。
② 用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、OS作业调度和简化设计等。