数据结构（C++）学习篇（六）：线性表（栈和队列）

���荐阅读：

数据结构（C++）学习篇（三）：线性表（链式表示和实现）

数据结构（C++）学习篇（四）：线性表（循环链表）

数据结构（C++）学习篇（五）：线性表（双向链表）-CSDN博客

================================================================

栈和队列定义和特点

定义：线性表的子集，即是插入和删除位置受限的线性表。

特点：限定插入和删除只能在“端点”

• 栈：后进先出 （LIFO结构）
• 队列：先进先出（FIFO结构）

  栈（Stack）相关概念

  1.  表尾：栈顶top；
  2.  表头：栈底base; 
  3.  入栈（push）：插入元素到栈顶（表尾）的操作。
  4.  出栈（pop）：从栈顶（表尾）删除最后一个元素的操作。

  栈示意图

  栈应用案例

  1. 进制转换
  2. 括号匹配
  3. 表达式求值（符号优先算法）

  栈的表示和实现

  1.顺序栈

  1.1 顺序栈定义

  #define MAXSIZE 100typedef struct{    SElemType *base;    SElemType *top;    int stacksize;}SqStack;

  1.2 顺序栈初始化

  //构造一个空栈Status InitStack(SqStack &S){    S.base = new SElemType[MAXSIZE];     //S.base = (SElemType *)malloc(MAXSIZE*sizeof(SEelmType))  C语言        if(!S.base)        return OVERFLOW;    S.top = S.base;    S.stacksize = MAXSIZE; }

  1.3 顺序栈是否为空

  Status StackEmpty(SqStack S){    if(S.top == S.base)  //空？        return TRUE;    esle        return FALSE;}

  1.4 顺序栈的长度

  int StackLength(SqStack S){    return S.top - S.base;}

  1.5 清空顺序栈

  Status ClearStack(SqStack S){    if(S.base) S.top = S.base;    return OK;}

  1.6 销毁顺序栈

  Status DestroyStack(SqStack &S){    if(S.base)    {        delete S.base;        S.stacksize = 0;        S.base = S.top = NULL;       }    return OK;}

  1.7 顺序栈的入栈*

  Status Push(SqStack &S, SElemType e){    if(S.top-S.base == S.stacksize) //栈满        return ERROR;    *S.top++ = e;  //*S.top=e;S.top++;    return OK;}

  1.8 顺序栈的出栈*

  Status Pop(SqStack &S, SElemType &e){    if(S.top==S.base)  return ERROR;        e = *--S.top; //--S.top; e=*S.top;    return OK;}

  2.链式栈

  2.1 链式栈的定义

  • 运算受限的单链表，只能在链表头部（栈顶）进行操作

    特性：

    • 不需要头结点
    • 基本不存在栈满的情况
    • 空栈相当于头指针指向空
    • 插入和删除仅在栈顶处执行

      typedef struct StackNode{    SElemType data;    struct StackNode *next;}StackNode, *LinkStack;LinkStack S;

      2.2 链式栈初始化

      void InitStack(LinkStack &S){    S = NULL;    return OK;}

      2.3 判断链式栈是否为空

      Status StackEmpty(LinkStack S){    if(S == NULL)        return TRUE;    else        return FALSE;}

      2.4 链式栈的入栈*

      Status Push(LinkStack &S, SElemType e){    p = new StackNode;  //生成新结点    p->data = e;            p->next = S;        //插入栈顶    S = p;              //修改栈顶指针    return OK;}

      2.5 链式栈的出栈*

      Status Pop(LinkStack &S, SElemType &e){    LinkStack p=NULL;    if(S==NULL) return ERROR;    e = S->data;    p = S;    S=S->next;    delete p;    return OK;}

      2.6 链式栈元素获取

      SElemType GetTop(LinkStack S){    if(S != NULL)        return S->data;}    

      =====================================================

      队列（Queue）

      • 在表一端插入（表尾），在另一端（表头）删除。

        1.顺序队列

        1.1顺序队列定义

        #define MAXQSIZE 100typedef struct {    QElemType *base;        //初始化动态内存分配    int front;    //头    int rear;     //尾}SqQueue;

        常用：循环队列，使用求模运算实现。

        循环队列解决队满的判断方法之一---少用一个元素空间。

        •         队空：front==rear;
        •         队满： (rear+1)%MAXQSIZE == front;

          1.2 循环队列的初始化

          Status InitQueue(SqQueue &Q){    Q.base = new QElemType[MAXQSIZE];    if(!Q.base)        return OVERFLOW;    Q.front = Q.rear = 0;    return OK;}

          1.3 循环队列的长度

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

          1.4 循环队列入队*

          Status EnQueue(SqQueue &Q, QElemType e){    if((Q.rear+1)%MAXQSIZE == Q.front)  return ERROR;  //队满        Q.base[Q.rear] = e;             //新元素加入队尾    Q.rear = (Q.rear+1) % MAXQSIZE; //队尾指针+1    return OK;}

          1.5 循环队列出队*

          Status DeQueue(SqQueue &Q, QElemType &e){    if(Q.rear == Q.front)          return ERROR;  //队空        e = Q.base[Q.front];    Q.front = (Q.front+1) % MAXQSIZE; //队头指针+1        return OK;}

          1.6 取队头元素

          SElemType GetHead(SqQueue Q){    if(Q.front != Q.rear)        return Q.base[Q.front];}

          2. 链式队列

          2.1 链式队列定义

          #define MAXQSIZE 100typedef struct Qnode{    QElmType data;    struct Qnode *next;}QNode, *QueuePtr;typedef struct{    QueuePtr front;//队头指针    QueuePtr rear;//队尾指针}LinkQueue;

          2.2 链式队列初始化

          Status InitQueue(LinkQueue &Q){    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));    if(!Q.front) return OVERFLOW;    Q.front->next = NULL;    return OK;}

          2.3 链式队列的销毁

          Status DestroyQueue(LinkQueue &Q){    QueuePtr p;    while(Q.front){        p = Q.front->next; //Q.rear = Q.front->next;        free(Q.front);             Q.front = p;       //Q.front = Q.rear;    }    return OK;}

          2.4 链式队列元素e入队

          Status EnQueue(LinkQueue &Q, QElmType e){    QueuePtr p = NULL;    p = (QueuePtr)malloc(sizeof(QNode));    if(!p)        return OVERFLOW;    p->data = e;    p->next = NULL;    Q.rear->next = p;    Q.rear = p;    return OK;}

          2.5 链式队列出队

          Status DeleteQueue(LinkQueue &Q, QElemType &e){    QueuePtr p = NULL;    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;    delete p;    return OK;}

          2.6 链式队列求队头元素

          Status GetHead(LinkQueue Q, QElemType &e){    if(Q.front == Q.rear)        return ERROR;    e = Q.front->next->data;    return OK;}

          文中代码均为手动输入，如有错误，欢迎指正！

          视频：戳这里_B站大学