栈和队列

我们以下的使用的栈或队列都是作为一个工具来解决其他问题的，我们可以把栈或队列的声明和操作写的很简单，而不必分函数写出。

• 顺序栈
  1. 声明一个栈并初始化：

    ElemType stack[maxSize];    //存放栈中的元素
    int top = -1;   //栈顶指针（指向栈顶元素）

  1. 元素进栈：

    stack[++top] = x;

  1. 元素出栈：

    x = stack[top--];

  1. 判断栈空:

    top == -1;  //栈空
    top > -1;   //栈非空

• 顺序队列
  1. 声明一个队列并初始化：

    ElemType queue[maxSize];    //存放队列中元素
    int front = -1, rear = -1;  //队头（指向队头元素的前一个位置），队尾（指向队尾元素）

  1. 元素入队：

    queue[++rear] = x;

  1. 元素出队：

    x = queue[++front];

  1. 判断队空:

    front == rear;  //队空
    front < rear;   //队非空

栈

卡特兰(Catalan)数：\(1/(n+1)C^n_{2n}\)
应用：对于n个不同元素进栈，出栈序列的个数为\(1/(n+1)C^n_{2n}\)

顺序栈

• 基本概念：
  采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针(top)指向当前栈顶的位置。

• 存储结构：

#define MaxSize 50      //定义栈中元素的最大个数
typedef struct {
    ElemType data[MaxSize]; //存放栈中元素
    int top;    //栈顶指针
}SqStack;       //Sequence Stack

• 基本操作：
  • 栈顶指针：S.top，初始时设置S.top=-1；（即 指向了栈顶元素）
  • 栈顶元素：S.data[S.top]；
  • 进栈操作：栈不满是，栈顶指针先加1，再送值到栈顶元素；
  • 出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1；
  • 栈空条件：S.top == -1；
  • 栈满条件：S.top == MaxSize-1；
  • 栈长：S.top+1

共享栈

• 基本概念：
  利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数据空间，将两个站的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。

• 基本操作：
  • 栈空条件：
    • 0号栈：top0=-1
    • 1号栈：top1=MaxSize

  • 栈满条件：top1 - top0 = 1(即 当两个栈顶指针相邻时栈满)

  • 进栈操作：
    • 0号栈：top0先加1再赋值
    • 1号栈：top1先减1再赋值
  • 出栈操作：栈非空时，
    • 0号栈：先取栈顶元素值，再将top0减1；
    • 1号栈：先取栈顶元素值，再将top1加1

链栈

• 基本概念：
  采用链式存储的栈称为链栈，通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。

• 存储结构：

typedef struct LinkNode {
    ElemType data;  //数据域
    struct LinkNode *next;  //指针域
}*LiStack;  //List Stack

• 优点：
  便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。便于结点的插入与删除。

队列

顺序队列

• 基本概念：
  队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针front和rear分别指向队头元素和队尾元素的位置。（这里队头指针指向队头元素的前一个位置，队尾指针指向队尾元素）（避免队空与队列中只有一个元素时无法区分）

• 存储结构：

#define MaxSize 50      //定义栈中元素的最大个数
typedef struct {
    ElemType data[MaxSize]; //存放队列元素
    int front, rear;        //队头指针和队尾指针
}SqQueue;   //Sequence Queue

• 基本操作：
  • 初始状态；Q.front = -1; Q.rear = -1；
  • 队空条件：Q.front == Q.rear； (因为队头指针指向队头元素的前一个位置，所以当与队尾指针相等时，队空)
  • 进队操作：队不满时，先送值到队尾元素，再将队尾指针加1；
  • 出队操作：队不空时，先取队头元素值，再将队头指针加1。

循环队列

• 基本概念：
  将顺序队列臆造为一个环状的空间，即吧存储队列元素的表从逻辑上视为一个环，称为循环队列。当队首指针Q.front=MaxSize-1后，再前进一个位置就自动到0，利用取余运算(%)。

• 基本操作：
  • 初始时：Q.front = Q.rear = 0；
  • 入队操作：Q.rear = (Q.rear+1)%MaxSize； (在队尾排队)
  • 出队操作：Q.front = (Q.front+1)%MaxSize； (在队头出队)
  • 队列长度：(Q.rear+MaxSize-Q.front)%MaxSize。
  • 出队入队时：指针都按顺时针方向进1

  但是无法区分队空与队满（都为Q.front == Q.rear）

  为了区分队空队满的情况，有三种处理方式：
  1. 牺牲一个单元来区分队空队满，入队时少用一个队列单元。约定以“队头指针在队尾指针的下一位置作为队满的标志”
     • 队满条件：(Q.rear+1)%MaxSize == Q.front；
     • 队空条件：Q.front == Q.rear；
     • 队列中元素的个数：(Q.rear-Q.front+MaxSize)%MaxSize。
  2. 类型中增设表示元素个数的数据成员。
     • 队空条件：Q.size == 0；

     • 队满条件：Q.size == MaxSize。

       这两种情况都有Q.front == Q.rear。

  3. 类型中增设tag数据成员，以区分是队满还是队空。
     • 队空条件：tag == 0时，若因删除导致Q.front == Q.rear，则为队空；
     • 队满条件：tag == 1时，若因插入导致Q.front == Q.rear，则为队满。

链队列

• 基本概念：
  队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表(通常设计成带头结点的单链表，方便操作)。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点（注意与顺序队列不同）。

• 存储结构：

typedef struct LinkNode{//链式队列结点
    ElemType data;      
    struct LinkNode *next;
}LinkNode;

typedef struct {    //链式队列
    LinkNode *front, *rear;     //队列的队头和队尾指针
}LinkQueue;

• 基本操作：
  • 初始化：Q.front = Q.rear = 头结点；
  • 队空条件：Q.front == NULL且Q.rear == NULL;
  • 入队操作：尾插法；
  • 出队操作：删除头。
• 适用性：
  链队列特别适合于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题。
  另外，假如程序中要使用多个队列，与多个栈的情形一样，最好使用链队列，这样就不会出现存储分配不合理和“溢出”的问题。

双端队列

• 基本概念：
  双端队列是指允许两端都可以进行入队和出队操作的队列。

数据结构之栈与队列

原文：https://www.cnblogs.com/blknemo/p/11306065.html