《大话数据结构》之栈与队列

2019-03-11

1. 栈

1.1 定义

栈，即只能在表尾进行插入或删除操作的线性表。

其中，“表尾”称为“栈顶”，另一端则为“栈底”。栈是“后进先出”（LIFO）的线性表。

1.2 栈的顺序存储结构

我们使用数组来描述栈的顺序存储结构。使用指针top来定义栈顶指针，其一直指向数组的最后一个元素的索引。空栈即top为-1。由于使用数组实现，故顺序栈在初始化时需要指定最大存储容量。

1.2.1 入栈

取出数组下一位置的索引（同时更新栈顶top指针），插入数据。

// S为栈（data为保存的数据，top为栈顶指针），e为插入数据，下同
if (S->top == MAX_SIZE - 1) {
    return False;
}
// 栈顶指针后移
S->top += 1;
// 在数组的该位置插入数据
S->data[S->top] = e;
return True;

1.2.2 出栈

取出栈顶top指针指向的数据，之后top指针前移。

if (S->top == -1) {
    // 空栈
    return NULL;
}
// 取出待返回数据
result = S->data[S->top];
// 栈顶指针前移
S->top -= 1;
return result;

入栈、出栈操作的时间复杂度均为O(1)。

1.3 栈的链式存储结构

由于顺序栈仍然需要提前考虑空间的存储问题，我们可以使用“单链表”来实现栈结构。

使用“头插法”实现链栈的“入栈”和“出栈”操作，可以有效降低时间复杂度。

对于链栈来说，空栈即栈顶指针top=NULL。

1.3.1 入栈

入栈操作，类似于单链表的插入操作，直接在链表头部进行。

// S为栈（top为栈顶指针，count为元素数量），e为插入数据结点（data为数据域，next为指针域），下同
// 新数据的next指向原top指针的节点，并将top指针指向新数据，更新表长
node = ...; // 创建新结点
node->data = e;
node->next = S->top;
S->top = node;
S->count += 1;

1.3.2 出栈

出栈操作，类似于单链表的删除操作，直接在链表头部进行。

if (S->count == 0) {
    // 空栈
    return NULL;
}
// 取出待返回的结点
p = S->top; 
// 取出待返回数据
result = p->data;
// 栈顶指针指向后一个结点
S->top = S->top->next;
// 更新表长
S->count -= 1;
// 释放对象
free(p);
return result;

链栈操作的时间复杂度仍然为O(1)。但由于其实际占用的存储空间会大于顺序栈（单链表结点额外包含指针域数据），故可以依情况自行决定使用哪种结构对栈进行实现。

1.4 栈的应用：使用栈进行四则运算

这里我们使用栈（demo中使用链栈进行实现）进行四则运算表达式的求值：

1	9 + ( 3 - 1 ) * 3 + 10 / 2

其中，主要步骤分为两步：

将（操作符）中缀表达式转换为后缀表达式（栈用来进出操作符）：

1	9 3 1 - 3 * + 10 2 / +

使用后缀表达式计算结果（栈用来进出操作数）。

Objective-C版本实现：代码地址。

2. 队列

2.1 定义

队列，即只能在一端进行插入操作，在另一端进行删除操作的线性表。

插入的一端叫做队尾，删除的一端叫做队头。队列是先进先出（FIFO）的线性表。

2.2 队列的顺序存储结构

仍然使用数组对队列进行描述。我们使用两个指针（front和rear）分别指向队头（首个元素）和队尾（末尾元素的下一个索引）。故初始时，front=rear。

2.2.1 顺序队列的入队

入队，即rear指针位置插入新数据，之后rear指针后移。时间复杂度为O(1)。

2.2.2 顺序队列的出队

出队，按标准数组的删除数据逻辑可知，front指针位置数据移除，之后后面的所有数据依次前移。此时算法的时间复杂度为O(n)。

若是不考虑移动元素的问题，则可以在front指向的数据移除后，front指针后移，达到目的且复杂度仍然为O(1)。但此时会造成数据的“假溢出”：在队列存储已满的情况下，插入新数据时无法插入，但队列头部明明有剩余空间却无法使用。

