栈和队列
2019-03-21 17:13:59 0 举报AI智能生成
数据结构-栈和队列
作者其他创作
大纲/内容
栈
定义
栈是一种只允许在表的一端进行插入操作和删除操作的线性表。允许操作的一端称为栈顶，栈顶元素的位置由栈顶指针给出
运算规则
先进后出
逻辑结构
线性结构，特殊的线性表：
1. 其操作仅是一般线性表的操作的一个子集。
2. 插入、删除操作的位置受到限制。
1. 其操作仅是一般线性表的操作的一个子集。
2. 插入、删除操作的位置受到限制。
存储结构
顺序存储结构
用一维数组STACK[0..M–1]来表示栈，并定义一个整形变量top指向当前栈顶元素。栈为空时，top=-1
类型定义
#define M 1000
SElemType STACK[M];
int top = -1; //初始为空栈
SElemType STACK[M];
int top = -1; //初始为空栈
判断栈空
int EMPTYS( int top )
{
return top==–1;
}
{
return top==–1;
}
判断栈满
int FULLS( int top )
{
return top==M–1;
}
{
return top==M–1;
}
插入（入栈）
要先判断是否栈满，再STACK[++top]=item；
删除（出栈）
要先判断是否栈空，再item=STACK[top--]; （item用来保存删掉的元素，只需将top指针下移，就算删除了）
两栈共享连续空间（数组）问题
数组STACK[0..M-1]
top[0]、 top[1] 分别为第1个与第2个栈的栈顶元素指针
top[0]、 top[1] 分别为第1个与第2个栈的栈顶元素指针
栈满：top[0]=top[1]–1
栈空：
第1个栈空 top[0]=–1
第2个栈空 top[1]=M
第1个栈空 top[0]=–1
第2个栈空 top[1]=M
链式存储结构
用一个线性链表来实现一个堆栈结构, 同时设置一个指针变量top指出栈顶元素所在链结点的位置。栈为空时，有top=NULL
（链栈是运算是受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针 ）
（链栈是运算是受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针 ）
类型定义
typedef struct node {
SElmeType data;
struct node *link;
} STNode, *STLink;
SElmeType data;
struct node *link;
} STNode, *STLink;
判断栈空
int EMPTYS( STLink top )
{
return top==NULL;
}
{
return top==NULL;
}
插入（入栈）
不必判断是否栈满，在链表最前面插入一个新结点即可（头插法）
删除（出栈）
先判断是否栈空，再删掉第一个结点（删前先保存以便free）
取栈顶元素
先判空，再返回头指针（top）所指元素
if (S==NULL) exit(1)；
else return S–>data;
if (S==NULL) exit(1)；
else return S–>data;
栈与递归
递归是自己调用自己，当多个函数构成嵌套调用时, 遵循后调用的先返回，即后进先出
具有递归定义的数据结构
树、广义表
可递归求解的问题
迷宫问题、hanoi塔问题
递归算法效率分析
空间效率：与递归树的深度成正比 O(n）
时间效率：与递归树的结点数成正比 O(2^n)
时间效率：与递归树的结点数成正比 O(2^n)
递归优缺点
优点：结构清晰，程序易读
缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大 。
为克服缺点：尾递归、单向递归——>循环结构
缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大 。
为克服缺点：尾递归、单向递归——>循环结构
队列
定义
队列是一种只允许在表的一端进行插入操作（队尾），而在表的另一端进行删除操作（队头）的线性表。队头由front指出，队尾由rear指出。
运算规则
先进先出
逻辑结构
线性结构，特殊的线性表：
1. 其操作仅是一般线性表的操作的一个子集。
2. 插入、删除操作的位置受到限制。
1. 其操作仅是一般线性表的操作的一个子集。
2. 插入、删除操作的位置受到限制。
约定
rear 指出实际队尾元素所在的位置,
front 指出实际队头元素所在位置的前一个位置。
front 指出实际队头元素所在位置的前一个位置。
存储结构
顺序存储结构
用一维数组QUEUE[0..M–1]来表示队列，设置两个变量 front与rear指出当前队头元素与队尾元素的位置
初始化
初始时，队列为空，有front=rear=-1
判断队空
return front==rear
插入（入队）
先判断是否队满 if(rear==M-1)，再插入QUEUE[++rear]=item;
删除（出队）
先判断是否队空，再删除item=QUEUE[++front];（只需将front指针后移，就算删除了）
假溢出
rear==M-1了，但front前面还有空位
循环队列（解决假溢出）
把队列(数组)设想成头尾相连的循环表，使得数组前部由于删除操作而导致的无用空间尽可能得到重复利用，这样的队列称为循环队列
链式存储结构
用一个线性链表表示一个队列，指针front与rear指向实际队头元素与实际队尾元素所在的结点
初始化
front=rear=NULL
判断队空
return front==NULL;
插入（入队）
分两种情况：（因为没给链表设头结点，如果有头结点就不用分情况）
1、将元素插入插入空队 if(front==NULL) front=p;
2、插入非空队 rear->link=p; rear=p;
1、将元素插入插入空队 if(front==NULL) front=p;
2、插入非空队 rear->link=p; rear=p;
删除（出队）
先判断队列是否为空，再删除队头结点
销毁一个队列
一个一个删除队头结点：
while(front){ /* 队列非空时 */
rear=front->link;
free(front); /* 释放一个结点空间 */
front=rear;
}
while(front){ /* 队列非空时 */
rear=front->link;
free(front); /* 释放一个结点空间 */
front=rear;
}
0 条评论
下一页
为你推荐
查看更多
