栈

先入后出，则称为栈。

结构定义

如果只是用普通的动态数组来实现的话，只需有栈底基地址 base 和预计的最大容量 stacksize，就可以使用 malloc 函数来开辟一片连续的空间了。不过为了实现压栈弹栈等操作，还需要一个指向栈顶元素的指针 top。这样一个顺序栈的类型就定义好了。但顺序栈可用的最大容量 stacksize 是固定的，虽然可以通过 realloc 来动态调整，但这样仍会造成内存的浪费。

栈只是操作受限的线性表，既然线性表可以用链表的方式来存储，那么栈也可以用链表来实现。

因此链栈也不难定义出来了，直接把链表的结构拿来用就好。

顺序栈的类型定义链栈的类型定义

cpp

// 顺序栈
typedef struct {
    SElemType *base; // 栈底基地址
    SElemType *top; // 栈顶指针
    int stacksize; // 栈可用的最大容量
} SqStack;

cpp

// 链栈，其实就是链表
typedef struct LNode {
    SElemType data; // 数据域
    struct LNode *next; // 指针域
} LNode, *LinkStack;

初始化创建

顺序栈的初始化其实就是动态数组的创建，使用 malloc 函数来开辟一片连续的空间，不过由于一开始栈是空的，所以要将栈顶指针 top 指向栈底 base。
而链栈初始化时直接将头指针置空即可，由于栈不需要像链表一样维护一个一直指向链表头部固定不变的头指针，所以就无需头节点多此一举了。

TIP

其实栈的 base 基地址已经做到了链表头指针的功能，而由于链表的头插法中正好实现了先入后出的功能，所以就不需要向顺序栈那样再额外维护一个 top 栈顶指针了。

顺序栈的初始化链栈的初始化

cpp

#define STACK_INT_SIZE 100 // 栈的最大容量

// 初始化栈
int InitStack(SqStack &S) {
    // STACK_INT_SIZE 是之前定义好的常量，表示栈的最大容量
    S.base = (SElemType *)malloc(STACK_INT_SIZE * sizeof(SElemType)); 
    if (!S.base)
        exit(OVERFLOW);
    S.top = S.base; // 栈顶指针指向栈底
    S.stacksize = STACK_INT_SIZE; // 栈的最大容量
    return OK;
}

cpp

// 初始化链栈
int LinkInitStack(LinkStack &S) {
    S = NULL;
    return OK;
}

入栈

也叫做压栈、进栈。

顺序栈入栈的时候第一时间要检查栈是否已满，如果满了就需要用 realloc 函数重新开辟新的内存来创建。如果考虑完这一点，那么入栈操作其实就是普通动态数组的操作：*(S.top++) = e。
链栈的优势在于无需考虑栈的最大容量，实际上就是上一篇链表介绍的头插法，不过不需维护头节点了。头节点的先进后出和栈一模一样。

其实判断顺序栈是否为满也可以封装成一个函数，由于这里展示了具体的细节，后面就不单独封装了。
实际上顺序表中：
判栈满就是 S.top - S.base == S.stacksize。
判栈空就是 S.top == S.base。

顺序栈的入栈链栈的入栈

cpp

#define STACKINCREMENT 10 // 每次栈满时，栈的最大容量增加的量

int Push(SqStack &S, SElemType 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;
}

cpp

// 进栈，其实就是数组的头插法
int LinkPush(LinkStack &S, SElemType e) {
    LinkStack p = (LinkStack)malloc(sizeof(LNode));
    if (!p)
        exit(OVERFLOW);
    p->data = e; // 放数据
    p->next = S; // 放指针
    S = p; // 栈顶指针上移
    return OK;
}

出栈

也叫做弹栈。

出栈的时候也要检验栈是否为空，将元素弹出就意味着这个元素离开了栈，所以要将顺序栈栈顶指针下移。对应着链栈则是该节点的删除。

顺序栈的出栈链栈的出栈

cpp

int Pop(SqStack &S, SElemType &e) {
    if (S.top == S.base)
        return ERROR;
    e = *(--S.top);
    return OK;
}

cpp

int LinkPop(LinkStack &S, SElemType &e) {
    if (!S)
        return ERROR;
    LinkStack p = S;
    e = p->data;
    S = S->next;
    free(p);
    return OK;
}

