数据结构复习(2)

接（1）的内容,原文参考链接
https://blog.csdn.net/m0_37568814/article/details/81288756

3.栈和队列

A.栈
限定仅在表尾进行插入或者删除操作的线性表。
有以下应用：数制转换，括号匹配的检验，行编辑程序，迷宫求解，表达式求值，递归实现。

• 栈的基本操作
  在栈顶进行插入或删除，栈的初始化、判空及取栈顶元素等。
  入栈口诀：堆栈指针top “先压后加”
  出栈口诀：堆栈指针top “先减后弹”
  top=0表示空栈。

• 栈的表现与实现
  1)构造一个空栈S

  Status InitStack(SqStack &S)
    {
        S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof(SElemType));
        if(!S.base) exit (OVERFLOW); //存储分配失败
            S.top = S.base;
            S.stacksize = STACK_INIT_SIZE;
            return OK;
    }

  2)返回栈顶元素

  Status GetTop(SqStack S, SElemType e) 
    {//若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR
         if(S.top == S.base) return ERROR;
         e = *(S.top-1);
         return OK; 
    }//GetTop

  3)顺序栈入栈函数PUSH（）

  Status Push(SqStack &S, SElemType e)
  { //插入元素e为新的栈顶元素
    if(S.top-S.base>=S.stacksize)//栈满，追加存储空间
   {
    s.base = (SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
    if(!S.base) exit(OVERFLOW);//存储分配失败
    S.top = S.base + S.stacksize;
    S.stacksize += STACKINCREMENT;
    }
    *S.top++ =e;
    return OK:
  }//PUSH

  4)顺序栈出栈函数POP()

  status Pop( SqStack &S,SElemType &e)
  { //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK,否则返回ERROR
    if(S.top == S.base) return ERROR; 
    e=* —S.top;
    return OK;
  }

B.队列
是一种先进先出的线性表，只允许在一端插入，另一端删除。允许插入的一端为队尾，允许删除的一端为队头。
另：除了栈和队列外，还有一种限定性数据结构是双端队列。双端队列是限定插入和删除操作在表的两端进行的线性表。

• 链队列
  示意图
  
  链队列结点类型定义：

  typedef Struct QNode{
     QElemType        data;     //元素
     Struct   QNode   *next;  //指向下一结点的指针
    }Qnode , * QueuePtr ;

  链队列类型定义：

  typedef  struct {
     QueuePtr     front ; //队首指针
     QueuePtr     rear ; //队尾指针
  }  LinkQueue;

总结