文章目录
一、栈
栈的基本定义
-
定义:只允许在一段进行插入或者删除操作的线性表(先进后出——LIFO:Last In First Out)
栈的逻辑结构与普通的线性表相同,数据运算(插入、删除操作)有区别
-
重要术语:
- 栈顶:允许插入和删除的一端(最上边的元素——栈顶元素)
- 栈底:不允许与插入和删除的一端(最下边的元素——栈底元素)
- 空栈:不包含任何元素
-
基本操作:
- InitStack(&S);——初始化栈:构建一个空栈S,分配内存空间(创建)
- DestoryStack(&L);——销毁栈:销毁并释放栈S说占用的内存空间(销毁)
- Push(&S,x);——进栈:若栈S未满,则将x加入使之成为心栈顶(增)
- Pop(&S,&x);——出栈:若栈S非空,则弹出栈顶元素,并用x返回(删)
- Getop(S,&x);——读栈顶元素:若栈S非空,则用x返回栈顶元素(查:大多只访问栈顶元素)
- StackEmpty(S);——判断S是否为空:若S为空,则返回true,否则返回false
顺序栈的实现
//顺序栈的定义
#define MaxSize 10 // 定义栈中元素最大个数
typedef struct{
ElemType data[MaxSize]; // 静态数组存放栈的数据元素
int top; //栈顶指针
}SqStack;
top指针的两种指示方式:
- top指针指向栈顶元素,空栈时指向-1——入栈时候:Top指针首先+1,然后再让新元素入栈;出栈时候:元素先出栈,然后top指针-1
- top指针指向下一个需要插入的元素的位置,初始化时空栈时指向0——入栈时候:首先让新元素入栈,然后top战阵+1;出栈时候:首先top指针-1,然后元素出栈
基本运算如下:(仅以top指针初始化指向-1为例)
// 初始化
void InitStack(SqStack &S){
S.top=-1; //栈顶指针设为-1
}
// 判断栈空
bool StackEmpty(SqStack S){
if(S.top=-1)
return true;
else
return false;
}
// 进栈操作
bool Push(SqStack &S,ElemType x){
if(S.top==MaxSize-1){ //栈满否?
return false;
}
S.top++;
S.data[S.top]=x; // 元素入栈,等价于 S.data[++S.top]=x;
return true;
}
// 出栈操作
bool Pop(SqStack &S,ElemType &x){ // 栈非空,弹出栈顶元素,用x返回
if(S.top=-1)
return false;
x=S.data[S.top];
S.top--; // 元素出栈,等价于 x=S.data[S.top--];
return true;
}
// 读栈顶元素
bool Gettop(SqStack &S,ElemType &x){
if(S.top=-1)
return false;
x=S.data[S.top];
return true;
}
共享栈
判断栈满的条件:top0+1==top1——两个栈顶指针除了初始化时,其余时候指向各自的栈顶元素
实现:
#define MaxSize 10 // 定义栈中元素最大个数
// typedef int ElemType;
typedef struct{
ElemType data[MaxSize]; // 静态数组存放栈的数据元素
int top0; // 0号栈顶指针
int top1; // 1号栈顶指针
}ShStack;
// 初始化栈
void InitStack(ShStack &S){
S.top0=-1;
S.top1=MaxSize;
}
栈的链式存储
// 定义
typedef struct Linknode{
ElemType data;
struct Linknode *next;
}*LiStack;
二、队列
-
定义:只允许在一端进行插入,另一端删除的线性表(先进先出FIFO)——操作受限的线性表
-
重要术语:
- 队头:允许删除的一端
- 队尾:允许插入的一端
- 空队列:不包含数据元素
-
操作:
- InitQueue(&Q);——初始化队列:构造一个空队列
- DestoryQueue(&Q);——销毁队列:销毁并释放队列Q所占用的内存空间
- EnQueue(&Q,x);——入队:若队列Q未满,将x加入,使之成为新的队尾
- DeQueue(&Q,&x):——出队:若队列Q非空,删除队头元素,并用x返回
- GetHead(Q,&x);——读队头元素:若队列Q非空,则将队头元素赋值给x(查:队列中大多数只访问队头元素)
- QueueEmpty(Q);——判队列空:若丢列Q为空返回true,否则返回false
顺序存储实现队列
实现:队头指针指向队头元素;队尾指针指向队尾元素的后一个位置(不同版本有不同定义:比如:队头指针指向队头元素,队尾指针指向队尾元素,此时的各类操作有下列操作列略有区别,请注意区分)
初始化:初始化时队头指针和队尾指针相同都指向0
判空:Q.rear=Q.front
#define MaxSize 10
typedef struct{
ElemType data[MaxSize]; // 存放队列元素
int front,rear; // 队列头指针与尾指针
}SqQueue;
基本操作实现:
// 初始化队列
void InitQueue(SqQueue &Q){
Q.rear=Q.front=0; // 初始化时,队头队尾指针指向0
}
// 判空
bool QueueEmpty(SqQueue Q){
if(Q.rear==Q.front) // 判空操作尾指针和头指针在同一个位置
return true;
else
return false;
}
// 插入操作——由于存在假溢出,所以需要特殊处理——引入循环队列
bool EnQueue(SqQueue &Q,ElemType x){
// if(队列已满)——判满操作,后边会给出具体实现
// return false;
Q.data[Q.rear]=x; // 新元素插入队尾
Q.rear=(Q.rear+1)%MaxSize; // 队列指针+1取模运算——构造逻辑上的环状
return true;
}
循环队列
在循环队列中,为了调和队空和队满时候的矛盾,有如下三种方案:
方案一:判满条件——队尾指针的下一个位置是队头(Q.front=(Q.rear+1)%MaxSize)——此时空了一位(rear指向的位置)未存入数据
-
初始化时:rear=front=0
-
判断队列已满的条件:Q.front==(Q.rear+1)%MaxSize
-
判断队列为空的条件:Q.rear==Q.front
-
队列数据元素:(rear+MaxSize-front)%MaxSize
// 方案一
// 空一位不存数据——最大长度为MaxSize-1
// 入队操作
bool EnQueue(SqQueue &Q,ElemType x){
if((Q.rear+1)%MaxSize==Q.front) // 判断队满条件
return false;
Q.data[Q.rear]=x;
Q.rear=(Q.rear+1)%MaxSize;
return true;
}
// 出队操作
bool DeQueue(SqQueue &Q,ElemType &x){
if(Q.front==Q.rear) // 判断队空条件
return false;
x=Q.data[Q.front];
Q.front=(Q.front+1)%MaxSize;
return true;
}
// 获得队头元素的数值,用x返回
bool GetHead(SqQueue &Q,ElemType &x){
if(Q.rear=Q.front)
return false;
x=Q.data[Q.front];
return true;
}
方案二:解决判断队满时队列有一位元素为空的情况:***使用size判断队满队空***
-
初始化时:rear=front=0;size=0
-
判断队列已满的条件:size=MaxSize
-
判断队列为空的条件:size=0(队满和队空时候Q.rear==Q.front)
// 方案二
#define MaxSize 10
typedef struct{
ElemType data[MaxSize];
int front,rear;
int size; // 队列当前长度
}SqQueue;
方案三:***使用tag变量:每次删除操作成功时,令tag=0;插入成功时候,令tag=1***(只有删除时候才有可能导致队列变空,只有插入操作采用可能导致队列变满)
-
初始化时:rear=front=0;tag=0
-
判断队列已满的条件:rear=front&&tag=1
-
判断队列为空的条件:rear=front&&tag=0
队列的链式存储
队列的链式存储实际上是一个带有队头指针和队尾指针的单链表(带/不带头结点),与单链表类似,带头结点的操作更方便。
链式存储的结构;
// 链式存储
typedef struct LinkNode{ // 链式队列结点
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct{ // 链式队列
LinkNode *front,*rear; // 链式队列的队头和队尾指针
}LinkQueue;
带头结点的操作和不带头结点的队列在初始化、判空、入队、出队等操作有所区别:
带头结点
// 带头结点初始化
void InitQueue(LinkQueue &Q){
//初始化时队头指针front、队尾指针rear都指向头结点
Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode));
Q.front->next=NULL;
}
// 带头结点判空操作
bool InEmpty(LinkQueue Q){
if(Q.rear==Q.front)
return true;
else
return false;
}
// 带头结点入队操作
void EnQueue(LinkQueue &Q,ElemType x){
LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
s->data=x;
s->next=NULL;
Q.rear->next=s; // 新节点插入到rear之后
Q.rear=s; // 修改队尾指针
}
// 带头结点的元素出队
bool DeQueue(LinkQueue &Q,ElemType &x){
if(Q.front==Q.rear) //队列为空
return false;
LinkNode *p=Q.front->next;
x=p->data;
Q.front->next=p->next;
if(Q.rear==p){ //如果要删除的结点是最后一个结点(头结点除外)
Q.rear=Q.front;
}
free(p);
return true;
}
不带头结点
// 不带头结点初始化
void InitQueue(LinkQueue &Q){
Q.front=NULL;
Q.rear=NULL;
}
// 不带头结点判空操作
bool InEmpty(LinkQueue Q){
if(Q.front=NULL)
return true;
else
return false;
}
// 不带头结点元素入队
void EnQueue(LinkQueue &Q,ElemType x){
LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
s->data=x;
s->next=NULL;
if(Q.front == NULL){ // 如果是队列为空,第一个入队结点操作需要特殊处理
Q.front=s;
Q.rear=s;
}
else{
Q.rear->next=s;
Q.rear=s;
}
}
// 不带头结点的元素出队
bool DeQueue(LinkQueue &Q,ElemType &x){
if(Q.front==NULL)
return false; // 空栈
LinkNode *p=Q.front; // p指向此次出队的元素
x=p->data;
Q.front=p->next; //修改front指针
if(Q.rear==p){ // p是最后一个元素
Q.front=NULL;
Q.rear=NULL;
}
free(p);
return true;
}
双端队列
定义:只允许从两端插入,两端删除的线性表
输出受限的双端队列:只允许在一端插入删除,另一端只允许插入
输入受限的双端队列:只允许在一端插入删除,另一端只允许删除