A01-栈和队列

自学笔记：《数据结构与算法基础》-第1篇——栈和队列（基于C语言）

一、基本概念

栈

  • 栈(Stack)：一种特殊的线性表，限定仅在一端（表尾）进行插入和删除操作的线性表。
  • 表尾(an端)称为栈顶(Top)，表头(a1)称为栈底(Base)，插入元素到栈顶的操作称为入栈，删除栈顶最后一个元素称为出栈，入 = 压入 = Push，出 = 弹出 = Pop
  • 逻辑结构：同线性表相同，一对一关系
  • 存储结构：顺序栈、链式栈
  • 运算规则：后进先出(LIFO)

队列

  • 队列(Queue)：一种特殊的线性表，限定仅在一端(表尾)进行插入操作，在另一端(表头)进行删除操作的线性表(头删尾插)。
  • 表尾(an端)称为队尾，表头a1端称为队头，插入元素称为入队，删除元素称为出队
  • 逻辑结构：同线性表相同，一对一关系
  • 存储结构：顺序队(循环顺序队列更常见)、链队
  • 运算规则：先进先出(FIFO)

二、抽象数据类型

栈

\small \color {rgb(70,130,180)}{ADT \ Stack}｛
\small \quad \color {rgb(255,99,71)}{数据对象：} \quad \color{rgb(70,130,180)}{D = ｛a_i \,|\, a_i \in ElemSet, \ i=1,2,...,n, \ n \geq 0｝}
\small \quad \color {rgb(255,99,71)}{数据关系：} \quad \color{rgb(70,130,180)}{R_1 = ｛<a_{i-1} \,,\, a_i> |\, a_{i-1},a_i \in D, \ i=2,...,n｝}
\qquad \qquad \qquad \small \color {rgb(70,130,180)}{约定a_n端为栈顶，a_1端为栈底}
\small \quad \color {rgb(255,99,71)}{基本操作：} \quad \color{ rgb(70,130,180)}{ 初始化、进栈、出栈、取栈顶元素等}
\small ｝\color {rgb(70,130,180)}{ADT \ Stack}

基本操作
  1. 初始化顺序栈:InitStack(*S)
    操作结果：构造一个空栈S。
  2. 销毁顺序栈：DestroyStack(*S)
    初始条件：栈S已存在。
    操作结果：栈S被销毁。
  3. 清空顺序栈：ClearStack(*S)
    初始条件：栈S已存在。
    操作结果：将S清为空栈。
  4. 判断是否为空栈：StackEmpty(S)
    初始条件：栈S已存在。
    操作结果：若栈S为空栈，则返回TRUE，否则FALSE。
  5. 求栈的长度：StackLength(S)
    初始条件：栈S已存在。
    操作结果：返回S的元素个数，即栈的长度。
  6. 入栈操作：Push(*S,e)
    初始条件：栈S已存在。
    操作结果：插入元素e为新的栈顶元素。
  7. 出栈操作：Pop(*S,*e)
    初始条件：栈S已存在且非空。
    操作结果：删除S的栈顶元素an，并用e返回其值。
  8. 取栈顶元素：GetTop(S,*e)
    初始条件：栈S已存在且非空。
    操作结果：用e返回S的栈顶元素。

队列

\small \color {rgb(70,130,180)}{ADT \ Queue}｛
\small \quad \color {rgb(255,99,71)}{数据对象：} \quad \color{rgb(70,130,180)}{D = ｛a_i \,|\, a_i \in ElemSet, \ i=1,2,...,n, \ n \geq 0｝}
\small \quad \color {rgb(255,99,71)}{数据关系：} \quad \color{rgb(70,130,180)}{R_1 = ｛<a_{i-1} \,,\, a_i> |\, a_{i-1},a_i \in D, \ i=2,...,n｝}
\qquad \qquad \qquad \small \color {rgb(70,130,180)}{约定a_1端为队列头，a_n端为队列尾}
\small \quad \color {rgb(255,99,71)}{基本操作：} \quad \color{rgb(70,130,180)}{初始化、入队、出队、取队头元素等}
\small ｝\color {rgb(70,130,180)}{ADT \ Queue}

