关于数据结构:数据结构-03-栈和队列

从数据结构角度看，栈和队列也是线性表，其特殊性在于 栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因而，可称为限定性的数据结构。但从数据类型角度看，它们是和线性表大不相同的两类重要的抽象数据类型。因为它们广泛应用在各种软件系统中，因而在面向对象的程序设计中，它们是多型数据类型。

栈（stack）是限定仅在表尾进行插入或删除操作的线性表。因而，对栈来说，表尾端有其非凡含意，称为栈顶（top），相应地，表头端称为栈底（bottom）。不含元素的空表称为空栈。

假如栈 \(S=(a_1,a_2,\cdots,a_n)\)，则称 \(a_1\) 为栈底元素，\(a_n\) 为栈顶元素。栈中元素按 \(a_1,a_2,\cdots,a_n\) 的秩序进栈，退栈的第一个元素应为栈顶元素。即栈的批改是按后进先出的准则进行的，因而，栈又称为 后进先出（last in first out）的线性表（简称 LIFO 构造）。

栈的抽象数据类型定义如下：

ADT Stack {数据对象：D = {ai | ai ∈ ElemSet, i = 1, 2, ..., n}
    数据对象: R1 = {<a_{i-1}, ai> | a_{i-1}, ai ∈ D, i = 2, 3, ..., n}
        约定 an 端为栈顶，a1 端为栈底
    基本操作:
        InitStack(&S)
            操作后果: 结构一个空栈 S
        DestroyStack(&S)
            初始条件: 栈 S 存在
            操作后果: 销毁栈 S 
        StackEmpty(S)
            初始条件: 栈 S 存在
            操作后果: 若栈 S 为空栈，则返回 TRUE，否则返回 FALSE
        StackLenght(S)
            初始条件: 栈 S 存在
            操作后果: 返回栈 S 的元素个数
        GetTop(S, &e)
            初始条件: 栈 S 存在且非空
            操作后果: 用 e 返回栈 S 的栈顶元素
        Push(&S, e)
            初始条件: 栈 S 存在
            操作后果: 插入新元素 e 为栈 S 的新的栈顶元素
        Pop(&S, &e)
            初始条件: 栈 S 存在且非空
            操作后果: 删除栈 S 的栈顶元素，并用 e 返回其值
        StackTraverse(S, visit())
            初始条件: 栈 S 存在
            操作后果: 从栈底到栈顶顺次对栈 S 中每个元素调用函数 visit()。一旦 visit() 失败，则操作失败
} ADT Stack

和线性表相似，栈也有两种存储示意形式。

程序栈，即栈的顺序存储构造是利用一组地址间断的存储单元顺次寄存自栈底到栈顶的数据元素，同时附设指针 top 批示栈顶元素在程序栈中的地位。通常的习惯做法是以 top=0 示意空栈；另一方面，因为栈在应用过程中所需最大空间的大小很难预计，因而，一般来说，在初始化设空栈时不应限定栈的最大容量。一个较正当的做法是：先为栈调配一个根本容量，而后在利用过程中，当栈的空间不够应用时再逐段扩充。为此，可设定两个常量：STACK_INIT_SIZE（存储空间初始调配量）和 STACKINCREMENT（存储空间调配增量），并以下述类型阐明作为程序栈的定义。

typedef struct {
    SElemType * base;
    SElemType * top;
    int stacksize;
} SqStack;

其中，stacksize 批示栈的以后可用最大容量。

栈的初始化操作为：按设定的初始调配量进行第一次存储调配，base 可称为栈底指针，在程序栈中，它始终指向栈底的地位，若 base 的值为 NULL，则表明栈构造不存在。称 top 为栈顶指针，其初值指向栈底，即 top=base 可作为栈空的标记，每当插入新的栈顶元素时，指针 top 增 1；删除栈顶元素时，指针 top 减 1，因而，非空栈中的栈顶指针始终在栈顶元素的下一个地位上。

// 栈基本操作的局部算法形容
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;
} // InitStack
Status GetTop(SqStack S, SElemType &e) {
  // 若栈不空，则用 e 返回 S 的顶栈元素，并返回 OK；否则返回 ERROR
  if(S.top == S.base) return ERROR;
  e = *(S.top - 1);
  return OK;
} // GetTop
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
Status Pop(SqStack &S, SElemType &e) {
    // 若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK；否则返回 ERROR
    if(S.top == S.base) return ERROR;
    e = *--S.top;
    return OK;
} // Pop

和栈相同，队列（queue）是一种 先进先出（first in first out，缩写为 FIFO）的线性表。它只容许在表的一端进行插入，而在另一端删除元素。

在队列中，容许插入的一端叫队尾（rear），容许删除的一端叫队头（front）。在队列 \(q=(a_1,a_2,\cdots,a_n)\) 中，\(a_1\) 时队头元素，\(a_n\) 时队尾元素，队列中元素依照 \(a_1,a_2,\cdots,a_n\) 的程序进入，推出队列也只能依照这个程序顺次退出。

队列的抽象数据类型定义如下：