2.3 循环队列

为了解决上述“假溢出”的问题，引入了循环队列这个特殊的顺序存储队列。

2.3.1 定义

队列中，头尾相接的顺序存储结构叫做循环队列。

利用循环队列，在尾部存满之后，如果头部存在剩余空间，可以从头开始继续存储。

2.3.2 循环队列的问题

队列为空时，front=rear。但当队列存满时，仍旧为front=rear。故在使用循环队列时，需要区分开这两种情况。

设置标志位flag：当队列为空时，flag=0；当队列占满时，flag=1。
少存一个数据。即当rear与front差1时，就认为队列已满。

故循环队列最大的问题是如何处理入队与出队操作时的溢出问题。

2.3.3 循环队列的满队及长度判定

对于上面的第二种情况，由于在队列已满时，rear与front的大小不确定（绝对值差1），故可以使用“取模”的方式确定队列是否已满：

1
2
3

if ((rear + 1) % MaxSize == front) {
    // 队列已满
}

而计算队列数据个数时，当rear > front时，队列长度即为rear - front；当rear < front时，队列为两部分：右半部分为QueueSize - front，左半部分为 rear - 0，故总长度为 rear - front + QueueSize。仍旧使用“取模”的方式，故最终队列长度为：

1 2	// 队列总长度 QueueLength = (rear - front + MaxSize) % MaxSize;

2.3.3 循环队列的入队操作

按照循环存储的方式，当队尾已满，但仍有空间可用时，将新元素重新放入到队列头部。

// Q为队列（data为数据数组，rear和front为其头尾指针），e为将入队的新元素，下同
if ((Q->rear + 1) % MaxSize == Q->front) {
    // 队列已满，不可入队
    return False;
}
// 队尾设置数据
Q->data[Q->rear] = e;
// 队尾指针后移（取模，填满后可从头赋值）
Q->rear = (Q->rear + 1) % MaxSize;
return True;

2.3.4 循环队列的出队操作

if (Q->rear == Q->front) {
    // 空队列，不可出队
    return NULL;
}
// e为出队对象
Element e = Q->front;
// 对首指针后移（取模，填满后可从头赋值）
Q->front = (Q->front + 1) % MaxSize;
return e;

2.4 队列的链式存储结构

队列的链式存储结构，本质上就是使用链表实现的队列。最简单的实现就是“单链表”。队首指针front指向链表的头结点，队尾指针rear指向链表的尾部结点。

2.4.1 链式队列的入队

链式队列的入队操作，实质上就是“尾插法”插入结点到单链表中。

// Q为队列（front和rear分别为队列的头尾指针），s为待插入结点（data为数据域，next为指针域），下同
// 创建新结点s
s = ...;
s->data = e;
s->next = NULL;
// 原尾部结点的next指向新结点
Q->rear->next = s;
// 队尾指针指向新结点
Q->rear = s;

2.4.2 链式队列的入队

链式队列的出队操作，实质上就是在链表头部移除首个结点。注意，出队后，若得到空队列，队尾指针rear也应指向链表的头结点。

if (Q->front == Q->rear) {
    // 空队列，不可出队
    return NULL;
}
// 得到当前待出队结点p
p = Q->front->next;
// 获取出队元素
e = p->data;
// 队首指针指向出队结点的下一个结点
Q->front->next = p->next;
if (Q->rear == p) {
    // 判空，若出队后为空队列，则更新队尾指针（均指向单链表的头结点）
    Q->rear = Q->front;
}
free(p);
return e;

2.5 两种存储结构队列的比较

比较两种存储结构的队列的异同，如同比较顺序存储和链式存储的优劣。首先，对于灵活程度来说，链式队列由于无需考虑存储空间的大小，且无需担心数据溢出或空间浪费，而显得更加灵活。但是，由于其单个数据占用空间略大，且创建和释放存在部分消耗，在纯性能上略差于顺序队列。

还是那句话，确定存储空间大小时，使用顺序队列；否则使用链式队列。