数据结构03-栈和队列

很多时候都需要将表作为某个暂时存储的容器,此时就需要频繁地添加或删除表中的元素。

然而,线性表的插入或删除需要线性时间,显然不适合频繁修改。链表的修改虽然需要只需要常数级时间,但是涉及内存的动态分配、指针的调整等,操作还是有些复杂。

本节介绍栈和队列的概念,栈和队列可以看作特殊的线性表,它们主要简化了插入或删除的操作,使得这一过程非常高效,很适合用于密集的调整操作。

栈的概念

(stack)是限制插入和删除都只能在一个位置上进行的表,该位置是表的末端,又称为栈顶(top)。下图列出了栈的概念:

对栈的基本操作有入栈(push)和出栈(pop),前者向栈内添加一个元素,后者向栈内移除一个元素。从图中可以看出,栈的特点是后添加的元素必须先被移除后,才能处理前面添加的元素,因此栈有时又被称为后进先出(last in first out, LIFO)表。

栈需要有一个栈顶指针实时指示栈顶的位置,对栈元素的访问及修改等操作都通过栈顶指针来实现。当元素入栈或出栈时,栈顶指针也相应被改变。一般来说,栈顶指针不能轻易被改变,因此栈顶指针指向的元素是唯一的可见元素。

栈可以使用许多形式实现,首先来看最简单的数组实现方式。

栈的数组实现

数组实现避免了直接使用指针,是更加简单且应用广泛的解决方案。这种方式的唯一缺点是需要提前声明一个数组的大小。

用数组实现下,每一个栈结构需要有一个成员 topptr ,用于指示栈顶在数组中的哪一个位置。对于空栈而言,它的值一般是是 -1 或 0 。下图展示了栈的数组实现模型:

根据以上介绍,栈的数组实现的结构定义为:

typedef struct {
    int size;
    int topptr;
    elemtype* body;
} stack;

#define STACK_NULLTOP (0)

数组实现下,栈的入栈和出栈操作分别如下:

为了将某个元素压入栈中,需要将栈顶位置上移一层,然后置栈的栈顶位置为入栈元素。相应的实现为:

bool Stack_IsFull(stack* s) {
    return s->topptr >= s->size - 1;
}
status Stack_Push(elemtype value, stack* s) {
    if (Stack_IsFull(s))
        return 1;  // stack full
    s->body[++s->topptr] = value;
    return 0;
}

由于数组的容量总是有限的,因此需要先判断栈是否已满。如果在栈已满的情况下继续入栈,将不可避免地发生栈顶越界,可能会与其余部分的数据发生冲突。因此对栈应该小心操作。

为了弹出栈元素,直接让栈顶位置下移一层即可:

bool Stack_IsEmpty(stack* s) {
    return s->topptr == STACK_NULLTOP;
}
status Stack_Pop(stack* s) {
    if (Stack_IsEmpty(s))
        return 1;  // stack empty
    s->topptr--;
    return 0;
}

同样,为了防止栈顶越界,需要提前判断栈是否为空。

入栈和出栈不仅以常数级别的时间实现,而且以非常快的时间运行。大部分机器上都支持寄存器的自增和自减寻址功能,因此栈顶位置移动一层只需要一条机器指令就能实现,入栈也只需要额外执行一次数组的索引赋值即可。

栈舍弃了查找与遍历等操作,实现了非常高效的修改操作。因此,栈是计算机中一种非常基本的数据结构。在大部分机器上甚至内存就是一个栈,可以使用寄存器对内存做入栈和出栈操作,执行效率非常高。

一个影响栈运行效率的因素在于错误检测。对空栈的出栈和对满栈的入栈都会引起数组越界从而导致程序出错。由于这个原因,在某些外部条件确保不会发生溢出的情况下,或在栈的底层实现中,经常会省略处理条件检测。

出栈是一种很有意思的操作,因为它不涉及数据的改变,只需要调整栈顶指针即可。下一次入栈操作时,该元素就会被覆盖,达到删除效果。因此,清空栈只需要将栈顶指针重新置于栈底即可:

void Stack_Clear(stack* s) {
    s->topptr = STACK_NULLTOP;
}

该操作不需要改动任何元素,可以以常数级,并且是非常快的常数级时间完成。

返回栈顶元素可以通过读取栈在栈顶指针位置的元素实现。出栈操作有时也需要读取弹出的元素,其实现就是读取栈顶和出栈的叠加:

elemtype Stack_PopTop(stack* s) {
    if (!Stack_IsEmpty(s))
        return s->body[s->topptr--];
    /* stack empty */
    return 0;  // return value to avoid warning
}

此过程中可能出现栈空的情况,但无法通过返回值提示栈已空,只能通过控制台提示或强制中断代码的执行。

栈的链表实现

由于栈是一个表,因此任何实现表的方式都能实现栈,链表也不例外。如果不能分配一个合理的数组空间,那么更好的方法还是使用链表来实现栈。

这种栈的实现下,测试栈是否是空栈的方式与测试链表是否为空的实现相同,并且栈几乎没有长度限制,无需判断栈是否已满:

bool Stack_IsEmpty(stack s) {
    return s->next == NULL;
}

入栈和出栈在栈的链表实现下的具体操作分别为:

入栈通过向链表开始端添加新的节点实现:

status Stack_Push(stack s, elemtype value) {
    linkedlist_node* cell = malloc(sizeof(linkedlist_node));
    if (cell == NULL)
        return 1;  // stack (memory) full
    cell->elem = value;
    cell->next = s->next;
    s->next = cell->next;
    return 0;
}

出栈通过移除链表开始端的首个节点实现:

status Stack_Pop(stack s) {
    stack first;
    if (Stack_IsEmpty(s))
        return 1;
    first = s->next;
    s->next = s->next->next;
    free(first);
    return 0;
}

