数据结构(第三章)——栈与队列

文章目录

一、栈

栈的基本定义

  1. 定义:只允许在一段进行插入或者删除操作的线性表(先进后出——LIFO:Last In First Out)

    栈的逻辑结构与普通的线性表相同,数据运算(插入、删除操作)有区别

  2. 重要术语:

    • 栈顶:允许插入和删除的一端(最上边的元素——栈顶元素)
    • 栈底:不允许与插入和删除的一端(最下边的元素——栈底元素)
    • 空栈:不包含任何元素
  3. 基本操作:

    1. InitStack(&S);——初始化栈:构建一个空栈S,分配内存空间(创建)
    2. DestoryStack(&L);——销毁栈:销毁并释放栈S说占用的内存空间(销毁)
    3. Push(&S,x);——进栈:若栈S未满,则将x加入使之成为心栈顶(增)
    4. Pop(&S,&x);——出栈:若栈S非空,则弹出栈顶元素,并用x返回(删)
    5. Getop(S,&x);——读栈顶元素:若栈S非空,则用x返回栈顶元素(查:大多只访问栈顶元素)
    6. StackEmpty(S);——判断S是否为空:若S为空,则返回true,否则返回false

顺序栈的实现

//顺序栈的定义
#define MaxSize 10 // 定义栈中元素最大个数
typedef struct{
	ElemType data[MaxSize]; // 静态数组存放栈的数据元素
	int top;  //栈顶指针
}SqStack;

top指针的两种指示方式:

  1. top指针指向栈顶元素,空栈时指向-1——入栈时候:Top指针首先+1,然后再让新元素入栈;出栈时候:元素先出栈,然后top指针-1
  2. 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;

二、队列

  1. 定义:只允许在一端进行插入,另一端删除的线性表(先进先出FIFO)——操作受限的线性表

  2. 重要术语:

    • 队头:允许删除的一端
    • 队尾:允许插入的一端
    • 空队列:不包含数据元素
  3. 操作:

    1. InitQueue(&Q);——初始化队列:构造一个空队列
    2. DestoryQueue(&Q);——销毁队列:销毁并释放队列Q所占用的内存空间
    3. EnQueue(&Q,x);——入队:若队列Q未满,将x加入,使之成为新的队尾
    4. DeQueue(&Q,&x):——出队:若队列Q非空,删除队头元素,并用x返回
    5. GetHead(Q,&x);——读队头元素:若队列Q非空,则将队头元素赋值给x(查:队列中大多数只访问队头元素)
    6. 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;
}

双端队列

定义:只允许从两端插入,两端删除的线性表
数据结构(第三章)——栈与队列

输出受限的双端队列:只允许在一端插入删除,另一端只允许插入
数据结构(第三章)——栈与队列

输入受限的双端队列:只允许在一端插入删除,另一端只允许删除
数据结构(第三章)——栈与队列

上一篇:go-实现一个队列queue


下一篇:数组模拟环形队列的思想