数据结构-栈和队列

栈的顺序存储结构

特点:利用一组地址连续的存储单元存放自栈底到栈顶的数据元素,同时附加一个指针(top)指示当前栈顶的位置

0.顺序栈的类型描述

1
2
3
4
5
#define MaxSize 50
typedef struct{
Elemtype data[MaxSize];
int top;
}SqStack;

1.初始化操作

目标:初始化一个空的顺序栈

1
2
3
Void InitStack(SqStack &stack){
stack.top=-1;//初始化栈顶指针
}

2.判空操作

目标:判断当前栈是否为空栈,若是返回TRUE,否则返回FALSE

1
2
3
4
5
6
int StackEmpty(SqStack stack){
if(stack.top==-1)//栈空
return TRUE;
else
return FALSE;
}

3.进栈操作

目标:向顺序栈中插入一个元素

1
2
3
4
5
6
int Push(SqStatck &stack,ElemType x){
if(stack.top)==MaxSize-1)//栈满,报错
retrun FALSE;
stack.data[++stack.top]=x//指针先加1再入栈
return TRUE;
}

WARNING

当初始化时stack.top=0;此时入栈代码变为stack.data[stack.top++]=x; 此时栈判空代码变为if(stack.top==0)

此时栈判满代码变为if(stack.top==MaxSize)

4.出栈操作

目标:从顺序栈中弹出一个元素

1
2
3
4
5
6
int Pop(SqStack &stack,ElemType &x){
if(stack.top==-1)//栈空
return FALSE;
x=stack.data[stack.top--];//先出栈指针再减1
return TRUE;
}

WARNING

当初始化时stack.top=0;此时出栈代码变为x=stack.data[--stack.top];

5.读栈顶元素

目标:当前顺序栈中栈顶的元素,并用引用变量x返回

1
2
3
4
5
6
int GetTop(SqStack stack,ElemType &x){
if(stack.top=-1)//栈空
return FALSE;
x=stack.data[stack.top];//x记录栈顶元素
return TRUE;
}

WARNING

当初始化时stack.top=0;此时读栈顶元素代码变为x=stack.data[stack.top-1];

共享栈

定义:利用栈底位置相对不变的特性,可以让两个顺序栈共享一个一维数据空间,将两个栈的栈底分别设置共享空间的两端,两个栈顶向共享空间的中间延伸

0号栈判空:top0==-1

1号栈判空:top1==MaxSize

栈满:top1-top0==1

0号栈进栈 top0先加一再赋值

1号栈进制top1先减一再赋值

0号栈出栈先取值再top0减一

1号栈出栈先取值再top1加一

优点:更有效的利用存储空间,两个栈空间相互调节只有整个存储空间被占满才发生上溢

栈的链式存储

特点:使用线性表的链式存储即单链表表示栈

0.链式栈的类型描述

1
2
3
4
typedef struct StackNode{
ElemType data;
struct StackNode *next;
}StackNode,*LinkStack;

队列

定义:只允许在一端进行插入操作,而在另一端进行删除操作的线性表

  • 队头:线性表只允许删除的那一端
  • 队尾:只允许进行插入的那一端
  • 空队列:不含任何元素的空表

注意:

  1. 队列本质是线性表,是操作受限的线性表
  2. 线性表可以有空表,队列也有空队列
  3. 插入:入队、出队
  4. 删除:出队
  5. 队列的操作特性:先进先出(FIFO)

队列的顺序存储

特点:分配一块连续的存储单元存放队列中的元素,并附设两个指针frontrear分别指示队头元素和队尾元素的位置

0.顺序队列的类型描述

1
2
3
4
5
#define MaxSize 50
typedef struct{
ElemType data[MaxSize];
int front,rear;
}SqQueue;
  • 初始状态:Q.front==Q.rear==0
  • 进队操作:队不满时,先赋值再Q.rear++;
  • 出队操作:队不空时,先取值再Q.front++;

循环队列

