4.栈和队列

栈和队列

栈和队列的定义和特点

栈的定义和特点

栈（stack）： 是限定仅在表尾（栈顶）进行插入或删除操作的线性表。

栈的表尾端称为 栈顶（top） ，表头端称为 栈尾（bottom） 。

空栈： 不含数据元素的栈

假设栈 S = {a1,a2,a3 ... an}，栈中元素按照 a1,a2,a3 ... an 的顺序进栈，则称 a1 为栈底元素，称 an 为栈顶元素。

栈又称 后进先出（Last In First Out） 的线性表，简称 LIFO 结构 。

栈的插入操作，叫做进栈，也称压栈、入栈。

栈的删除操作，叫做出栈，也称弹栈。

注意： 栈对线性表的插入和删除的位置进行限制，并没有对元素进出的时间进行限制。 这意味着在任何时候的栈顶元素都可以出栈，哪怕是在将所有元素压栈的过程中。比如1、2、3进栈，当1、2进，3没进时，可以选择将2出栈再让3进栈。

队列的定义和特点

队列（queue）： 是只允许在一端进行插入操作，在另一端进行删除操作的线性表。

队列中允许插入的一端称为 队尾 ，允许删除的一端称为 对头 。

队列是一种 先进先出（First In First Out， FIFO）的线性表。

假设栈 q = {a1,a2,a3 ... an}，其中的元素按照 a1,a2,a3 ... an 的顺序进队列并删除，则称 a1 为对头元素，称 an 为队尾元素。

栈的抽象数据类型

ADT 栈 (stack)
Data
    线性表的数据对象为{a1,a2,a3,...,an}，每个数据元素的类型均为 Datatype 。
    与线性表一样，数据元素具有相同的类型，相邻元素之间一对一，除了首尾元素都具有前驱和后继的关系。
Operation
    InitStack(*s)：初始化操作，创建一个空栈
    DestroyStack(*s)：若栈存在，则销毁它
    ClearStack(*s)：若栈存在，则清空它
    StackEmpty(s)：若栈为空，则返回 OK ，否则返回 ERROR 
    GetTop(s, *e)：若栈非空，则通过 e 返回栈顶元素
    Push(*s, e)：若栈非空且未满，则插入 e 到栈 s 内成为栈顶元素
    Pop(*s, *e)：若栈非空，则删除栈 s 中的栈顶元素，并用 e 返回其值
    StackLength(s)：返回栈 s 的长度，即栈的元素个数

栈的顺序存储结构和链式存储结构

栈的顺序存储结构的定义

栈的结构定义①：

#define MAXSIZE 1000 //假设栈长度为 1000
typedef int SElemType; // SElemType 视具体情况而定，这里假设为 int 
typedef struct {
    SElemType data[MAXSIZE];
    int top;  //栈顶元素的数组下标，空表设为 -1 
}SqStack;
定义为①的栈的示意图

栈的结构定义②：

#define MAXSIZE 1000 
typedef int SElemType; 
typedef struct {
    SElemType *top;    //栈顶指针
    SElemType *base;  //栈底指针
    int stacksize;    //栈空间的最大大小
}SqStack;
定义②的栈的示意图

定义②的栈的 top ：当栈为空栈时， top 指向栈底，非空时， top 永远指向栈顶元素的下一个位置。

当使用定义①时，判断空栈的条件是 top == -1 ，为真则栈为空，反之非空。
当使用定义②时，判断空栈的条件是 top == base ，为真则栈为空，反之非空。

栈的顺序存储结构的操作

注意： 以下两个操作都是基于定义①的栈定义

进栈操作 的代码实现：

Status Push(Sqstack *s, SElemType e){
    if(s->top == MAXSIZE - 1)  //判断是否满栈
        return ERROR;
    s->top++;
    s->data[s->top] = e;
    return OK;
}

出栈操作 的代码实现：

