数据结构从零开始③：栈和队列——操作受限的线性表，一篇搞懂

一、引言

我们已经学习了顺序表和链表，今天要学的栈和队列在逻辑结构上也是线性的

不同于线性表，栈和队列都只能在一端或两端进行操作。限制了操作范围后，代码自然也变得简单、安全、高效，因此当我们只需要对线性结构数据两端进行操作时，可以使用栈和队列。

二、栈（stack）

栈是一种只允许在一端（栈顶）进行插入和删除的线性表，遵循后进先出（LIFO）原则。

举个例子，比如我们生活中放盘子，放在最上面的盘子肯定会被最先使用，栈也是同理。

我们目前已经学了两种底层方法（数组、链表）去实现一些的数据结构，大家可以先思考一下，对于这样一种数据结构我们应该使用哪种方法实现。

答案是都可以。只要能够实现这种数据结构无论使用哪种方法实现都是可以的。
对于数组来说，对头部的操作时间复杂度为O(n)，对尾部的操作时间复杂度为O(1)，我们只需要将数组尾部当作栈顶来操作即可。
对于链表来说，对头部操作时间复杂度反而为O(1)，因此我们将链表头部当作栈顶即可。

这里我们用数组来实现，相比于链表来说，数据有个好处就是空间开销会小一些。例如我们增加一个整型，数组只需要增加4个字节空间，链表却要申请一整个结点。

当我们仔细完成了前面顺序表和链表的实现，栈和队列的实现就会变得非常简单了。下面我直接给大家把我实现好的代码附上，以供大家借鉴参考。

// 栈的结构 typedef int StackDataType; typedef struct Stack { StackDataType* arr; int top; int capacity; }Stack; // 入栈 void StackPush(Stack* Stack, StackDataType x) { assert(Stack); // 判断空间是否足够 if (Stack->capacity == Stack->top) { int newCapacity = Stack->capacity == 0 ? 4 : 2 * Stack->capacity; StackDataType* newArr = (StackDataType*)realloc(Stack->arr, newCapacity * sizeof(StackDataType)); if (newArr == NULL) { perror("realloc failed"); exit(1); } Stack->arr = newArr; Stack->capacity = newCapacity; } Stack->arr[Stack->top] = x; Stack->top++; } // 出栈 void StackPop(Stack* Stack) { assert(Stack && Stack->arr && Stack->top); Stack->top--; } // 取栈顶元素 StackDataType StackTop(Stack* Stack) { assert(Stack && Stack->arr && Stack->top); return Stack->arr[Stack->top - 1]; } // 销毁 void StackDestroy(Stack* Stack) { assert(Stack); if (Stack->arr) { free(Stack->arr); Stack->arr = NULL; } Stack->top = Stack->capacity = 0; }

从栈的实现就能发现，栈的实现大多数都是O(1)的时间复杂度，并且只能对一端进行操作，这样就保证了即安全又高效。

下面我们就用栈来实践一道 leetcode 上的题：有效的括号https://leetcode.cn/problems/valid-parentheses/

解题思路：

1. 遍历字符串

2. 遇到左括号就入栈，包括 "("，"["，"{"

3. 遇到右括号就取栈顶元素来判断是否为配对的括号

4. 若不匹配或此时栈为空就返回 false

5. 遍历完之后，若栈为空则返回 true，否则返回 false

具体代码如下：

bool isValid(char* s) { char* i = s; // 创建并初始化一个栈 Stack stack = {NULL, 0, 0}; // 遍历字符串 while(*i != '\0') { // 这里我用ASCII码来匹配括号 // 若为左括号就入栈 if(*i == 40 || *i == 91 || *i == 123) { StackPush(&stack, *i); } // 若为右括号就判断 else if(*i == 41 || *i == 93 || *i == 125) { // 如果此时栈为空，则返回 false if(stack.top == 0) { StackDestroy(&stack); return false; } // 若不为空，就判断栈顶括号是否和右括号匹配 else { // 若匹配成功，就出栈一个左括号 if(StackTop(&stack) == 40 && *i == 41 || StackTop(&stack) == 91 && *i == 93 || StackTop(&stack) == 123 && *i == 125) { StackPop(&stack); } // 匹配失败直接返回 false else { StackDestroy(&stack); return false; } } } i++; } // 遍历完字符串判断栈是否为空，为空返回true，不为空返回false if(stack.top == 0) StackDestroy(&stack); return true; else StackDestroy(&stack); return false; }

三、队列

队列是一种只允许在一端（队尾）插入，另一端（队头）删除的线性表，遵循先进先出（FIFO）原则。

这个就与我们生活中的队列相同，排队只能在队尾排（当然，有插队的人另说），先排的人先处理。

队列通常用链表的方式去实现，由于队列要对两端进行操作，普通链表无法实现以时间复杂度O(1)来对尾端进行操作，因此我们需要在普通链表的基础上进行改进：
定义两个结构体，一个表示结点（包含数据data和下一个结点next），一个表示整个队列（包含首结点head和尾结点tail）。这样改进之后有了一个专门指向队尾的tail，就能以O(1)的时间复杂度从队尾入队。

具体实现代码如下（依然是仅供参考，希望兄弟们能写出属于自己的队列）：

typedef int QueueDataType; // 队列结点结构 typedef struct QueueNode { QueueDataType data; QueueNode* next; }QueueNode; // 队列结构 typedef struct Queue { QueueNode* head; QueueNode* tail; }Queue; // 入队 void QueuePush(Queue* queue, QueueDataType x) { assert(queue); QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode)); if (newNode == NULL) { perror("malloc failed"); exit(1); } newNode->data = x; newNode->next = NULL; if (queue->head == NULL) { queue->head == queue->tail == newNode; } else { queue->tail->next = newNode; queue->tail = newNode; } } // 出队 void QueuePop(Queue* queue) { assert(queue && queue->head); if (queue->head == queue->tail) { free(queue->head); queue->head = queue->tail = NULL; } else { QueueNode* del = queue->head; queue->head = queue->head->next; free(del); del = NULL; } } // 销毁队列 void QueueDestroy(Queue* queue) { assert(queue); QueueNode* del = queue->head; while (del) { queue->head = queue->head->next; free(del); del = queue->head; } queue->head = queue->tail = NULL; } // 取队首元素 QueueDataType QueueFront(Queue* queue) { assert(queue && queue->head); return queue->head->data; } // 取队尾元素 QueueDataType QueueBack(Queue* queue) { assert(queue && queue->head); return queue->tail->data; }

还有一个计算队列元素个数的方法我没有实现，如果以我这种方式写，那就变成O(n)了，如果需要可以在Queue中再添加一个size成员，这样计算更加方便。