网站导航
> 文档中心 > C语言简单的【栈和队列】（括号匹配问题）

C语言简单的【栈和队列】（括号匹配问题）

网友: 文档中心 2022-04-13 08:36:41

C语言实现简单数据结构
本系列全篇呈现C语言简单实现数据结构

不好看的目录

  • 前言
  • 一、栈
    • C语言简单实现栈
  • 二、队列
    • C语言简单实现队列
  • 括号匹配问题
  • 总结

前言

摆烂一个月的大学生回来写栈和队列
C语言简单的【栈和队列】（括号匹配问题）
通篇代码非常简单，且每一行都有注释，还有图示哦~

一、栈

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

在这里插入图片描述

C语言简单实现栈

了解了栈的特性，我们发现栈的实现特别简单，不管是数组还是链表都尤其容易，从操作和理解的角度，以及栈只需要对尾部进行操作，数组的操作更为容易

为什么不适用链表，每次找到尾结点都需要遍历链表，时间浪费。

在这里插入图片描述
在这里插入图片描述

首先了解大致框架以及结构原理

typedef struct Stack
{
STDataType* a;
int top; //栈顶的位置
int capacity; //容量
}ST;
C语言简单的【栈和队列】（括号匹配问题）

Stack.h

#pragma once//防止头文件重复#include #include #include #include typedef int STDataType;//栈存储的数据类型typedef struct Stack{STDataType* a;int top;//栈顶的位置int capacity;//容量}ST;void StackInit(ST* ps);//栈初始化void StackDestory(ST* ps);//栈的销毁void StackPush(ST* ps, STDataType x);//压栈void StackPop(ST* ps);//出栈bool StackEmpty(ST* ps);//判断栈是否为空int StackSize(ST* ps);//栈内元素数量STDataType StackTop(ST* ps);//栈顶元素
  • void StackInit(ST* ps);//栈初始化
void StackInit(ST* ps){assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;}

销毁栈，数组首地址置空，栈顶位置与栈容量重置为0（不需要画图讲吧）

  • void StackDestory(ST* ps);//栈的销毁
void StackDestory(ST* ps){assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;}

assert断言栈ps是否为空，为空没有必要进行下面的操作,然后就是正常的free操作，与初始化的不同就是free会将这块空间归还系统，操作者无法再次使用。

  • void StackPush(ST* ps, STDataType x);//压栈
