堆栈的定义
后进先出
二、堆栈的基本操作
1.插入（进栈、入栈）
2.删除（出栈、退栈）
3.测试堆栈是否为空
4.测试堆栈是否已满
5.检索当前栈顶元素
数组 静态结构
堆栈 动态结构
溢出
上溢 当堆栈已满时做插入操作（top = M-1）
下溢 当堆栈为空时做删除操作（top = -1）
1.初始化堆栈
void INITIALS(int &top)
{
top = -1;
}
2.测试堆栈是否为空
int EMPTYS(int top)
{
return top == -1;
}
3.测试
int FULLS(int top)
{
return top == M - 1;
}
4.插入（进栈）算法
int PUSH(SElemType STACK[], int &top)
{
if(FULLS(top))
{
return 0;
} else {
STACK[++top] = item;
retrun 1;
}
}
5.删除（出栈）算法
int POP (SElemType STACK[], int &top)
{
if(EMPTYS(top))
return 0;
else {
item = STACK[top - -];
return 1;
}
}
三、多栈共享连续空间问题
（以两个栈共享一个数组为例）
栈满的条件 top[0] = top[1] - 1
算法
int PUSH(SElemType STACK[], int top,int i,SelemType item)
{
if(top[0] == top[1] -1)
retrurn 0;
else {
if(i == 1)
STACK[++top] = item;
else
STACK[- - top] = item;
return 1;
}
}
int PUSH(SElemType STACK[], int top,int i,SelemType item)
{
if(top[0] == top[1] -1)
retrurn 0;
else {
if(i == 1)
top[0] ++; // 修改第一个栈顶指针
else
top[1]- -; // 修改第二个栈顶指针
STACK[top[i - 1]] = item;
return 1;
}
}
int POP(SElemType STACK[], int top, int i, SElemType item)
{
if(i == 1)
if(top[0]==-1)
return 0;
else {
item = STACK[top[0] - -];
return 1;
}
else
if(top[1]== M)
return 0;
else {
item = STACK[top[1]++];
return 1;
}
}
4.3 堆栈的链式存储结构
类型定义
typedef struct node {
SELmeType data;
struct node *link;
} STNode, *STLink;
二、基本算法
1.堆栈初始化
void INITIAL(STLink &top)
{
top = NULL;
}
2.测试堆栈是否为空
int EMPTYS(STLink top)
{
return top == NULL;
}
3.插入（进栈）算法
// 不必判断栈满
int PUSHLINK(STLink &top, SElemType item)
{
STLink p;
if(!(p=(STLink)malloc(sizeof(STNode)))
return 0;
else {
p->data = item; // 将item送新的结点数据域
p->link = top; // 将新结点插入到结点最前面
top = p; // 修改栈顶指针指向
return 1;
}
}
4.删除（退栈）算法
int POPLINK(STLink &top, SElemType &item)
{
STLink p;
if(EMPTYS(top))
return 0;
else {
p = top;
item = top->data;
top = top->link;
free(p);
return 1;
}
}
4.4堆栈的应用举例
4.5队列的基本概念
先进先出
二、队列的基本操作
1.队列的插入（进队、入队）
2.队列的删除（出队、退队）
3.测试队列是否为空
4.检索当前对头元素
5.创建一个空队
特殊性：1.其操作仅是一般线性表的操作的一个子集
2.插入和删除操作的位置受限制
约定
rear 指出实际队尾元素所在的位置
front 指出实际队头元素所在位置的前一个位置
二、基本算法
1.初始化队列
void INITIALQ(int &front, int &rear)
{
front = -1;
rear = -1;
}
2.测试队列是否为空
int EMPTYQ(int front, int rear)
{
return front == rear;
}
3.插入（进队）算法
int ADDQ(QElemType QUEUE, int &rear, QElemType item)
{
if(rear == M-1)
return 0;
else {
QUEUE[++ rear] = item;
return 1;
}
}
4.删除（出队）算法
int DELQ(QElemType QUEUE[], int &front, int &rear, QElemType &item)
{
if(EMPTYQ(front, rear))
return 0;
else
item = QUEUE[++ front];
return 1;
}
假溢出
算法
int ADDQ(QElemType QUEUE[] , int &rear, QElemType item)
{
if(rear == M -1 )
return 0;
else {
QUEUE[++ rear] = item;
return 1;
}
}
三、循环队列
4.7 队列的链式存储结构
front 与 rear分别指向实际队头和队尾元素
3.插入（进队）
1.初始队列为空
2.初始队列非空
算法
#define LEN sizeof(QNode)
int ADDLINKQ(QLink &front, QLink &rear, QElemType item)
{
QLink p;
if(!(p=(Qlink)malloc(LEN)))
return 0;
p->data = item;
p->link = NULL;
if(front == NULL) // 插入空队
front = p;
else
rear->link = p; // 插入非空队
rear = p;
return 1;
}
4.删除（出队）
算法
int DELLINKQ(QLink &front, QLink &rear, QElemType &item)
{
Qlink p;
if(EMPTYQ(front))
return 0;
else {
p = front;
front = front->link;
item = p->data;
free(p);
return 1; // 队列非空 删除成功
}
}
5.销毁一个队列
将链表中所有结点都删除 并且释放存储空间 使队列成为一个空队列（空链表）
void DESLINKQ(QLink &front, QLink &rear)
{
while(front) {
rear = front->link;
free(front);
front = rear;
}
}