[数据结构] 04 - 1 - 栈和队列

栈和队列是操作受限的线性表。 它们属于线性表的范畴,但是是"受限"的线性表。


4.1 - 栈

一、定义

栈(Stack)是一个【后进先出(LIFO, Last In First Out)】的列表或者集合,它有这样一种限制:插入和删除操作只能从一端进行,称之为栈顶(Top)。

A stack is a Last-In-First-Out (LIFO) list, that is, an ordered list in which insertions and deletions are made at the top only.

最后加入的元素最先出去:就像一个球桶中的网球,最后被放进去的球,在取出时一定是最先被取出的,无法从中间的任意位置取出或插入一个球,除非先取出它上面的所有球

二、栈 ADT

(一)数据对象和数据关系

数据对象

  • 记为 D={a1,a2,…,an}D = \left\{a_{1} , a_{2} , \ldots , a_{n}\right\},其中 n≥0n \geq 0 ;
    • 每个元素 aia_{i} 可以是任意数据类型(如整数、字符、结构体等),具体取决于应用场景;
    • 当 n=0n = 0 时,表示空栈。

数据关系

  • 栈是一种线性结构,元素之间存在一对一的相邻关系。
  • 可表示为:R={⟨ai−1,ai⟩∣i=2,3,…,n}R = \left\{\langle a_{i - 1} , a_{i} \rangle \mid i = 2 , 3 , \ldots , n\right\},即前驱与后继关系;
  • 元素按 a1,a2,…,ana_{1} , a_{2} , \ldots , a_{n}​ 的顺序依次入栈,出栈时只能从 ana_{n} 端进行。
  • 通常 a1a_{1}为栈底(Bottom)元素,ana_{n}​ 为栈顶(Top)元素;

(二)基本操作示例

操作名含义典型函数原型
初始化构造一个空栈InitStack(&S)
判空判断栈是否为空IsEmpty(S)
入栈 / 压栈(Push)在栈顶插入元素Push(&S, e)
出栈 / 弹栈(Pop)删除栈顶元素并返回Pop(&S, &e)
取栈顶读取栈顶元素但不删除GetTop(S, &e)
清空将栈置为空栈ClearStack(&S)
销毁释放栈所占空间DestroyStack(&S)
求长度返回栈中元素个数StackLength(S)

入栈、出栈、取栈顶和判空 4 个主要操作均为 O(1)。

三、实现基本操作(数组)

结构定义:

#define MAXSIZE 100          // 栈的最大容量
#define OK 1
#define ERROR 0
 
typedef int ElemType;        // 元素类型,可按需修改
 
typedef struct {
    ElemType data[MAXSIZE];  // 存放栈元素的数组
    int top;                 // 栈顶指针(下标),空栈时为 -1
} SqStack;

1. 初始化

void InitStack(SqStack *S) {
    S->top = -1;             // 栈顶指针置为 -1,表示空栈
}
  • 数组下标从 0 开始,入栈时先将栈顶加 1 再存入数据,所以从 -1 开始。

2. 入栈

必须考虑数组填满的情况,即发生溢出的情况:

  • 在数组长度不足时,我们可以返回一个错误信息;
int Push(SqStack *S, ElemType e) {
    if (S->top == MAXSIZE - 1) {   // 栈满,上溢
        return ERROR;
    }
    S->data[++S->top] = e;         // 栈顶指针先加 1,再存入元素
    return OK;
}
  • 更好的做法是像动态数组那里讲的一样(3.2.2.2 动态列表),创建一个更大的数组,拷贝数据,然后删除旧数组。

3. 出栈

int Pop(SqStack *S, ElemType *e) {
    if (S->top == -1) {            // 栈空,下溢
        return ERROR;
    }
    *e = S->data[S->top--];        // 先取出栈顶元素,再让指针减 1
    return OK;
}

4. 取栈顶

int GetTop(SqStack *S, ElemType *e) {
    if (S->top == -1) {            // 栈空
        return ERROR;
    }
    *e = S->data[S->top];          // 只读取,不改变栈顶指针
    return OK;
}

四、实现基本操作(链表)

结构定义:

typedef int ElemType;
 
typedef struct StackNode {
    ElemType data;              // 数据域
    struct StackNode *next;     // 指针域
} StackNode, *LinkStack;