把顺序队列从逻辑上看成一个环,成为循环队列

  • 初始时:Q.rear=Q.front=0;

  • 入队时:Q.rear=(Q.rear+1)%MaxSize

  • 出队时:Q.front=(Q.front+1)%MaxSize

  • 队列长度:(Q.rear-Q.front+MaxSize)%MaxSize

  • 判空:if(Q.rear==Q.front)

  • 判满:if(Q.rear==Q.front)

    • 判空和判满重复!!改进:

      • 牺牲一个存储单元来区分队空还是队满

        队空:Q.front==Q.rear

        队满: (Q.rear+1)%MaxSize==Q.front

        队中元素个数: (Q.rear-Q.front+MaxSize)%MaxSize

      • 增设一个记录当前数据元素的变量Q.size

        队空:Q.size==0

        队满:Q.size==MaxSize

        队中元素个数:Q.size

      • 增设tag变量,记录最后一次操作是插入还是删除

        tag=0,表示最后一次操作是删除

        tag=1,表示最后一次操作是插入

        队空:if(Q.front==Q.rear&&tag==0)

        队满:if(Q.front==Q.rear&&tag==1)

        队中元素个数: (Q.rear-Q.front+MaxSize)%MaxSize

1.初始化

目标:初始化一个循环队列

1
2
3
void InitQueue(SqQueue &Q){
Q.rear=Q.front=0;//初始化队首、队尾指针
}

2.判队空

目标:判断给定队列是否为空,若空返回TRUE,否则返回FALSE

1
2
3
4
5
6
int QueueEmpty(SqQueue Q){
if(Q.rear==Q.front)//队空条件(使用方法一改进循环队列)
return TRUE;
else
return FALSE;
}

3.入队

目标:向循环队列入队一个元素,若入队失败返回FALSE,若入队成功返回TRUE

1
2
3
4
5
6
7
8
9
#define TURE 1
#define FALSE 0
int 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;
}

4.出队

目标:从循环队列出队一个元素,若出队失败返回FALSE,若出队成功返回TRUE,并引用变量x返回出队元素

1
2
3
4
5
6
7
8
9
#define TURE 1
#define FALSE 0
int DeQueue(SqQueue &Q,ElemType &x){
if((Q.rear==Q.front)//队空(使用方法一改进循环队列)
return FALSE;
x=Q.data[Q.front];
Q.front=(Q.front+1)%MaxSize;//后移循环队列队头指针
return TRUE;
}

队列的链式存储

特点:使用链表来表示队列

0.链式队列的类型描述

1
2
3
4
5
6
7
8
typedef struct QNode{
ElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
  • 链队列本质是一个同时带队头指针和队尾指针的单链表
  • 判空:if(Q.front==Q.rear)

1.初始化

目标:初始化一个带头结点的链式队列

1
2
3
4
void InitQueue(LinkQueue &Q){
Q.front=Q.rear=(QNode *)malloc(sizeof(QNode));
Q.front->next=NUll;
}

2.判队空

目标:判断队列是否为空,若空返回TRUE,否则返回FALSE

1
2
3
4
5
6
int QueueEmpty(LinkQueue Q){
if(Q.front==Q.rear)
return TRUE;
else
return FALSE;
}

3.入队

目标:向链式队列中入队一个元素x

1
2
3
4
5
6
7
void EnQueue(LinkQueue &Q,ElemType x){
s=(QNode *)malloc(sizeof(LinkNode));
s->data=x;
s->next=NULL;
Q.rear->next=s;
Q.rear=s;
}

4.出队

目标:从链式队列中出队一个元素,若出队失败返回FALSE,成功返回TRUE,并用引用变量x保持出队元素

1
2
3
4
5
6
7
8
9
10
11
int DeQueue(LinkQueue &Q,ElemType &x){
if(Q.front==Q.rear)
return FALSE;
p=Q.front->next;
x=p->data;//保存出队元素
Q.front->next=p->next;//修改头结点指针
if(Q.rear=P)//额外处理仅有一个元素时的Q.rear指针
Q.rear=Q.front;
free(p);//释放已出队结点
return TRUE;
}

双端队列

特点:允许两端都进行入队和出队操作的队列,元素的逻辑结果仍是线性结构

  • 输出受限的双端队列

    • 允许在一端进行插入删除,但在另一端只能插入的双端队列
  • 输入受限的双端队列

    • 允许在一端进行插入删除,但在另一端只能删除的双端队列

END


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!