【数据结构】第六站：栈和队列

目录

一、栈

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;
}

---

本期内容就到这里了

如果对你有帮助的话，不要忘记点赞加收藏哦！！！