数据结构与算法2
目录
- 栈和队列
- 1.栈（stack）
- 1.1 栈的定义和特点
- 1.2 顺序栈的表示
- 1.3 顺序栈的实现
- 1.3.1 顺序栈的初始化
- 1.3.2 顺序栈判断栈是否为空
- 1.3.3 求顺序栈长度
- 1.3.4 清空顺序栈
- 1.3.5 销毁顺序栈
- 1.3.6 顺序栈的入栈
- 1.3.7 顺序栈的出栈
- 1.4 栈链的表示
- 1.5 栈链的实现
- 1.5.1 栈链的初始化
- 1.5.2 判断栈链是否为空
- 1.5.3 栈链的入栈
- 1.5.4 栈链的出栈
- 1.5.5 取栈顶元素
- 2.队列（queue）
- 2.1 队列的定义和特点
- 2.2 顺序队的表示
- 2.3 顺序队的实现
- 2.3.1 顺序队的初始化
- 1.栈（stack）
栈和队列
1.栈（stack）
1.1 栈的定义和特点
- 栈是一个特殊的线性表，在表尾进行插入和删除
- 后进先出的线性表（LIFO结构）
表尾（an端）称为栈顶TOP；表头（a1端）称为栈底BASE
- 入栈：插入元素到TOP
- 出栈：从TOP删除最后一个元素
同线性表相同，为一对一关系
-
存储结构：顺序栈、链栈
- 栈的顺序存储：顺序栈
- 栈的链式存储：链栈
-
上溢（overflow）：栈已经满，继续压入值
-
下溢（underflow）：栈已经空，继续弹出值
上溢是一种错误，使问题处理无法进行
下溢使一种结束条件，问题处理结束
1.2 顺序栈的表示
#define MAXSIZE 100
typedef struct{
int *base; //栈底
int *top; //栈顶
int stacksize; //栈可用的最大容量
}SqStack；
1.3 顺序栈的实现
1.3.1 顺序栈的初始化
void InitStack(SqStack &S){ //构建一个空顺序栈
S.base = new int[MAXSIZE];
if(!S.base) return; //存储分配失败
S.top = S.base;
S.stacksize = MAXSIZE;
}
1.3.2 顺序栈判断栈是否为空
bool StackEmpty(SqStack S){ //若栈顶等于栈底，则顺序栈为空
if(S.top == S.base) return true;
else return false;
}
1.3.3 求顺序栈长度
int StackLength(SqStack S){
return S.top - S.base;
}
1.3.4 清空顺序栈
void ClearStack(SqStack &S){
if(S.base) S.top = S.base;
}
1.3.5 销毁顺序栈
void DestoryStack(SqStack &S){
if(S.base){
delete S.base;
S.stacksize = 0;
S.base = S.top = NULL;
}
}
1.3.6 顺序栈的入栈
void Push(SqStack &S, int e){
if(S.top - S.base == S.stacksize) return; //栈满
*S.top++ = e;
}
1.3.7 顺序栈的出栈
void Pop(SqStack &S, int &e){
if(S.top == S.base) return;
e = *--S.top;
}
1.4 栈链的表示
- 运算受限的单链表，只能在链表头部进行操作
- 链表的头指针就是栈顶，不需要头结点
- 插入删除仅在栈顶
typedef struct StackNode{
int data;
struct StackNode *next;
}StackNode, *LinkStack;
LinkStack S;
1.5 栈链的实现
1.5.1 栈链的初始化
void InitStack(LinkStack &S){
S = NULL;
}
1.5.2 判断栈链是否为空
bool StackEmpty(LinkStack S){
if(S == NULL) return true;
else return false;
}
1.5.3 栈链的入栈
void Push(LinkStack &S, int e){
p = new StackNode; //生成新节点
p->data = e;
p->next = S;
S = p;
}
1.5.4 栈链的出栈
void Pop(LinkStack &S, int &e){
if(S == NULL) return;
e = S->data; //出栈的元素值
p = S;
S = S->next;
delete p;
}
1.5.5 取栈顶元素
int GetTop(LinkStack S){
if(S == NULL) return;
return S->data;
}
2.队列（queue）
2.1 队列的定义和特点
- 队列是一种先进先出（FIFO）的线性表
- 在表尾插入，表头删除（头删尾插）
- 表尾为an端（队尾），表头为a1端（队头）
同线性表相同，为一对一关系
- 存储结构：顺序队、链队
循环顺序队列更常见
2.2 顺序队的表示
#define MAXQSIZE 100 //最大队列长度
typedef define{
int *base; //初始化动态分配原始空间
int front; //头指针
int rear; //尾指针
}SqQueue;
2.3 顺序队的实现
常见问题：假上溢
解决方法：引入循环队列 实现方式：使用模运算
- 插入元素： Q.base[Q.rear] = x; Q.rear=(Q.rear+1) % MAXQSIZE;
- 删除元素： x = Q.base[s.front]; Q.front = (Q.front+1) % MAXQSIZE;
2.3.1 顺序队的初始化
void Init