读栈顶

无论是顺序栈还是链栈，栈顶都是可以轻松访问到的。所以读栈顶的操作就很简单了，直接返回栈顶指针指向的元素即可。

顺序栈的读栈顶链栈的读栈顶

cpp

int GetTop(SqStack S, SElemType &e) {
    if (S.top == S.base)
        return ERROR;
    e = *(S.top - 1);
    return OK;
}

cpp

int LinkGetTop(LinkStack S, SElemType &e) {
    if (!S)
        return ERROR;
    e = S->data;
    return OK;
}

至于课本提到的其他小操作其实都可以用之前数组或链表的方式实现，这里就不一一列举了。

队列

不会有人插队的。

先进先出，即队列。

循环对列与链队列

人类世界在排队买鸡蛋灌饼的时候，如果前面的人买完了，后面的人自然会补上，队伍会缓缓向前移动。但是编程世界不一样，如果将队列用数组来表示的话，队列的每个元素都会占据自己固定的内存空间，即使第一个元素出队了，后面的元素也不会自动向前移动。

但是数组的空间是有限的，如果前面的元素离开了，而后面的元素又不向前移动，那么数组的空间就会越来越少，直到队满。这时就会出现一种奇怪的现象，哪怕队列里的元素很少，新元素也无法入队了。因为队列里不能插队，是不可能跑到前面的。

TIP

这里不考虑实现像现实生活中让队伍向前移动，因为在顺序表中，这意味着要控制每一个元素都要依次前移一位，时间复杂度是 $O (n)$ ，显然是不划算的。

解决这个问题，用链表来存储固然可行，也就是链队列；但是使用固定长度的数组并非毫无机会，一种方式是想象成将队尾和对头衔接起来，实现成一个圈，蛇头咬蛇尾，形成一个循环，循环队列也就这样实现了。

既然连成了一个圈，除了开辟顺序表所需要的基地址之外，自然还需要有一个队头指针和一个队尾指针来标识队伍的头部和尾部。既然是顺序表，指针其实就是数组的下标，int 类型足矣。

链队列也有头尾指针，这里之所以将链队列的头尾指针与链表的定义分开，是因为链表结构体所表示的只是链表的一个节点。显然不是每个节点都有头尾指针，所以单独封装。指针所指向的地址是链表节点，所以类型本来就是 QueuePtr。

循环队列链队列

cpp

typedef int QElemType

// 循环队列
typedef struct {
    QElemType * base;
    int front; // 队头指针
    int rear;  // 队尾指针
} SqQueue;

cpp

typedef int SElemType