基本操作
  1. 初始化队列:InitQueue(*Q)
    操作结果：构造一个空队列Q。
  2. 销毁队列：DestroyQueue(*Q)
    初始条件：队列Q已存在。
    操作结果：队列Q被销毁。
  3. 清空队列：ClearQueue(*Q)
    初始条件：队列Q已存在。
    操作结果：将Q清为空队列。
  4. 判断是否为空队列：QueueEmpty(Q)
    初始条件：队列Q已存在。
    操作结果：若队列Q为空队列，则返回TRUE，否则FALSE。
  5. 求队列的长度：QueueLength(Q)
    初始条件：队列Q已存在。
    操作结果：返回Q的元素个数，即队列的长度。
  6. 入队列操作：EnQueue(*Q,e)
    初始条件：队列Q已存在。
    操作结果：插入元素e为新的队尾元素。
  7. 出队列操作：DeQueue(*Q,*e)
    初始条件：队列Q已存在且非空。
    操作结果：删除Q的队头元素an，并用e返回其值。
  8. 取队头元素：GetHead(Q,*e)
    初始条件：队列Q已存在且非空。
    操作结果：用e返回Q的队头元素。

三、栈的C语言表示和实现

栈的顺序表示

  • 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，栈底一般在低地址端。附设top指针，指向栈顶元素在顺序栈中的位置，附设base指针，指向栈底元素在顺序栈中的位置
  • 为了方便操作，通常top指向栈顶元素之后的下标地址。用stacksize表示栈可使用的最大容量
  • 空栈：base == top，栈空标志；栈满：top-base == stacksize，栈满标志
  • 栈满时的处理方法：
    1. 报错，返回操作系统。
    2. 分配更大的空间，作为栈的存储空间，将原栈内容移入新栈

顺序栈的实现

//数据结构与算法分析-栈-顺序实现
#include<stdio.h>
#include<stdlib.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1  //不可实现
#define OVERFLOW -2  //溢出

#define MAXSIZE 100  //长度

typedef int value;  //返回值类型
typedef int status;  //返回状态类型
typedef int elemtype;  //元素类型

typedef struct
{
    elemtype *base;  //栈底指针
    elemtype *top;  //栈顶指针
    int stacksize;  //栈可用最大容量
}SqStack;

status initstack(SqStack *s);  //顺序栈的初始化
status stackempty(SqStack s);  //判断栈是否为空
value stacklength(SqStack s);  //返回顺序栈长度
status clearstack(SqStack s);  //清空顺序栈
status destroystack(SqStack *s);  //销毁顺序渣
status push(SqStack *s,elemtype e);  //入栈
status pop(SqStack *s,elemtype *e);  //出栈

int main()
{
    printf("\n测试\n");
//  system("pause");
    return 0;
}
status initstack(SqStack *s)
{
    s->base = (elemtype*)malloc(MAXSIZE*sizeof(elemtype));
    if(!s->base)
        exit(OVERFLOW);
    s->top = s->base;
    s->stacksize = MAXSIZE;
    return OK;
}
status stackempty(SqStack s)
{
    if(s.top == s.top)
        return TRUE;
    else
        return FALSE;
}
value stacklength(SqStack s)
{
    return s.top-s.base;
}
status clearstack(SqStack s)
{
    if(s.base)
        s.top = s.base;
    return OK;
}
status destroystack(SqStack *s)
{
    if(s->base)
    {
        free(s->base);
        s->stacksize = 0;
        s->base = NULL;
        s->top = NULL;
    }
    return OK;
}
status push(SqStack *s,elemtype e)
{
    if(s->top - s->base == s->stacksize)
        return ERROR;
    *s->top++ = e;  //*(s->top)=e;s->top++;
    return OK;
}
status pop(SqStack *s,elemtype *e)
{
    if(s->top == s->base)
        return ERROR;
    *e = *--s->top;  //--s->top;*e = *s->top;
    return OK;
}

栈的链式表示

  • 使用数组作为顺序栈存储方式的特点：简单、方便、但易产生溢出（数组大小固定）
  • 上溢(overflow):栈已经满，又要压入元素；下溢（underflow）：栈已经空，还要弹出元素
    注：上溢是一种错误，使问题的处理无法进行；而下溢一般认为是一种结束条件，即问题处理结束。
  • 链表的头指针就是栈顶；不需要头结点；基本不存在栈满的情况；空栈相当于头指针指向空

链栈的实现

//数据结构与算法分析-栈-链式实现
#include<stdio.h>
#include<stdlib.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1  //不可实现
#define OVERFLOW -2  //溢出

#define MAXSIZE 100  //长度

typedef int value;  //返回值类型
typedef int status;  //返回状态类型
typedef int elemtype;  //元素类型

typedef struct StackNode
{
    elemtype data;
    struct StackNode *next;
}StackNode,*LinkStack;

