西安网站制作多少钱,报价单模板英文,wordpress佣金分成,电商网站建设技术员的工作职责栈和队列的建立 前言一、栈1.栈的概念2.栈的实现3.代码示例#xff08;1#xff09;Stack.h#xff08;2#xff09;Stack.c#xff08;3#xff09;Test.c#xff08;4#xff09;运行结果#xff08;5#xff09;完整代码演示 二、队列1.队列的概念2.队列的实现3.代… 栈和队列的建立 前言一、栈1.栈的概念2.栈的实现3.代码示例1Stack.h2Stack.c3Test.c4运行结果5完整代码演示 二、队列1.队列的概念2.队列的实现3.代码示例1Queue.h2Queue.c3Test.c4运行结果5完整代码演示 三、栈的应用例题方法一方法二 总结 前言
今天我们来学习栈和队列的简易建立 在后面还会有一道栈的应用题检测大家的用功程度 加油吧 一、栈
1.栈的概念 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端称为栈顶另一端称为栈底。 栈中的数据元素遵守后进先出LIFOLast In First Out的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶。 模型图示例
2.栈的实现 栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。 图片示例
3.代码示例
1Stack.h 1.头文件的声明 //头文件的声明
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h2.栈的接口定义 //栈的接口定义
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;3.初始化和销毁函数的声明 //初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);4.入栈和出栈函数的声明 //插入
void STPush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);5.查找栈顶元素和长度计算函数以及判空函数的声明 //插入
//查找栈顶元素
STDataType STTop(ST* ps);
//长度计算
int STSize(ST* ps);
//判断是否为空
bool STEmpty(ST* ps);2Stack.c 1.头文件的声明 #include Stack.h2.初始化和销毁函数的定义 /初始化
void STInit(ST* ps)
{assert(ps);ps-a NULL;ps-capacity 0;ps-top 0;
}//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;
}3.入栈和出栈函数的定义 //插入
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps-top ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;ps-top;
}//删除栈顶元素
void STPop(ST* ps)
{assert(ps);assert(ps-top 0);--ps-top;
}4.查找栈顶元素和长度计算函数以及判空函数的定义 //查找栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}//长度计算
int STSize(ST* ps)
{assert(ps);return ps-top;
}//判断是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}3Test.c 1.头文件的声明 #include Stack.h2.测试函数的定义 void TestStack()
{ST st;STInit(st);STPush(st, 1);STPush(st, 2);STPush(st, 3);STPush(st, 4);STPush(st, 5);while (!STEmpty(st)){printf(%d , STTop(st));STPop(st);}printf(\n);STPush(st, 6);STPush(st, 7);STPush(st, 8);STPush(st, 9);STPush(st, 10);while (!STEmpty(st)){printf(%d , STTop(st));STPop(st);}printf(\n);STDestroy(st);
}3.主函数的定义 int main()
{TestStack();return 0;
}4运行结果 5完整代码演示 1.Stack.h #pragma once
//头文件的声明
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h//栈的接口定义
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//插入
void STPush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//查找栈顶元素
STDataType STTop(ST* ps);
//长度计算
int STSize(ST* ps);
//判断是否为空
bool STEmpty(ST* ps);2.Stack.c #include Stack.h//初始化
void STInit(ST* ps)
{assert(ps);ps-a NULL;ps-capacity 0;ps-top 0;
}//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;
}//插入
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps-top ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;ps-top;
}//删除栈顶元素
void STPop(ST* ps)
{assert(ps);assert(ps-top 0);--ps-top;
}//查找栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}//长度计算
int STSize(ST* ps)
{assert(ps);return ps-top;
}//判断是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}3.Test.c #include Stack.hvoid TestStack1()
{ST st;STInit(st);STPush(st, 1);STPush(st, 2);STPush(st, 3);STPush(st, 4);STPush(st, 5);while (!STEmpty(st)){printf(%d , STTop(st));STPop(st);}printf(\n);STPush(st, 6);STPush(st, 7);STPush(st, 8);STPush(st, 9);STPush(st, 10);while (!STEmpty(st)){printf(%d , STTop(st));STPop(st);}printf(\n);STDestroy(st);
}int main()
{TestStack1();return 0;
}二、队列
1.队列的概念 队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出 FIFO(First In First Out) 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头 模型图示例
2.队列的实现 队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。 图片示例
3.代码示例
1Queue.h 1.头文件的声明 #pragma once
//头文件的声明
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h2.队列接口的定义 //链表接口定义
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;//队列接口定义
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que; 3.初始化和销毁函数的声明 //队列初始化
void QueueInit(Que* pq);
//队列销毁
void QueueDestroy(Que* pq);4.入队列和出队列函数的声明 //插入
void QueuePush(Que* pq, QDataType x);
//删除
void QueuePop(Que* pq);5.查找队头、查找队尾函数的声明 //查找队头元素
QDataType QueueFront(Que* pq);
//查找队尾元素
QDataType QueueBack(Que* pq);6.判空以及长度计算函数的声明 //判断是否为空
bool QueueEmpty(Que* pq);
//计算长度
int QueueSize(Que* pq);2Queue.c 1.头文件的声明 #include Queue.h2.初始化和销毁函数的定义 void QueueInit(Que* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}void QueueDestroy(Que* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;pq-size 0;
}3.入队列和出队列函数的定义 void QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;if (pq-tail NULL){pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size;
}void QueuePop(Que* pq)
{assert(pq);//判断队列指针指向是否为空assert(!QueueEmpty(pq));//判断队列里面的数据是否为空if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* next pq-head-next;free(pq-head);pq-head next;}pq-size--;
}4.查找队头、查找队尾函数的定义 //查找队头元素
QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-data;
}//查找队尾元素
QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}5.判空以及长度计算函数的定义 //判断是否为空
bool QueueEmpty(Que* pq)
{assert(pq);return pq-head NULL;
}//长度计算
int QueueSize(Que* pq)
{assert(pq);return pq-size;
}3Test.c 1.头文件的声明 #include Queue.h2.测试函数的定义
void QueueTest() {Que pq;QueueInit(pq);QueuePush(pq, 1);QueuePush(pq, 2);QueuePush(pq, 3);QueuePush(pq, 4);QueuePush(pq, 5);while (!QueueEmpty(pq)) {printf(%d , QueueFront(pq));QueuePop(pq);}QueueDestroy(pq);
}3.主函数的定义
int main() {QueueTest();return 0;
}4运行结果 5完整代码演示 1.Queue.h #pragma once
//头文件的声明
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h//链表接口定义
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;//队列接口定义
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;//队列初始化
void QueueInit(Que* pq);
//队列销毁
void QueueDestroy(Que* pq);
//插入
void QueuePush(Que* pq, QDataType x);
//删除
void QueuePop(Que* pq);
//查找队头元素
QDataType QueueFront(Que* pq);
//查找队尾元素
QDataType QueueBack(Que* pq);
//判断是否为空
bool QueueEmpty(Que* pq);
//计算长度
int QueueSize(Que* pq); 2.Queue.c #include Queue.hvoid QueueInit(Que* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}void QueueDestroy(Que* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;pq-size 0;
}void QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;if (pq-tail NULL){pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size;
}void QueuePop(Que* pq)
{assert(pq);//判断队列指针指向是否为空assert(!QueueEmpty(pq));//判断队列里面的数据是否为空if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* next pq-head-next;free(pq-head);pq-head next;}pq-size--;
}//查找队头元素
QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-data;
}//查找队尾元素
QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}//判断是否为空
bool QueueEmpty(Que* pq)
{assert(pq);return pq-head NULL;
}//长度计算
int QueueSize(Que* pq)
{assert(pq);return pq-size;
}3.Test.c #include Queue.hvoid QueueTest() {Que pq;QueueInit(pq);QueuePush(pq, 1);QueuePush(pq, 2);QueuePush(pq, 3);QueuePush(pq, 4);QueuePush(pq, 5);while (!QueueEmpty(pq)) {printf(%d , QueueFront(pq));QueuePop(pq);}QueueDestroy(pq);
}int main() {QueueTest();return 0;
}三、栈的应用例题 题目括号匹配问题 题目链接 提示 . 1 s.length 104 . s 仅由括号 ‘()[]{}’ 组成
解题思路 这道题我有两种解法 建栈法和暴力破解法
方法一
首先第一种就是利用栈来解决 1.左括号入栈 2.右括号与栈中的栈顶括号进行匹配
图例 代码示例
引用之前栈的建立函数
//栈的接口定义
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//插入
void STPush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//查找栈顶元素
STDataType STTop(ST* ps);
//长度计算
int STSize(ST* ps);
//判断是否为空
bool STEmpty(ST* ps);//初始化
void STInit(ST* ps)
{assert(ps);ps-a NULL;ps-capacity 0;ps-top 0;
}//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;
}//插入
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps-top ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;ps-top;
}//删除栈顶元素
void STPop(ST* ps)
{assert(ps);assert(ps-top 0);--ps-top;
}//查找栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}//长度计算
int STSize(ST* ps)
{assert(ps);return ps-top;
}//判断是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}功能函数的定义
bool isValid(char* s) {ST st;STInit(st);char topVal;while (*s ) {if (*s ( || *s [ || *s {) {STPush(st, *s);}else {//数量不匹配if (STEmpty(st)){STDestroy(st);return false;}topVal STTop(st);STPop(st);if ((*s ] topVal ! [)|| (*s ] topVal ! [)|| (*s ] topVal ! [)) {STDestroy(st);return false;}}s;}bool ret STEmpty(st);STDestroy(st);return ret;
}方法二
第二种方法就是例子中如果不存在无效括号的话那么至少有一个是左右括号相邻的 所以先找到相邻且匹配的括号将其移除然后慢慢一点一点全部都移除的话则说明全部括号有效
图例
代码演示
bool isValid(char* s) {char* p s;while (*p) {p s;while (*p) {if (*p 1 *(p 1) || *p 2 *(p 1)) {//查看assii码表了解符号的大小char* move p;while (true) {*move *(move 2);if(*move\0)break;move;}break;}else {p;}}if (*p \0 *s ! \0)return false;}return true;
}总结
今天的内容有点多希望大家仔细观看细细揣摩 好好学习天天向上 不变的真理