// 链队列
typedef struct QNode {
    SElemType data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct
{
    QueuePtr front, rear; // 队头和队尾指针
} LinkQueue;

初始化与判空

循环队列在一开始什么元素也没有的时候，对头和队尾指针都是指向一起的，所以其实只需要判断对头和队尾指针是否相等，就可以判断出这个队列是否空空如也了。

链队列也是如此。

循环队列的初始化链队列的初始化

cpp

#define MAXSIZE 100

// 初始化循环队列
int InitQueue(SqQueue &Q) {
    Q.base = (QElemType *)malloc(MAXSIZE * sizeof(QElemType));
    if (!Q.base)
        exit(OVERFLOW);

    Q.front = Q.rear = 0;
    return OK;
}

cpp

// 初始化链队列
int InitLinkQueue(LinkQueue &Q) {
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if (!Q.front)
        exit(OVERFLOW);

    Q.front->next = NULL;
    return OK;
}

由于都具有头尾指针，判空的表达式也就都是一样的了：Q.front == Q.rear。

循环队列的判空链队列的判空

cpp

// 判空
int QueueEmpty(SqQueue Q) {
    return Q.front == Q.rear;
}

cpp

// 判空
int QueueEmpty(LinkQueue Q) {
    return Q.front == Q.rear;
}

进队与判满

链队列的进队就是尾插法，恰好满足先进先出。

循环队列的基础仍然是顺序表，线性的链条该怎么满足首尾相接呢？数学中有一种运算可以将无限长的数轴变为有限的周期循环，也就是取余。

任意自然数除以一个正整数 $n$ ，余数一定在 $0$ 到 $n - 1$ 之间。所以将入队的下标对总长度取余，自然就可以将元素存储在队列的任意位置了。

(Q.rear + 1) % MAXSIZE。

循环队列的进队链队列的进队

cpp

// 进队
int EnQueue(SqQueue &Q, QElemType e) {
    if (QueueFull(Q))
        return ERROR;                // 队列满
    Q.base[Q.rear] = e;              // 插入数据
    Q.rear = (Q.rear + 1) % MAXSIZE; // 队尾指针后移
    return OK;
}

cpp

// 链队进队
int LinkEnQueue(LinkQueue &Q, SElemType e) {
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if (!p)
        exit(OVERFLOW);
    p->data = e; // 数据放进去
    p->next = NULL; 
    Q.rear->next = p; // 原队尾指向新元素
    Q.rear = p; // 队尾指针后移
    return OK;
}

在进队时，数据放入尾指针所指向的空间，形成新的队尾，然后尾指针下移，永远指向队尾的下一个位置。

那么循环队列判满的条件也自然得出了。尾指针永远指向空位，头指针永远指向第一个元素，当尾指针的下一位是头指针时，就说明队列满了。

(Q.rear + 1) % MAXSIZE == Q.front。

循环队列的判满

cpp

bool QueueFull(SqQueue Q) {
    return (Q.rear + 1) % MAXSIZE == Q.front;
}

判满无需考虑链队列，因为链表本身就是为了解决空间固定不变的问题的，随时可以动态增删节点。

出队

循环队列出队后，头指针要后移，选取新的对头，同时完成取余计算：(Q.front + 1) % MAXSIZE。

循环队列的出队链队列的出队

cpp

int DeQueue(SqQueue &Q, QElemType &e) {
    if (QueueEmpty(Q))
        return ERROR;                  // 队列空
    e = Q.base[Q.front];               // 取队头元素
    Q.front = (Q.front + 1) % MAXSIZE; // 队头指针后移
    return OK;
}

cpp

int LinkDeQueue(LinkQueue &Q, SElemType &e) {
    if (LinkQueueEmpty(Q))
        return ERROR;
    QueuePtr p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p)
        Q.rear = Q.front; // 更新队尾指针，否则队尾指针就指向了已释放的节点了
    free(p);
    return OK;
}

读对头元素

对头指针在哪里，对头元素自然就在哪里。

循环队列的读对头元素链队列的读对头元素

cpp

// 读队头元素
int GetHead(SqQueue Q, QElemType &e) {
    if (QueueEmpty(Q))
        return ERROR;    // 队列空

    e = Q.base[Q.front]; // 获取队头元素
    return OK;
}

cpp

// 链队读队头元素
int LinkGetHead(LinkQueue Q, SElemType &e) {
    if (LinkQueueEmpty(Q))
        return ERROR;

    e = Q.front->next->data;
    return OK;
}

输出队列

剩下的操作自然也就很简单了，很多都是数组或链表的常规操作。

循环队列的输出链队列的输出

cpp

// 输出队列
void PrintQueue(SqQueue Q) {
    int i = Q.front;
    while (i != Q.rear) // 遍历队列
    { 
        printf("%d ", Q.base[i]);
        i = (i + 1) % MAXSIZE; // 循环方式处理
    }
    printf("\n\n");
}

cpp

// 输出链队列
void PrintLinkQueue(LinkQueue Q) {
    QueuePtr p = Q.front->next;
    while (p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n\n");
}

销毁队列

循环队列的销毁链队列的销毁

cpp

// 释放队列
void DestroyQueue(SqQueue &Q) {
    free(Q.base); // 释放动态内存
    Q.base = NULL;
    Q.front = Q.rear = 0;
}

cpp

// 销毁链队列
void DestroyLinkQueue(LinkQueue &Q) {
    while (Q.front)
    {
        QueuePtr p = Q.front;
        Q.front = Q.front->next;
        free(p);
    }
    Q.rear = NULL;
}

栈 ​

结构定义 ​

初始化创建 ​

入栈 ​

出栈 ​

读栈顶 ​

队列 ​

循环对列与链队列 ​

初始化与判空 ​

进队与判满 ​

出队 ​

读对头元素 ​

输出队列 ​

销毁队列 ​

栈