ADT Queue {数据对象: D = {ai | ai ∈ ElemSet, i = 1, 2, ..., n, n ≥ 0}
    数据关系: R1 = {<a_{i-1}, ai> | a_{i-1}, ai ∈ D, i = 2,..., n}
        约定其中 a1 为队头元素，an 为队尾元素
    基本操作:
        InitQueue(&Q)
            操作后果: 结构一个空队列 Q
        DestroyQueue(&Q)
            初始条件: 队列 Q 已存在
            操作后果: 销毁队列 Q
        ClearQueue(&Q)
            初始条件: 队列 Q 已存在
            操作后果: 将 Q 清为空队列
        QueueEmpty(Q)
            初始条件: 队列 Q 已存在
            操作后果: 若 Q 为空队列，则返回 TRUE，否则返回 FALSE
        GueueLength(Q)
            初始条件: 队列 Q 已存在
            操作后果: 返回 Q 的元素个数，即队列的长度
        GetHead(Q, &e)
            初始条件: 队列 Q 已存在
            操作后果: 若队列不空，则用 e 返回 Q 的队头元素，并返回 OK；否则返回 ERROR
        EnQueue(&Q, e)
            初始条件: 队列 Q 已存在
            操作后果: 插入新元素 e 为 Q 的新的队尾元素
        DeQueue(&Q, &e)
            初始条件: 队列 Q 已存在
            操作后果: 若队列不空，则删除 Q 的队头元素，用 e 返回其值，并返回 OK；否则返回 ERROR
        QueueTraverse(Q, visit())
            初始条件: 队列 Q 已存在
            操作后果: 从队头到队尾顺次对 Q 的每个元素调用函数 visit()。一旦 visit() 失败，则操作失败
} ADT Queue

除了栈和队列外，还有一种限定性数据结构是 双端队列（deque）。双端队列是限定插人和删除操作在表的两端进行的线性表。这两端别离称做端点 1 和端点 2。在理论应用中，还能够有输入受限的双端队列（即一个端点容许插人和删除，另一个端点只容许插人的双端队列）和输出受限的双端队列（即一个端点容许插人和删除，另一个端点只容许删除的双端队列）。而如果限定双端队列从某个端点插人的元素只能从该端点删除，则该双端队列就变质为两个栈底相邻接的栈了。只管双端队列看起来仿佛比栈和队列更灵便，但实际上在应用程序中远不迭栈和队列有用。

和线性表相似，队列也能够有两种存储示意。

用链表示意的队列简称为 链队列。一个链队列显然须要两个别离批示队头和队尾的指针（别离称为头指针和尾指针）能力惟一确定。这里，和线性表的单链表一样，为了操作不便起见，给链队列增加一个头结点，并令头指针指向头结点。由此，空的链队列的裁决条件为头指针和尾指针均指向头结点。

链队列的操作即为单链表的插入和删除操作的非凡状况，只需批改尾指针或头指针。

// 单链队列的存储构造
typedef struct QNode {
    QElemType data;
    struct QNode *next;
} QNode, *QueuePtr;
typedef struct {
    QueuePtr front; // 队头指针
    QUeuePtr rear;  // 队尾指针
} LinkQueue;

// 基本操作的局部算法形容
Status InitQueue(LinkQueue &Q) {
    // 结构一个空队列
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if (!Q->front) exit(OVERFLOW);  // 存储调配失败
    Q.front->next = NULL;
    return OK;
}
Status DestroyQueue(LinkQueue &Q) {
    // 销毁队列 Q
    while (Q.front) {
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
    return OK;
}
Status EnQueue(LinkQueue &Q, QElemType e) {
    // 插入元素 e 为 Q 的新的队尾元素
    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, QElemType &e) {
    // 若队列不空，则删除 Q 的队头元素，用 e 返回其值，并返回 OK；否则返回 ERROR
    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;
}

留神：在上述模块的算法形容中，应留神删除队列头元素算法中的非凡状况。个别状况下，删除队列头元素时仅需批改头结点中的指针，但当队列中最初一个元素被删后，队列尾指针也失落了，因而需对队尾指针从新赋值（指向头结点）。

循环队列是一种非凡的队列，它的队头和队尾指针能够在队列的存储空间上造成一个环，从而使得队列的存储空间能够反复利用。指针和队列元素之间的关系不变。

循环队列的判空和判满条件为：

队空条件：front == rear
队满条件：(rear + 1) % MAXSIZE == front

其中，MAXSIZE 为循环队列的最大容量。

循环队列的入队和出队操作如下：

Status EnQueue(CirQueue &Q, QElemType e) {
    // 插入元素 e 为 Q 的新的队尾元素
    if ((Q.rear + 1) % MAXSIZE == Q.front) return ERROR; // 队列满
    Q.data[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXSIZE;
    return OK;
}
Status DeQueue(CirQueue &Q, QElemType &e) {
    // 若队列不空，则删除 Q 的队头元素，用 e 返回其值，并返回 OK；否则返回 ERROR
    if (Q.front == Q.rear) return ERROR; // 队列空
    e = Q.data[Q.front];
    Q.front = (Q.front + 1) % MAXSIZE;
    return OK;
}

Reference：

严蔚敏 / 吴伟民《数据结构（C 语言版）》

关于数据结构:数据结构-03-栈和队列

1 栈

1.1 抽象数据类型栈的定义

1.2 栈的示意与实现

2 队列

2.1 抽象数据类型队列的定义

2.2 链队列

2.3 循环队列