void StackPush(ST* ps, STDataType x){assert(ps);if (ps->top == ps->capacity)//用满了满了{int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//是空栈还是用满了，扩容两倍不多不少ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));//给栈newnode大小的空间。if (ps->a == NULL)//realloc失败会返回空指针{printf("realloc fail\n");exit(-1);}ps->capacity = newCapacity;}ps->a[ps->top] = x;//这里注意区分top和capacity的位置ps->top++;}代码有逐行注释，思维见图

在这里插入图片描述

通俗来讲，top与capacity都是对应元素的数组下标位置+1,或者说是元素的数量

  • void StackPop(ST* ps);//出栈
void StackPop(ST* ps){assert(ps);assert(ps->top > 0);//栈是否为空ps->top--;//甚至不用重置数据，因为我们之后不会再用到删除的数据，利用结构特性top--即可.}0~~~比较简单
  • bool StackEmpty(ST* ps);//判断栈是否为空
bool StackEmpty(ST* ps){assert(ps);return ps->top == 0;}ps->top为0即是空，为真返回1，因为不可能为负数，大于0即为假不为空返回0
  • int StackSize(ST* ps);//栈内元素数量
int StackSize(ST* ps){assert(ps);return ps->top;//见图}

C语言简单的【栈和队列】（括号匹配问题）
可以把栈理解为一个饮料瓶，top就是瓶盖那一片片

  • STDataType StackTop(ST* ps);//栈顶元素
STDataType StackTop(ST* ps){assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];}

上面形容top是瓶盖，那么我们要找到最上面的一块水总得找到瓶盖下的一块位置才能访问最后一个元素。

二、队列

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
在这里插入图片描述

C语言简单实现队列

像栈一样，从概念理解，队列也可以用数组或链表来实现，但考虑队列需要对头部和尾部也仅需要对头部和尾部需要操作，使用链表进行头尾操作相当便捷。
为什么不使用数组
进行头插与头删时需要挪动整个数组。
在这里插入图片描述
在这里插入图片描述

大致框架与结构原理

typedef int QDataType;typedef struct QListNode{struct QListNode* next;//指向下一个结点的指正QDataType data;//该节点内的数据}QNode;//一个数据结点// 队列的结构 typedef struct Queue{QNode* front;//对头QNode* rear;//对尾}Queue;

在这里插入图片描述
队列的结构中只放置了头尾两个结点。

到头来，不就是单链表头尾操作吗。C语言简单的【栈和队列】（括号匹配问题）

Queue.h

#pragma once// 链式结构：表示队列 #include #include #include typedef int QDataType;typedef struct QListNode{struct QListNode* next;QDataType data;}QNode;// 队列的结构 typedef struct Queue{QNode* front;QNode* rear;}Queue;// 初始化队列 void QueueInit(Queue* q);// 队尾入队列 void QueuePush(Queue* q, QDataType data);// 队头出队列 void QueuePop(Queue* q);// 获取队列头部元素 QDataType QueueFront(Queue* q);// 获取队列队尾元素 QDataType QueueBack(Queue* q);// 获取队列中有效元素个数 int QueueSize(Queue* q);// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* q);// 销毁队列 void QueueDestroy(Queue* q);
  • 初始化队列

void QueueInit(Queue* q);

void QueueInit(Queue* q){assert(q);q->front = NULL;q->rear = NULL;}

过于简单

  • 队尾入队列

void QueuePush(Queue* q, QDataType data);

void QueuePush(Queue* q, QDataType data){assert(q);QNode* newnode = (QNode*)malloc(sizeof(QNode));//开辟一个需要插入的节点assert(newnode);//不排除malloc失败的可能newnode->data = data;//节点赋值newnode->next = NULL;//单链表中尾结点的next为NULLif (q->rear == NULL)//判断队列原来有没有数据{assert(q->front == NULL);q->front = q->rear = newnode;//相当于给空队列插入一个结点，插入后即是头节点也是尾节点}else//正常情况，队列内有数据，正常的单链表尾插{q->rear->next = newnode;q->rear = newnode;}}

代码每一行都有注释，而且代码本身也很好懂偶
在这里插入图片描述

  • 队头出队列

void QueuePop(Queue* q);
相当普通的单列表头删

void QueuePop(Queue* q){assert(q);assert(q->front && q->rear);//头删也得有东西删吧if (q->front->next == NULL)//只有一个数据{q->front = q->rear == NULL;}else{QNode* next = q->front->next;//提前保存头节点的下一个节点，不然free后就找不到啦free(q->front);//正常操作，删除节点，不再使用需要释放空间q->front = next;//front换人（老二）了}}

在这里插入图片描述

  • 获取队列头部元素

QDataType QueueFront(Queue* q);

QDataType QueueFront(Queue* q){assert(q);if (q->front == NULL && q->rear == NULL)//空队列{return NULL;}return q->front->data;//是不是非常简单}

需要图解吗，不需要吧.

  • 获取队列队尾元素

QDataType QueueBack(Queue* q);

// 获取队列队尾元素 QDataType QueueBack(Queue* q){assert(q);if (q->front == NULL && q->rear == NULL)//为空{return NULL;}return q->rear->data;//《？？？》}

很简单的，队列很简单的，栈和队列的理解都很简单的

  • 获取队列中有效元素个数

int QueueSize(Queue* q);

// 获取队列中有效元素个数 int QueueSize(Queue* q){assert(q);QNode* cur = q->front;//一种编程习惯，不直接把形参拿来用int size = 0;while (cur)//遍历{size++;//计数器的方法cur = cur->next;}return size;}

在这里插入图片描述

  • 检测队列是否为空，如果为空返回非零结果，如果非空返回0

int QueueEmpty(Queue* q);

int QueueEmpty(Queue* q){assert(q);return q->front == NULL;//表达式成立返回1队列为空}

头都是空了~~~

  • 销毁队列

void QueueDestroy(Queue* q);

void QueueDestroy(Queue* q){assert(q);QNode* cur = q->front;//建立连接while (cur)//一个一个的free结点{QNode* next = cur->next;free(cur);cur = next;}q->front = q->rear = NULL;}

不能直接free头结点吧，也更不能直接free队列的地址吧，里面的结点还在的，会造成内存泄漏的。
在这里插入图片描述

括号匹配问题

  • 括号匹配题目链接

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
在这里插入图片描述
在这里插入图片描述

  • 思路

匹配问题，想要括号正确匹配就必须有对应的左右括号，考虑到匹配操作，可以利用栈的特性，将左括号入栈，一旦遇到右括号便与栈中最近的左括号进行匹配，匹配则继续向后判断，不匹配返回FALSE。
在这里插入图片描述

考虑到需要使用栈，我们可以之间把我们实现的栈拿来用（这里是C语言频道，STL暂不涉及）
剩下的就是把思想用代码实现

题目只给出了函数名以及所传参数.

//这样部分可以拿来放到开头typedef int STDataType;typedef struct Stack{STDataType* a;int top;//栈顶的位置int capacity;//容量}ST;void StackInit(ST* ps){assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;}void StackDestory(ST* ps){assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;}void StackPush(ST* ps, STDataType x){assert(ps);if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));if (ps->a == NULL){printf("realloc fail\n");exit(-1);}ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;}void StackPop(ST* ps){assert(ps);assert(ps->top > 0);ps->top--;}bool StackEmpty(ST* ps){assert(ps);return ps->top == 0;}int StackSize(ST* ps){assert(ps);return ps->top;}STDataType StackTop(ST* ps){assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];}
bool isValid(char * s){    ST st;//创建一个栈    StackInit(&st);    while(*s)//题目传了一个括号数组进来    { if(*s == '(' || *s == '{' || *s == '[')//左括号入栈 {     //入栈     StackPush(&st, *s);     s++; }  else {     //匹配     if(StackEmpty(&st))//直到遇到第一个右括号也没有左括号，括号不匹配     {  return false;     }     //栈内有左括号，可以进行匹配     char top = StackTop(&st);//拿到了栈顶的数据并记录，因为下一步会删除     StackPop(&st);//匹配后需要与它左边的括号继续匹配直到匹配完     if(*s == ']' && top != '['      || *s == '}' && top != '{'     || *s == ')' && top != '(')//不匹配     {  StackDestory(&st);防止内存泄漏，因为栈是我们自行开辟的  return false;     }     else//单个括号匹配     {  //继续比  ++s;//找到s里的下一个括号，再次判断需要入栈还是与前面剩余也是栈顶的括号进行匹配     } }    }    bool ret = StackEmpty(&st);//栈为空，就说明全部匹配    StackDestory(&st);//栈是自己开辟的    return ret;}

每次只有s出现右括号时让其与栈顶括号匹配，然后删除栈顶数组。

总结

栈和队列很简单的，都是顺序表和单链表的子集啦
下次会有用队列实现栈、用栈实现队列、循环队列等经典题目讲解。

网络标签：

相关问题