LinkStack 为指向栈顶结点的指针。空栈时 LinkStack == NULL。

1. 初始化

void InitStack(LinkStack *S) {
    *S = NULL;                  // 栈顶指针置空,表示空栈
}
  • 数组下标从 0 开始,入栈时先将栈顶加 1 再存入数据,所以从 -1 开始。

2. 入栈

int Push(LinkStack *S, ElemType e) {
    StackNode *p = (StackNode *)malloc(sizeof(StackNode));
    if (p == NULL) {            // 内存分配失败
        return ERROR;
    }
    p->data = e;
    p->next = *S;               // 新结点指向原栈顶
    *S = p;                     // 更新栈顶指针为新结点
    return OK;
}

3. 出栈

int Pop(LinkStack *S, ElemType *e) {
    if (*S == NULL) {           // 栈空
        return ERROR;
    }
    StackNode *p = *S;          // 暂存栈顶结点
    *e = p->data;               // 取出数据
    *S = p->next;               // 栈顶指针下移
    free(p);                    // 释放原栈顶结点
    return OK;
}

4. 取栈顶

int GetTop(LinkStack S, ElemType *e) {
    if (S == NULL) {            // 栈空
        return ERROR;
    }
    *e = S->data;               // 直接读取栈顶结点数据
    return OK;
}

五、栈的应用

参阅【4.1.5 - 栈的应用】
https://salmon-isle.com/archives/2663

这部分的内容较多,所以我将其独立为一篇文章,包括:

  • 用栈的方法反转字符串 / 链表;
  • 用栈检验括号匹配性(检测括号是否成对、是否未发生嵌套);
  • 前缀、后缀、中缀表达式,及其之间的转换(用栈解决);

此外,栈还用于实现任何编辑器中的 Undo 操作。

六、总结

优缺点 / 复杂度:

  • 栈的所有基本操作,时间复杂度均为 O(1)(除链式栈的清空);
  • 顺序栈内存连续、实现简单,但容量较为固定,存在浪费 / 溢出问题;
  • 链式栈不会溢出、容量只受限于内存,但需额外指针域、内存不连续、需要频繁的动态内存分配 / 释放。

4.2 - 队列

一、定义

队列(Queue)是一种先进先出(First In, First Out,FIFO)的列表或者集合,它有这样一种限制:只允许在队尾(rear) 插入,在队头(front) 删除。

A queue is a First-In-First-Out (FIFO) list, that is, an ordered list in which insertions take place at one end and deletions take place at the opposite end.

最先加入的元素最先出去:就和现实中的排队一样。

二、队列 ADT

(一)数据对象和数据关系

数据对象:与线性表一致;

数据关系:数据对象间仍是一对一的线性关系

S={⟨ai,ai+1⟩∣ai,ai+1∈D, i=1,2,…,n−1}S = \{ \langle a_i, a_{i+1} \rangle \mid a_i, a_{i+1} \in D,\ i = 1, 2, \ldots, n-1 \}
  • a₁ 是队头元素,最先入队,也最先出队。
  • aₙ 是队尾元素,最后入队。
  • 新元素只能插在 aₙ 之后(成为新的队尾)。
  • 删除只能删 a₁(删后 a₂ 成为新队头)。

(二)基本操作示例

操作名含义典型函数原型
初始化构造一个空队列InitQueue(&Q)
判空判断队列是否为空QueueEmpty(Q)
入队 (EnQueue)在队尾插入元素EnQueue(&Q, e)
出队 (DeQueue)删除队头元素并返回DeQueue(&Q, &e)
取队头读取队头元素但不删除GetHead(Q, &e)
清空将队列置为空队列ClearQueue(&Q)
销毁释放队列所占空间DestroyQueue(&Q)
求长度返回队列中元素个数QueueLength(Q)

三、实现(数组, 循环队列)

(一)假溢出问题

队列属于线性表,所以也有顺序和链式两种存储方式。如果采用顺序存储的方式:

  • 入队操作只需在队尾追加元素,无需移动任何元素;
  • 但是,出队操作要在队头删除元素,需要移动所有元素,使表首项不为空;