Status Pop(Sqstack *s, SElemType *e){
    if(s->top == -1)  //判断是否为空栈
        return ERROR;
    *e = s->data[s->top];
    s->top--;
    return OK;
}

初始化操作 的代码实现：

void InitStack(Sqstack *s){
    s-> = -1;
}

注意： 以下两个操作都是基于定义②的栈定义

进栈操作 的代码实现：

Status Push(Sqstack *s, SElemType e){
    if(s->top - s->base == s.stacksize)  //判断是否满栈
        return ERROR;
    *s->top++ = e; //元素 e 压入栈中，栈顶指针 + 1
}

出栈操作 的代码实现：

Status Pop(Sqstack *s, SElemType *e){
    if(s->top == s->base)  //判断 s 是否为空栈
        return ERROR;
    *e = *--s.top;
    return OK;
}

初始化操作 的代码实现：

void InitStack(Sqstack *s){
    s->base = (Sqstack *)malloc(sizeof(SElemType) * MAXSIZE);
    if(!s->base)
        exit(OVERFLOW);
    s->top = s->base;
    s.stacksize = MAXSIZE;
    return OK;
}

栈的链式存储结构的定义

栈的链式存储结构，简称链栈。

typedef struct StackNode{
    SElemType data;
    struct StackNode *next;
}StackNode, *LinkStackPtr;

typedef struct LinkStack{
    LinkStackPtr top;
    int count;  //元素个数
}LinkStack;

链栈大部分操作都与单链表相似，只是在插入和删除时不太一样。

栈的链式存储结构的操作

初始化操作 的代码实现：

void InitStack(LinkStack *s){
    s->top = NULL;
    s->count = 0;
}

进栈操作 的代码实现：

Status Push(LinkStack *s, ElemType e){
    LinkStackPtr temp = (LinkStackPtr)malloc(sizeof(StackNode));
    temp->data = e;
    temp->next = s->top;
    s->top = temp;
    s->count++;
    return OK;
}

出栈操作 的代码实现：

Status Pop(LinkStack *s, ElemType *e){
    LinkStackPtr p;
    if(StackEmpty(*s))
        return ERROR;
    *e = s->top->data;
    p = s->top;
    s->top = s->top-next;
    free(p);
    s->count--;
    return OK;
}

如果栈的使用过程中元素个数变化不可控，则最好使用链栈；反之使用顺序栈。

栈的作用

栈的引用简化了某些特定的程序设计的问题。好比人类过海开船，去远方坐飞机一样，提高了解决问题的效率。而栈的顺序存储结构相比于数组，不再关注数组的下标的，而是重点关注栈顶。

栈的应用——递归

递归 ：在一个函数、过程或者数据结构定义的内部又直接或间接出现定义本身的应用，则称它们是递归的。

而每一个递归定义都必须至少拥有一个条件： 一个满足该条件时，递归终止，即不再引用自身而是返回值退出，且是按照递归的顺序，反序退出。

例如链表，在定义时，再次调用了自己的定义，所以链表是一种递归的数据结构。

递归和迭代的区别：

  1. 迭代使用的是循环结构，递归使用的是选择结构。
  2. 由于大量的递归函数调用会创建过多的函数副本，所以往往会占据大量的时间和内存。而迭代则不会。
  3. 递归的代码相比迭代更加具有可读性。

因为递归的调用和退出过程很像栈的出栈与入栈，所以 编译器一般都通过栈实现递归函数：

在递归函数的调用过程中，每一次递归都将函数的局部变量、函数形参、以及返回地址压入栈中。在退出时，位于栈顶的局部变量、函数形参、以及返回地址都被弹出。

栈的应用——四则运算表达式求值

逆波兰（Reverse Polish Notation，RPN）表示： 一种不需要括号的后缀表达式，这里的后缀指的是运算符在它的两个运算数字的后面。比如 “9+(3-1)*3+10/2” 表示为 “9 3 1 - 3 * + 10 2 / +”

  1. 计算机如何应用后缀表达式计算出结果：