status initstack(LinkStack *s);  //链栈初始化
status stackempty(LinkStack s);  //判断链栈是否为空
status push(LinkStack *s,elemtype e);  //入栈
status pop(LinkStack *s,elemtype *e);  //出栈
elemtype gettop(LinkStack s);  //返回链栈栈顶元素

int main()
{
    printf("\n测试\n");
//  system("pause");
    return 0;
}
status initstack(LinkStack *s)
{
    *s = NULL;
    return OK;
}
status stackempty(LinkStack s)
{
    if(s == NULL)
        return TRUE;
    return FALSE;
}
status push(LinkStack *s,elemtype e)
{
    StackNode *p = (StackNode*)malloc(sizeof(StackNode));
    p->data = e;
    p->next = *s;
    *s = p;
    return OK;
}
status pop(LinkStack *s,elemtype *e)
{
    if(s == NULL)
        return ERROR;
    *e = (*s)->data;
    StackNode *p;
    p = *s;
    *s = (*s)->next;
    free(p);
    return OK;
}
elemtype gettop(LinkStack s)
{
    if(s != NULL)
        return s->data;
}

栈与递归

  • 递归：若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的;若一个过程直接地或者间接地调用自己，则称这个过程是递归的过程。
  • 以下三种情况常常用到递归方法：
    1.递归定义的数学函数。2.具有递归特性的数据结构。3.可递归求解的问题。
  • 递归问题——用分治法求解
    分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解。
  • 必备的三个条件：
    1.能够将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的。
    2.可以通过上述转化使问题简化。
    3.必须有一个明确的递归出口，或称递归的边界。
  • 分治法求解递归问题算法的一般形式：
void p(参数表)
{
    if (递归结束条件)  可直接求解步骤;  //------基本项
    else p(较小的参数);  //------归纳项
}
  • 函数调用过程
    调用前，系统完成：
    （1）将实参、返回地址等传递给被调用函数。
    （2）为被调用函数的局部变量分配存储区。
    （3）将控制转移到被调用函数的入口。
    调用后，系统完成：
    （1）保存被调用函数的计算结果。
    （2）释放被调用函数的数据区。
    （3）依照被调用函数保存的返回地址将控制转移到调用函数。
  • 当多个函数构成嵌套调用时：遵循后调用的先返回------栈
    “层次”-函数嵌套
    “递归工作站”-递归程序运行期间使用的数据存储区
    “工作记录”-实参，局部变量，返回地址
  • 递归的优缺点：
    优点：结构清晰，程序易读。
    缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息，时间开销大。
  • 递归->非递归的方法：
    1.（尾递归、单向递归）->变成循环结构。
    2.自用栈模拟系统的运行时栈。
  • 借助栈改写递归
    递归程序在执行时需要系统提供栈来实现。
    仿照递归算法执行过程中递归工作栈的状态变化可写出相应的非递归程序。
    改写后的非递归算法与原来的递归算法相比，结构不够清晰，可读性较差，有的还需要经过一系列优化。
  • 借助栈改写递归的方法（了解）
    （1）设置一个工作栈存放递归工作记录（包括实参、返回地址及局部变量等）。
    （2）进入非递归调用入口（即被调用程序开始处）将调用程序传来的实参和返回地址入栈（递归程序不可以作为主程序，因而可认为初始是被某个调用程序调用）。
    （3）进入递归调用入口：当不满足递归结束条件时，逐层递归，将实参、返回地址及局部变量入栈，这一过程可用循环语句来实现——模拟递归分解的过程。
    （4）递归结束条件满足，将到达递归出口的给定常数作为当前的函数值。
    （5）返回处理：在栈不空的情况下，反复退出栈顶记录，根据记录中的返回地址进行题意规定的操作，即逐层计算当前函数值，直至栈空为止——模拟递归求值过程。

四、队列的C语言表示和实现

队列的表示

  • 建立顺序队列结构为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置（见下述队列标志问题）。
  • 在队尾插入一个元素，rear++；在队头删除一个元素，front++。当front = rear时，队列中没有任何元素，称为空队列。
  • 假上溢现象：
    当rear = MAXSIZE时，队列发生上溢。此时若front = 0，为“真上溢”；但若front\neq0时，为“假上溢”。
    “假上溢”：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间无法重新利用，如图1所示。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。
    图1
  • 解决假上溢的方法：
    1.将队中元素依次向头方向移动。缺点：浪费时间，每移动一次，队中元素都要移动。
    2.将队空间设想成一个循环的表，即分配给队列的m个存储单元可以循环使用，当rear为MAXSIZE时，若向量的开始端空着，又可从头使用空着的空间，当front为MAXSIZE时，也是一样。
    • 引入循环队列：实现方法：模运算%
  • 队列标志问题：
    队空：front == rear，队满：front == rear
    解决方法：
    1.另外设一个标志区别队空，队满。
    2.另设变量，记录元素个数。
    3.少用一个元素空间（常用方法）。
    利用方法3解决，故队尾指针rear指向下一个入队元素的存储位置，而不直接指向队尾。队空：front == rear，队满：(rear+1)%MAXSIZE == front

