目录
栈和队列
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
标签:1.5,顺序,栈链,1.3,int,算法,base,数据结构
From: https://www.cnblogs.com/cherishviki/p/18430214