从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将栈顶两个数字出栈，进行计算并将结果进栈，一直到最终获得结果。

  1. （重）如何把中缀表达式转为后缀表达式：

从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分。
若是符号，则判断其与栈顶符号的优先级：若优先级低于栈顶符号，则栈顶元素依次出栈并输出，并将当前符号进栈；若优先级高于栈顶符号，则将当前符号进栈；若是左括号“(”，则进栈；若是右括号“)”，则将栈内元素依次出栈，直到将“(”出栈为止，但是注意： 左括号和右括号不输出到后缀表达式中 。
若已经到原表达式的最后，则将栈内符号全部输出。

计算机如何处理中缀表达式 最重要的两步：

  1. 将中缀表达式转换为后缀表达式（栈用来进出运算的符号）
  2. 将后缀表达式进行运算得出结果（栈用来进出运算的数字）

队列的定义

队列（queue）： 队列是只允许在一端进行插入操作，在另一端进行删除操作的线性表。

队列是一种 先进先出（First In First Out， FIFO）的线性表。队列中允许插入的一端称为 队尾 ，允许删除的一端称为 对头 。

队列的结构定义：

ADT 队列 (Queue)
Data
    线性表的数据对象为{a1,a2,a3,...,an}，每个数据元素的类型均为 Datatype 。
    与线性表一样，数据元素具有相同的类型，相邻元素之间一对一，除了首尾元素都具有前驱和后继的关系。
Operation
    InitQueue(*Q)：初始化操作，建立一个空队列
    DestroyQueue(*Q)：若队列存在，则销毁它
    ClearQueue(*Q)：若队列存在，则清空它
    QueueEmpty(Q)：若队列为空，则返回 OK ，否则返回 ERROR 
    GetHead(Q, *e)：若队列 Q 存在且非空，则用 e 返回其队头元素
    EnQueue(*Q, e)：若队列 Q 存在，则将 e 插入该队列成为其队尾元素
    DeQueue(*Q, *e)：若队列 Q 存在且非空，则删除其队头元素并用 e 返回其队头元素
    QueueLength(Q)：返回队列 Q 的长度，即队列的元素个数
endADT

循环队列——队列的头尾相接的顺序存储结构

为什么使用循环队列？

如果队列使用常规的顺序存储结构的话，队列头是在数组下标为0的位置，此时入队列操作只需要在队尾插入一个元素即可，时间复杂度为 O(1) 。但是出队列的操作是在队列头操作的，所以每次出队列，除队列后的元素都要向前移一位，用于保证队列头不为空，此时时间复杂度为 O(n) 。

为什么出队列操作中元素全部都要移动呢？而循环队列则是为了解决常规顺序存储结构的入队列操作问题。通过不固定表头在数组首位，再加上两个分别指向首元素 front 和尾元素下一位的下标变量 rear ，即可解决这个问题。

第二个问题：循环队列如何判断队列是否为空？

方法①：设置一个变量 flag ，当 Q->rear == Q->front 和 flag == 0 都为真时，队列非空，反之为空。

方法①

方法②：当队列空时 front == rear 为真，当队列满时 (Q->rear + 1) % MAXSIZE == Q->front 为真，我们修改其条件，令满队列保留一个元素空间不存储数据。

方法②

循环队列的定义

循环队列： 我们把队列的头尾相接的顺序存储结构称为循环队列

注意： 以下的结构定义和操作都是采取方法②

循环队列的结构 定义：

#define MAXSIZE 1000 //队列可能达到的最大长度
typedef int QElemType;

typedef struct {
    QElemType data[MAXSIZE];
    int front;  //队列头元素的下标
    int rear;  //队列头元素的下标；若队列不为空，则为尾元素下一个元素的下标
}SqQueue;

循环队列的初始化操作 代码实现：

Status InitQueue(SqQueue *Q){
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

求循环队列的长度操作 代码实现：

int QueueLength(SqQueue Q){
    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

循环队列的入队列操作 代码实现：

Status EnQueue(SqQueue *Q, QElemType e){
    if ( (Q->rear + 1) % MAXSIZE == Q->front )
        return OK;
    Q->data[Q->rear] = e;  //从队列尾元素入队列
    Q->rear = (Q->rear + 1) % MAXSIZE;  // rear 向后移一位，若到最后则转到数组头部
    return OK;
}

循环队列的出队列操作 代码实现：

Status DeQueue(SqQueue *Q, QElemType *e){
    if ( Q->rear == Q->front )
        return OK;
    *e = Q->data[Q->front];  //用 e 返回队头元素
    Q->front = (Q->front + 1) % MAXSIZE;  // front 向后移一位，若到最后则转到数组头部
    return OK;
}

队列的链式存储结构及其实现

队列的链式存储结构： 其实就是线性表的单链表，只是只能在队头出元素，队尾进元素，简称 链队列 。

为了操作的方便，我们将队头指针 front 指向链队列的头结点，而队尾指针 rear 指向终端结点。同样地，我们 也给链队列添加头结点 ，用于统一和简化某些操作。

当队列为空时， front 和 rear 指针都指向头结点。

空链队列

链队列的结构 代码实现：

typedef int QElemType;  //假设抽象数据类型为 int ，根据实际情况更改
typedef struct QNode{
    QEleType data;
    struct QNode *next;
}QNode, *QueuePtr;

typedef struct {
    QueuePtr front, rear;
}LinkQueue;

链队列的出队列操作 代码实现：

Status DeQueue (LinkQueue *Q, QElemType *e){
    QueuePtr p;
    if(Q->front == Q->rear)
        return ERROR;
    p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if(Q->rear == p)
        Q->rear = Q->front;
    free(p);
    return OK;
}

链队列的入队列操作 代码实现：

Status EnQueue (LinkQueue *Q, QElemType e){
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if( !s )
        exit(OVERFLOW);
    s->data = e;
    s->next = NULL;
    Q->rear->next = s;
    Q->rear = s;
    return OK;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 199,830评论 5赞 468
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 83,992评论 2赞 376
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 146,875评论 0赞 331
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 53,837评论 1赞 271
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 62,734评论 5赞 360
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,091评论 1赞 277
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,550评论 3赞 390
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,217评论 0赞 254
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,368评论 1赞 294
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,298评论 2赞 317
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,350评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,027评论 3赞 315
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,623评论 3赞 303
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,706评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,940评论 1赞 255
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,349评论 2赞 346
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 41,936评论 2赞 341

推荐阅读更多精彩内容

  • 4.栈和队列--大话数据结构
    1.栈 定义：是限定仅在表尾进行插入和删除操作的线性表，我们允许插入和删除的一端称为栈顶(top)，另一端称为端底...
    小李同学今天博学了吗阅读 121评论 0赞 1
  • 数据结构学习—栈和队列
    1、栈的定义 ​ 栈是限定仅在表尾进行插入和删除操作的线性表。我们把插入和删除的一段称为栈顶，另一端称...
    先弓阅读 737评论 0赞 1
  • 4.数据结构--栈与队列
    首先需要介绍栈和队列与线性表的关系栈：栈是限定在表尾进行插入和删除的线性表队列：队列是只允许在一段进行插入操作，在...
    梁炜东阅读 392评论 0赞 2
  • 栈和队列
    栈和队列是两种应用非常广泛的数据结构，它们都来自线性表数据结构，都是“操作受限”的线性表。 栈 栈(Stack)：...
    karlsu阅读 635评论 0赞 1
  • 11. 山有乔松隰有龙，不见子充见狡童
    黑色的海岛上悬着一轮又大又圆的明月，毫不嫌弃地把温柔的月色照在这寸草不生的小岛上。一个少年白衣白发，悠闲自如地倚坐...
    小水Vivian阅读 3,090评论 1赞 5