顺序队列的实现

//数据结构与算法分析-队列-顺序实现
#include<stdio.h>
#include<stdlib.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1  //不可实现
#define OVERFLOW -2  //溢出

#define MAXSIZE 100  //长度

typedef int value;  //返回值类型
typedef int status;  //返回状态类型
typedef int elemtype;  //元素类型

typedef struct
{
    elemtype *base;  //初始化的动态分配空间
    int front;  //"头指针"
    int rear;  //"尾指针"
}SqQueue;

status initqueue(SqQueue *Q);  //顺序队列初始化
value queuelength(SqQueue Q);  //返回顺序队列长度
status enqueue(SqQueue *Q,elemtype e);  //入队
status dequeue(SqQueue *Q,elemtype *e);  //出队
elemtype gethead(SqQueue Q);  //返回队头元素

int main()
{
    printf("\n测试\n");
//  system("pause");
    return 0;
}
status initqueue(SqQueue *Q)
{
    Q->base = (elemtype*)malloc(MAXSIZE*sizeof(elemtype));
    if(!Q->base)
        exit(OVERFLOW);
    Q->front = 0;
    Q->rear = 0;
    return OK;
}
value queuelength(SqQueue Q)
{
    return ((Q.rear-Q.front+MAXSIZE)%MAXSIZE);
}
status enqueue(SqQueue *Q,elemtype e)
{
    if((Q->rear+1)%MAXSIZE == Q->front)
        return ERROR;
    Q->base[Q->rear] = e;
    Q->rear = (Q->rear+1)%MAXSIZE;
    return OK;
}
status dequeue(SqQueue *Q,elemtype *e)
{
    if(Q->front == Q->rear)
        return ERROR;
    *e = Q->base[Q->front];
    Q->front = (Q->front+1)%MAXSIZE;
    return OK;
}
elemtype gethead(SqQueue Q)
{
    if(Q.front!=Q.rear)
        return Q.base[Q.front];
}

链式队列的实现

//数据结构与算法分析-队列-链式实现
#include<stdio.h>
#include<stdlib.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1  //不可实现
#define OVERFLOW -2  //溢出

#define MAXSIZE 100  //长度

typedef int value;  //返回值类型
typedef int status;  //返回状态类型
typedef int elemtype;  //元素类型

typedef struct Qnode
{
    elemtype data;
    struct Qnode *next;
}Qnode,*QueuePtr;
typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

status initqueue(LinkQueue *Q);  //链式队列初始化
status destroyqueue(LinkQueue *Q);  //销毁链式队列
status enqueue(LinkQueue *Q,elemtype e);  //入队
status dequeue(LinkQueue *Q,elemtype *e);  //出队
status gethead(LinkQueue Q,elemtype *e);  //返回队头元素

int main()
{
    printf("\n测试\n");
//  system("pause");
    return 0;
}
status initqueue(LinkQueue *Q)
{
    Q->rear = (QueuePtr)malloc(sizeof(Qnode));
    Q->front = Q->rear;
    if(!Q->front)
        exit(OVERFLOW);
    Q->front->next = NULL;
    return OK;
}
status destroyqueue(LinkQueue *Q)
{
    Qnode *p;
    while(Q->front)
    {
        p = Q->front->next;
        free(Q->front);
        Q->front = p;
    }
    return OK;
}
status enqueue(LinkQueue *Q,elemtype e)
{
    Qnode *p = (QueuePtr)malloc(sizeof(Qnode));
    if(!p)
        exit(OVERFLOW);
    p->data = e;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
    return OK;
}
status dequeue(LinkQueue *Q,elemtype *e)
{
    if(Q->front == Q->rear)
        return ERROR;
    Qnode *p;
    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 gethead(LinkQueue Q,elemtype *e)
{
    if(Q.front == Q.rear)
        return ERROR;
    *e = Q.front->next->data;
    return OK;
}

参考文献：

  1. https://www.bilibili.com/video/BV1nJ411V7bd?p=62
  2. https://baike.baidu.com/item/%E9%98%9F%E5%88%97/14580481?fr=aladdin
：永远不要忘记提升自己~~
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容