如果允许存在空元素?

  • 可同时维护 head 和 rear 指针来标记队列的首尾位置,即可避免频繁、大量的元素移动;
  • 但是,这会带来尾部超限,但头部仍有很多空元素的情况,造成假溢出。

注:rear 指的是队列最后一个元素的下标 +1,这样方便判断空队列(当 front == rear 的时候,队列就为空)。并且队列的长度就是 rear - front。

(二)循环队列定义

  • 解决假溢出的方法就是后面满了,就再从头开始,形成头尾相接的循环。
  • 我们把队列这种头尾相接的顺序存储结构称为循环队列。

从刚才的例子继续:若 rear 超限,则移动到下标为 0 处从头开始

入队 a6 和 a7 后,rear 就与 head 指针重合

首尾指针重合,产生了新问题:如何判断此时的队列究竟是空还是满呢?

  • 【办法一】设置标志变量 flag,为 true 时队列满,为 false 时队列空;
  • 【办法二】当数组中只剩一个空闲单元时,就认为队列满了,即不允许右图的情况发生。即 (rear + 1) % QueueSize == front。

(三)循环队列实现

1. 存储结构定义

typedef int QElemType; // 假设为 int
 
typedef struct
{
    QElemType data[MAXSIZE];
    int front;
    int rear;
} SqQueue;

2. 初始化

Status InitQueue(SqQueue *Q)
{
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

3. 求队列长度

int QueueLength(SqQueue Q)
{
    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

同时解决了 rear 在 head 前、在 head 后两种情况。

4. 入队(EnQueue)

若队列未满,则插入元素 e 为 Q 新的队尾元素

Status EnQueue(SqQueue *Q, QElemType e)
{
    if ((Q->rear + 1) % MAXSIZE == Q->front)  // 判满
        return ERROR;
    
    // 将元素e赋值给队尾
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAXSIZE;
    return OK;
}

5. 出队(DeQueue)

若队列不空,则删除 Q 中队头元素,用 e 返回其值

Status DeQueue(SqQueue *Q, QElemType *e)
{
    if (Q->front == Q->rear)  // 判空
        return ERROR;
    
    // 将队头元素赋值给 e
    *e = Q->data[Q->front]; 
    Q->front = (Q->front + 1) % MAXSIZE; 
    
    return OK;
}

四、实现(链表, 链式队列)

队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,我们把它简称为链队列

1. 存储结构定义

typedef int QElemType;
 
typedef struct QNode      /* 结点结构 */
{
    QElemType data;
    struct QNode *next;
} QNode, *QueuePtr;       /* QueuePtr 是指向 QNode 的指针 */
 
typedef struct            /* 队列的链表结构 */
{
    QueuePtr front, rear;
} LinkQueue;

2. 初始化

初始化链队列:创建头结点,front 和 rear 都指向头结点

Status InitQueue(LinkQueue *Q)
{
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
    if (!Q->front)
        exit(OVERFLOW);
    
    // 头结点的 next 置空
    Q->front->next = NULL;
    
    return OK;
}

3. 入队

插入元素e为Q的新的队尾元素

Status EnQueue(LinkQueue *Q, QElemType e)
{
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if (!s) 
        exit(OVERFLOW);
        
    s->data = e;
    s->next = NULL;
    // 把拥有元素e的新结点s赋值给原队尾结点的后继
    Q->rear->next = s; 
    
    Q->rear = s; 
    return OK;
}

4. 出队

若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR

Status DeQueue(LinkQueue *Q, QElemType *e)
{
    QueuePtr p;
    if (Q->front == Q->rear)
        return ERROR;
        
    p = Q->front->next; 
    *e = p->data; 
    Q->front->next = p->next;
    
    // 若删空了,则将rear指向头结点,避免rear变成悬空指针
    if (Q->rear == p)
        Q->rear = Q->front;
    free(p);
    return OK;
}

五、总结

优缺点 / 复杂度:

  • 无论循环还是链式队列,其基本操作都是 O(1) 的(除链式队列清空);
  • 但循环队列只在开始申请空间,使用时不释放,时间开销会有细微的差异;
  • 循环队列必须有固定的长度,而链队列则更加灵活。在可确定队列最大长度时,建议用循环队列。无法预估长度时,用链队列。