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

一、引言我们已经学习了顺序表和链表今天要学的栈和队列在逻辑结构上也是线性的不同于线性表栈和队列都只能在一端或两端进行操作。限制了操作范围后代码自然也变得简单、安全、高效因此当我们只需要对线性结构数据两端进行操作时可以使用栈和队列。二、栈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. 若不匹配或此时栈为空就返回 false5. 遍历完之后若栈为空则返回 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成员这样计算更加方便。