【数据结构】第六站：栈和队列
目录
一、栈
1.栈的概念和结构
2.栈的实现方案
3.栈的具体实现
4.栈的完整代码
5.有效的括号
二、队列
1.队列的概念及结构
2.队列的实现方案
3.队列的实现
4.队列实现的完整代码
一、栈
1.栈的概念和结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
2.栈的实现方案
对于这个栈，想必我们也不难想到他有两种实现的方案了，第一种方案是使用顺序表来实现，第二种方案是使用链表来实现
顺序表实现
如果采用顺序表来实现的话，由于只有在栈顶会出数据和入数据，所以栈顶就应该对应着数组的尾。
而这种方式，我们不难发现他是很优的，而且由于cpu的局部性原理，也是具有一定的优势的。因此我们发现栈是一种很适合使用顺序表实现的
链表来实现
如果采用链表来实现的话，我们可以选择使用单链表和带头双向循环链表。
如果我们使用单链表
我们这里又可以细分为栈顶在链表头和在链表尾
如下图所示是栈顶在链表尾部，这样的话我们显然可以得知他的效率是很低的
如果栈顶在链表头的话，这样就可以提升了效率，但是仍然没有顺序表更具有优势
而如果使用带头双向循环链表的话，确实也可以高效的实现栈，但是是没有顺序表具有优势的
3.栈的具体实现
栈的定义
根据上面的分析，我们决定采用顺序表来实现栈，使用顺序表又可以分为静态的和动态的。当然动态的性能是要优于静态的。我们使用动态顺序表
typedef int STDateType;typedef struct Stack {STDateType* a;int top;int capacity; }Stack;
栈的初始化
对于栈的初始化，与动态顺序表的初始化完全一样。初始为其分配四个数据的空间。然后让top和capacity分别置为0和4
//栈的初始化 void StackInit(Stack* ps) {assert(ps);ps->a = (STDateType*)malloc(sizeof(STDateType) * 4);if (ps->a == NULL){perror("malloc fail");return;}ps->top = 0;ps->capacity = 4; }
栈的销毁
由于这个栈的本质是一个顺序表，所以直接释放顺序表中指针所对应的那块空间即可
//栈的销毁 void StackDestroy(Stack* ps) {assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0; }
入栈
对于入栈，我们需要先检查容量，容量不够则扩容，然后直接尾插即可
//入栈 void StackPush(Stack* ps, STDateType x) {assert(ps);if (ps->top == ps->capacity){STDateType* tmp = (STDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDateType));if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++; }
出栈
对于出栈，我们得先确定栈内元素不为空，然后我们直接让top--即可
//出栈 void StackPop(Stack* ps) {assert(ps);assert(!StackEmpty(ps));ps->top--; }
栈的个数
由于我们的top代表的就是栈的个数，所以直接返回即可
//栈的个数 int StackSize(Stack* ps) {assert(ps);return ps->top; }
栈是否为空
对于判断栈是否为空，我们直接根据top的值即可判断
//栈是否为空 bool StackEmpty(Stack* ps) {assert(ps);return ps->top == 0; }
取出栈顶的元素
我们先确定栈不为空，然后直接返回栈顶元素即可
//取出栈顶的数据 STDateType StackTop(Stack* ps) {assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1]; }
4.栈的完整代码
Stack.h
#pragma once #include<stdio.h> #include<malloc.h> #include<stdbool.h> #include<assert.h>typedef int STDateType;typedef struct Stack {STDateType* a;int top;int capacity; }Stack;//栈的初始化 void StackInit(Stack* ps); //栈的销毁 void StackDestroy(Stack* ps); //入栈 void StackPush(Stack* ps, STDateType x); //出栈 void StackPop(Stack* ps); //栈的个数 int StackSize(Stack* ps); //栈是否为空 bool StackEmpty(Stack* ps); //取出栈顶的数据 STDateType StackTop(Stack* ps);
Stack.c
#define _CRT_SECURE_NO_WARNINGS 1#include"Stack.h"//栈的初始化 void StackInit(Stack* ps) {assert(ps);ps->a = (STDateType*)malloc(sizeof(STDateType) * 4);if (ps->a == NULL){perror("malloc fail");return;}ps->top = 0;ps->capacity = 4; } //栈的销毁 void StackDestroy(Stack* ps) {assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0; } //入栈 void StackPush(Stack* ps, STDateType x) {assert(ps);if (ps->top == ps->capacity){STDateType* tmp = (STDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDateType));if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++; } //出栈 void StackPop(Stack* ps) {assert(ps);assert(!StackEmpty(ps));ps->top--; } //栈的个数 int StackSize(Stack* ps) {assert(ps);return ps->top; } //栈是否为空 bool StackEmpty(Stack* ps) {assert(ps);return ps->top == 0; } //取出栈顶的数据 STDateType StackTop(Stack* ps) {assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1]; }
Test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" void TestStack1() {Stack s;StackInit(&s);StackPush(&s, 1);StackPush(&s, 2);StackPush(&s, 3);StackPush(&s, 4);StackPush(&s, 5);printf("%d\\n", StackSize(&s));while (!StackEmpty(&s)){printf("%d ", StackTop(&s));StackPop(&s);}StackDestroy(&s); } int main() {TestStack1();return 0; }
5.有效的括号
题目链接：力扣
题目解析：对于这道题，最简单的方法就是使用一个栈来记录左括号，如果是左括号，则入栈，如果不是左括号，先取出栈顶的元素，并出栈。然后将栈顶元素与当前的字符进行比较。如果满足错误条件，则销毁栈后直接返回即可。
如果可以匹配，则直接让s++即可。最后当所有字符串遍历完成以后，然后根据栈是否为空，返回即可
typedef char STDateType;typedef struct Stack {STDateType* a;int top;int capacity; }Stack; //栈的初始化 void StackInit(Stack* ps) {assert(ps);ps->a = (STDateType*)malloc(sizeof(STDateType) * 4);if (ps->a == NULL){perror("malloc fail");return;}ps->top = 0;ps->capacity = 4; } //栈的销毁 void StackDestroy(Stack* ps) {assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0; } //入栈 void StackPush(Stack* ps, STDateType x) {assert(ps);if (ps->top == ps->capacity){STDateType* tmp = (STDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDateType));if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++; } //栈是否为空 bool StackEmpty(Stack* ps) {assert(ps);return ps->top == 0; } //出栈 void StackPop(Stack* ps) {assert(ps);assert(!StackEmpty(ps));ps->top--; } //栈的个数 int StackSize(Stack* ps) {assert(ps);return ps->top; }//取出栈顶的数据 STDateType StackTop(Stack* ps) {assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1]; } bool isValid(char * s){Stack st;StackInit(&st);while(*s!='\\0'){if( (*s=='(')||(*s=='[')||(*s=='{')){StackPush(&st,*s);}else{if(StackEmpty(&st)){StackDestroy(&st);return false;}char p=StackTop(&st);StackPop(&st);if( ((*s!=')')&&(p=='('))|| ((*s!=']')&&(p=='['))||((*s!='}')&&(p=='{'))){StackDestroy(&st);return false;}}s++;}bool ret =StackEmpty(&st);StackDestroy(&st);return ret; }
二、队列
1.队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头
2.队列的实现方案
对于队列的实现，我们仍然又两种方法可以选择，一种是链表形式，一种是顺序表形式
如果采用顺序表来实现的话，我们会发现头删操作时间复杂度较高。
如果采用链表来实现的话，我们发现找尾部结点的时间复杂度较高，但是我们可以多定义一个结点来随时知道尾部结点的地址。这样就可以优化掉找尾的时间复杂度。而且对于计算队列长度的话，我们也可以多定义一个变量size，我们在删除和插入数据的时候调整好size的大小。就可以优化掉计算队列长度的时间复杂度
这里我们也产生一个新的问题，对于单链表，能否多定义一个指针来控制尾部的地址，从而优化找尾的时间复杂度。
其实是不行的，对于尾插显然可以优化，但是对于尾删就不可以了。因为他需要找前一个结点的地址。
对于单链表我们也可以使用一个变量size，用来优化计算单链表长度的时间复杂度
综上所述，我们发现采用链表的结构是最优的。这个链表有一些不同的是，我们需要使用头尾两个指针以及一个size变量来进行优化，既然如此，那么我们就最好使用一个结构体来连接这些变量。否则传参的时候我们需要传三个以上的变量。
typedef int QDateType;typedef struct QNode {QDateType data;struct QNode* next; }QNode;typedef struct Queue {QNode* head;QNode* tail;int size; }Queue;
3.队列的实现
1.初始化队列
//初始化队列 void QueueInit(Queue* q) {assert(q);q->head = NULL;q->tail = NULL;q->size = 0; }如上代码所示，我们直接传结构体的地址就可以了。
2.队尾入数据
//申请一个结点 QNode* BuyQNode(QDateType x) {QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->next = NULL;newnode->data = x;return newnode; } //队尾入队列 void QueuePush(Queue* q, QDateType x) {assert(q);QNode* newnode = BuyQNode(x);if (q->tail == NULL){q->head = q->tail = newnode;}else{q->tail->next = newnode;q->tail = q->tail->next;}q->size++; }队尾入数据的话，与单链表的入数据思路是一致的，我们先申请一个结点，然后判断这个链表是否为空，如果为空，则特殊处理，否则正常尾插即可
3.队头出数据
//队头出队列 void QueuePop(Queue* q) {assert(q);assert(q->head);QNode* first = q->head->next;free(q->head);q->head = first;q->size--;if (q->head == NULL){q->tail = NULL;} }对于出数据，与单链表是一样的，但是我们需要特别注意尾指针，如果删了队列最后一个结点后队列为空，那么需要将尾结点置为空
4.获取头部尾部数据
//获取队列头部元素 QDateType QueueFront(Queue* q) {assert(q);assert(q->head);return q->head->data; } //获取队列尾部元素 QDateType QueueBack(Queue* q) {assert(q);assert(q->head);return q->tail->data; }对于这两个函数，基本思路是一样的，我们先判断链表不为空，然后直接返回数据即可
5.获取队列中的有效元素的个数
//获取队列中的有效元素个数 int QueueSize(Queue* q) {assert(q);return q->size; }对于这段代码，我们直接返回size即可
6.检测队列是否为空
//检测队列是否为空 bool QueueEmpty(Queue* q) {assert(q);return q->head == NULL; }这段代码也很简单，直接返回这个判断条件即可
7.销毁队列
//销毁队列 void QueueDestroy(Queue* q) {assert(q);QNode* cur = q->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}q->head = q->tail = NULL;q->size = 0; }销毁队列的方法与单链表的销毁是一样的，我们需要注意的是，别忘记置空head和tail以及size。
4.队列实现的完整代码
Queue.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<stdbool.h> #include<assert.h>typedef int QDateType;typedef struct QNode {QDateType data;struct QNode* next; }QNode;typedef struct Queue {QNode* head;QNode* tail;int size; }Queue;//初始化队列 void QueueInit(Queue* q); //队尾入队列 void QueuePush(Queue* q, QDateType x); //队头出队列 void QueuePop(Queue* q); //获取队列头部元素 QDateType QueueFront(Queue* q); //获取队列尾部元素 QDateType QueueBack(Queue* q); //获取队列中的有效元素个数 int QueueSize(Queue* q); //检测队列是否为空 bool QueueEmpty(Queue* q); //销毁队列 void QueueDestroy(Queue* q);
Queue.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h"//初始化队列 void QueueInit(Queue* q) {assert(q);q->head = NULL;q->tail = NULL;q->size = 0; } //申请一个结点 QNode* BuyQNode(QDateType x) {QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->next = NULL;newnode->data = x;return newnode; } //队尾入队列 void QueuePush(Queue* q, QDateType x) {assert(q);QNode* newnode = BuyQNode(x);if (q->tail == NULL){q->head = q->tail = newnode;}else{q->tail->next = newnode;q->tail = q->tail->next;}q->size++; } //队头出队列 void QueuePop(Queue* q) {assert(q);assert(q->head);QNode* first = q->head->next;free(q->head);q->head = first;q->size--;if (q->head == NULL){q->tail = NULL;} } //获取队列头部元素 QDateType QueueFront(Queue* q) {assert(q);assert(q->head);return q->head->data; } //获取队列尾部元素 QDateType QueueBack(Queue* q) {assert(q);assert(q->head);return q->tail->data; } //获取队列中的有效元素个数 int QueueSize(Queue* q) {assert(q);return q->size; } //检测队列是否为空 bool QueueEmpty(Queue* q) {assert(q);return q->head == NULL; } //销毁队列 void QueueDestroy(Queue* q) {assert(q);QNode* cur = q->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}q->head = q->tail = NULL;q->size = 0; }
Test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h"void TestQueue1() {Queue pq;QueueInit(&pq);QueuePush(&pq, 1);QueuePush(&pq, 2);QueuePush(&pq, 3);QueuePush(&pq, 4);QueuePush(&pq, 5);printf("%d \\n", QueueSize(&pq));while (!QueueEmpty(&pq)){printf("%d ", QueueFront(&pq));QueuePop(&pq);}QueueDestroy(&pq); } int main() {TestQueue1();return 0; }
本期内容就到这里了
如果对你有帮助的话，不要忘记点赞加收藏哦！！！