【计算机考研（408）- 数据结构】栈和队列
登录 / 注册
【计算机考研（408）- 数据结构】栈和队列
美丽新科技BLOG

【计算机考研（408）- 数据结构】栈和队列

刘纪彤
刘纪彤
7月13日发布
0 12 0

栈和队列

栈

一种只允许在一段进行插入或删除操作的[[线性表#什么是线性表|线性表]]。

栈的定义

栈（Stack）是一种只允许在一端进行插入或者删除操作的线性表。它也是一种线性表，但是它限制了其插入和删除操作，相关概念：

  • 栈顶：线性表允许进行插入和删除操作的那一段。
  • 栈底：固定的，不允许进行插入和删除操作的另一端
  • 空栈：没有任何元素的空表

对于栈这个数据结构，可以概括为它是一种进行后进先出操作的线性表（Last In First Out,LIFO）。

栈的基本操作

栈的基本操作可以说和线性表的操作大差不差，同时结合栈自身的操作特性得到其基本操作：初始化一个栈、判断栈是否为空、入栈、出栈、获取栈顶操作、销毁栈，函数名就不多说了，写了这么多一定能写出来的。

栈的数学公式(卡特兰数) :当n个不同元素入栈的时候，出栈元素不同排列个数为$\frac{1}{n+1} C^n_{2n}$ ，我也不知道哪来的，记住!

栈的顺序存储结构

既然栈是一种线性表，那么它必然有两种存储方式：顺序存储/链式存储。

顺序栈的实现

栈的顺序存储结构也称之为顺序栈，他利用地址连续的存储单元存放自栈底到栈顶的数据元素，同时也会附设置值一个栈顶(top)指针来指示当前栈顶元素的位置。

栈的顺序存储结构可以用代码描述为：

#define MaxSize 50 //栈中最大的个数
tyepdef strcut{
    ElemType data[MaxSize];//栈中元素
    int top;//栈顶指针
}SqStack;

在这里：

  • 栈顶指针：S.top 初始时设置为-1，栈顶元素S.data[s.top]；
  • 入栈：判断是否已满，指针+1，再把值赋值给栈顶。
  • 出栈：非空时，先取元素，再-1，同时返回该元素。
  • 判空操作：S.top\=\=-1;
  • 判满操作：S.top\=\=MaxSize-1;

  • 栈的长度：S.top+1;

    当然如果栈顶指针初始值时0的时候，只需要在入栈时，先赋值，再指针加一，出栈时先-1，再返回值，那么栈空和栈满操作都+1就可以了，栈的长度也就是S.top了。
    在严蔚敏的数据结构中会出现S.top和S.base一起出现在栈中，这种情况下判空操作就变为S.top\=\=S.base，当然如果是栈满就可以用S.top-S.base>=S.stacksize来判断。

顺序栈的一些基本操作

下面所有方法以初始栈顶指针为-1为例：

初始化：

void InitStack(SqStack &s);{
    s.top=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+=1//指针先＋1
    s.data[s.top]=x;//再赋值
    /*
    书中++s.top也代表着先自增s.top指针再取值
    */
    return true;
}

出栈

bool Pop(SqStack &s,ElemType &x){
    if(StackEmpty(s)) return false;//判断是否为空栈
    x=s.data[s.top];/先出栈
    s.top-=1;//再减一
    /*书中s.top--同理*/
    return true;
}

获取栈顶元素

bool GetTop(SqStack s,ElemType &x){
    if(StackEmpty(s)) return false;//空
    x=s.data[s.top];
    return true;
}
入栈/出栈操作要注意s.top指针是从-1开始还是从0开始。

共享栈

共享栈是指两个栈共享一块数组空间，那么根据栈的特性，很容易想到这块空间应当是栈底在这个数组空间两端，栈顶相向而行。

设置数组有MaxSize个元素，也就是说这个数组的有效下标从0到MaxSize-1，意味着呢，top0\=\=-1时代表着0号栈为空，top1\=\=MaxSize代表1号栈为空，如果top1-top0 \=\= 1的时候代表栈满，0号栈的操作和上面的类似，1号栈与其正好反过来

共享栈优点就是两个栈空间可以相互调节。

栈的链式存储结构

代码描述如下：

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LiStack;

简直就是跟单链表一个样，没错就是一个样子的。

我们可以设置一个head结点指向链表头结点，以后无论什么操作，都限定只能对表头进行操作，这样也体现了栈的后进先出的特性。

队列

队列（Queue）是只允许在一端进行插入，在另一端删除的线性表

队列的定义

队列（Queue）是只允许在一端进行插入，在另一端删除的线性表。它也是一种线性表，但是它限制了其插入和删除操作，相关概念：

  • 队头 ：允许删除的一端，又叫队首
  • 队尾： 允许插入的一端
  • 空队列：不含任何元素的空表

对于队列这个数据结构，可以概括为它是一种进行先进先出操作的线性表（First In First Out,FIFO）。

队列的基本操作

队列的基本操作可以说和线性表的操作大差不差，同时结合队列自身的操作特性得到其基本操作：初始化一个队列、判断队列是否为空、入队、出队、获取队头元素、销毁队列，函数名就不多说了，写了这么多一定能写出来的。

队列的顺序存储结构

他利用地址连续的存储单元存放自队头到队尾的数据元素，同时也会设置一个队头(front)指针来指示队头元素位置，一个队尾(rear)指针来指示当前队尾元素（也有的教材指向队尾的下一个位置）位置。

#define MaxSize 50 //队列中最大的个数
typedef struct{
    ElemType data[MaxSize];//队列中元素
    int front;//队头指针
    int rear;//队尾指针
}SqQueue;

这里：

  • 队头指针：S.front 初始时设置为0，队头元素S.data[s.front]；
  • 队尾指针：S.rear 初始时设置为0，队尾
  • 元素S.data[s.rear]；
  • 入队：判断是否已满，先把值送到队尾元素，再+1。
  • 出队：非空时，先取元素，再+1，同时返回该元素。
  • 判空操作：S.front\=\=S.rear;
  • 判满操作：S.rear\=\=MaxSize;
  • 队列长度：S.rear-S.front;
当然如果队尾指针初始值是-1的时候就要另行再论了，他可能需要先+1再赋值。这个需要自行判断。

顺序队列的一些基本操作

初始化：

void InitQueue(SqQueue &q){
    q.front=0;
    q.rear=0;
}

判空：

bool QueueEmpty(SqQueue q){
    if(q.front==q.rear) return true;//空
    else return false;//不空
}

入队：


bool EnQueue(SqQueue &q,ElemType x){
    if(q.rear==MaxSize) return false;//满
    q.data[q.rear]=x;//先赋值
    q.rear+=1;//再指针+1
    return true;
}

出队：

bool DeQueue(SqQueue &q,ElemType &x){
    if(QueueEmpty(q)) return false;//判断是否为空队列
    x=q.data[q.front];//先出队
    q.front+=1;//再+1
    return true;
}

获取队头元素:

bool GetHead(SqQueue q,ElemType &x){
    if(QueueEmpty(q)) return false;//空
    x=q.data[q.front];
    return true;
}
针对判断是否满的操作，有这样一个疑问，q.rear==MaxSize代表着队列满吗？答案是不一定。如下面的图示。md1e9aqd.png
本图d中虽然只有一个元素，但是q.rear\=\=MaxSize，这时入队出现了上溢，但这种溢出不是真正的溢出，我们仍可以存放元素，所以为了解决这个问题，引入了[[栈和队列#循环队列|循环队列]]的概念。

循环队列

为了解决提到的假溢出问题，提高存储空间的利用率，我们把顺序队列臆想成为一个环形结构。当队首指针Q.front==Maxsize-1后再前进一个位置到达0，这种操作可以用模运算，也就是Q.front=(Q.front+1)%Maxsize来表示。

循环队列的一些基本操作:

判空与之前一样，还是Q.front==Q.rear。

入队:

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;//再指针+1
    return true;
}

出队:

bool DeQueue(SqQueue &q,ElemType &x){
    if(QueueEmpty(q)) return false;//判断是否为空队列
    x=q.data[q.front];//先出队
    q.front=(q.front+1)%MaxSize;//再+1
    return true;
}
补充：区分队空还是队满的三种处理方式:
牺牲一个单元来区分队空或者队满。入队时少用一个单元，约定以队首指针在队尾指针的下一个位置时尾队满，也就是(Q.rear+1)%MaxSize==Q.front代表队满，Q.front==Q.rear代表队空。
增加size数据成员变量，入队时size++，出队时size--，size==0时队空，size==MaxSize时队满。两种情况都满足Q.front==Q.rear。
增设一个标志位，如果删除成功就置0，插入成功就置1。如果Q.front==Q.rear且标志位为0代表队空，标志位为1代表队满。

队列的链式存储结构

队列的链式表示又称为链式队列。他是一个同时具有队首指针和队尾指针的单链表，队首指针指向队头结点，队尾指针指向队尾结点。接下来我只写代码，就不多赘述了。

定义：

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;//链表结点

typedef struct{
    LinkNode *front,*rear;
}LinkQueue;//链式队列

创建队列：

void InitQueue(LinkQueue &q){
    q.front=q.rear=(LinkNode *)malloc(sizeof(LinkNode));//建立一个头结点
    q.front->next=NULL;
}

判空

bool QueueEmpty(LinkQueue q){
    if(q.front==q.rear) return true;//空
    else return false;//不空
}

入队：

bool EnQueue(LinkQueue &q,ElemType x){
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));//新建一个结点
    s->data=x;//赋值
    s->next=NULL;//新结点的next指向NULL
    q.rear->next=s;//将新结点接到队尾
    q.rear=s;//更新队尾指针
    return true;
}

出队：

bool DeQueue(LinkQueue &q,ElemType &x){
    if(QueueEmpty(q)) return false;//判断是否为空队列
    LinkNode *p=q.front->next;//指向队头结点
    x=p->data;//先出队
    q.front->next=p->next;//将队头结点的next指向下一个结点
    if(q.rear==p) q.rear=q.front;//如果出队的是队尾结点，更新队尾指针
    free(p);//释放队头结点
    return true;
}

双端队列

双端队列：只允许从两端插入、两端删除的线性表

双端队列的定义

双端队列：只允许从两端插入、两端删除的线性表

针对双端队列的不同应用场景，又分为以下：

输入受限的双端队列：只允许从一端插入、两端删除的线性表
输出受限的双端队列：只允许从两端插入、一端删除的线性表

栈和队列的应用及考点

罗列几个以后可能会考到的考点，慢慢补

栈的括号匹配

栈的表达式求值

栈在递归中的应用

队列在层次遍历中的作用

队列在操作系统的应用

双端队列的输出序列问题

数据结构
喜欢就支持一下吧
点赞 0 分享 收藏
版权属于：刘纪彤
本文链接：https://www.mlxkj.xyz/index.php/archives/149/
作品采用《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
评论 抢沙发
OωO
取消