链表实现下,入栈和出栈的操作依赖于内存的重新分配,不仅速度较慢,在许多机器上需要依赖操作系统的行为,因此链表实现的栈并不能作为计算机的基本数据结构。

链表实现栈的特点是首节点本身不动,且代表栈顶。下图展示了这一思想:

因此,返回栈顶元素通过检查链表的首节点的值实现:

elemtype Stack_Top(stack s) {
    if (!Stack_IsEmpty(s))
        return s->next->elem;
    /* empty stack */
    return 0;  // return to avoid warning
}

链表实现下,出栈后栈的位置无法被重新利用,因此需要显式回收。清空链表的操作需要通过不断执行出栈操作实现,而不能直接修改栈顶指针:

status Stack_Clear(stack s) {
    if (s == NULL)
        return 1;  // not created
    else
        while (!Stack_IsEmpty(s))
            Stack_Pop(s);
}

该操作需要消耗线性时间。考虑到链表的操作更加复杂,因此使用链表实现栈并不是一种很实用的做法。

队列

队列的概念

栈具有后入先出的特性,这意味着先入栈的元素往往得不到优先处理。该特性在一些倒序处理时很实用,然而在顺序处理元素时却无能为力。

通过对栈原理的思考,可以做一些修改而得到队列的概念。类似于栈,队列(queue)也是一个表。然而,队列的插入操作在一端进行,而删除操作在另一端进行。因此队列是先入先出(first in first out, FIFO)的,在保持栈的优点下可以顺序处理元素。

队列的基本操作是入队(enqueue)和出队(dequeue)。入队是在表的末端,即队尾(rear)处插入一个元素;而出队则删除表的第一个元素,即队首(front)处的元素。

下图展示了一个队列的模型:

同样地,队列可以由数组或链表实现。不过数组的实现较为常用,因此这里只介绍队列的数组模型。

队列的实现

下图展示了数组模型下,处于中间状态的一个队列:

队列两端的元素有着不确定的值。特别地,队列前面的元素曾经属于该队列。

采用以下结构定义实现队列:

typedef struct {
    int size;
    int front;
    int rear;
    int length;
    elemtype* body;
} queue;

这里需要一个成员 length 来记录实际存在队列中的元素个数。

通过队列的类型声明,测试一个队列为空或已满的方法是很容易的:

bool Queue_IsEmpty(queue* q) {
    return q->length == 0;
}
bool Queue_IsFull(queue* q) {
    return q->length == q->size;
}

队列的操作细节和栈比较相似。为了使一个元素入队,让队尾后移,并将元素放入队尾后更新队列长度。

为了使一个元素出队,置队首元素为返回值,然后让队首后移并更新长度。

这种实现的问题在于入队和出队时队列会不断后移(而不是像栈一样栈顶在上上下下的过程中达到平衡),造成队列空间一直向后压缩。当多次入队后,队尾到达的数组的边界,那么下一次入队就会发生队列溢出。

一种简单的解决方法可以参考循环链表的思想,即只要队首或队尾到达数组尾端,它就绕回数组开头,形成循环结构。其实现为:

static int Queue_Succ(queue* q, int pos) {
    if (++pos == q->size)
        pos = 0;
    return pos;
}

如果 frontrear 增 1 使得超越了数组,那么其值重置为数组的第一个位置,否则可以放心增 1 。实现绕回并不需要多少附加代码,不过它会使开销变大。如果能保证入队的次数不会大于队列长度,那么没必要使用回绕。

关于队列的循环实现,还需要注意:

  • 检测队列为空或为满非常重要,因为在循环实现下虽然不会发生数组溢出,但是当队首和队尾相邻时,队列自身可能发生交叉,致使自身被自身覆盖
  • 队首和队尾可能有多种表示方法,例如当队列为空时,队首和队尾可能在同一个单元,也可能在相邻单元,这两种情况下队列的长度计算方式不同

这里采用后一种实现,即队首和队尾在相邻单元。和栈一样,为了清空队列,只需要将位置 frontrear 修改到合适的位置,并将队列大小置 0 即可,并不需要对队列中的元素作任何改动:

void Queue_Clear(queue* q) {
    q->length = 0;
    q->front = 0;
    q->rear = 1;
}

该操作也可用于初始化队列。

根据以上对队列操作的介绍,入队和出队的操作分为为:

入队:让队尾在逻辑上后移,并将元素放入队尾后更新队列长度,代码实现为:

status Queue_Enqueue(queue* q, elemtype value) {
    if (Queue_IsFull(q))
        return 1;  // queue full
    q->length++;
    q->rear = Queue_Succ(q, q->rear);
    q->body[q->rear] = value;
}

这里的后移是一种逻辑上的后移,因为队列底层是由循环数组支持的,其位置的改变由相应的函数决定。

出队的操作为,置队首元素为返回值,然后让队首后移并更新长度。一般情况下都需要对出队元素做一定处理,否则栈就够用了:

elemtype Queue_Dequeue(queue* q) {
    int elem;
    if (Queue_IsEmpty(q)) {
        /* queue empty */
        return 0;  // return to avoid warning
    }
    q->length--;
    elem = q->body[q->front];
    q->front = Queue_Succ(q->front, q);
    return elem;
}

循环实现下,队列可以在无需移动元素的基础上,不断操作队列两端的元素,使得插入和删除都有着常数级且很快的效率。但也正因如此,队列的维护不像栈那么简单,无法得到计算机底层的直接支持。

队列相比栈,更适合用于处理生活问题。因为在生活情景下,许多问题都需要优先处理先到达的项,并且在处理时随时可能有新的项到达。

京ICP备2021034974号
contact me by hello@frozencandles.fun