网站建设上传与发布流程,河北搭建营销型网站,网站建设费要摊销,做网站的的步骤怎么写目录 一.数据结构--栈
1.栈的基本介绍
2.栈的实现
二.数据结构--队列
1.队列的基本介绍
2.队列的实现
三.栈的运用(Leetcode20. 有效的括号225)
1.问题描述
2.问题分析
题解代码#xff1a;
四.用两个队列实现栈(225. 用队列实现栈 - 力扣#xff08;Leetcode225)
1.问题描述
2.问题分析
题解代码
四.用两个队列实现栈(225. 用队列实现栈 - 力扣Leetcode)
题解代码:
五.用两个栈实现队列(232. 用栈实现队列 - 力扣Leetcode)
题解代码: 一.数据结构--栈
1.栈的基本介绍 栈是一种数据先进后出,后进先出的数据结构 栈一般用数组来实现(用单链表实现的栈缺陷明显:数据的出栈操作时间复杂度为O(N),原因在于要找到表尾数据的前一个数据的地址) 2.栈的实现 总体图解 栈的头文件 #pragma once
#include stdio.h
#include assert.h
#include stdbool.h
#include stdlib.htypedef int STDataType;
typedef struct Stack
{STDataType * arry; //栈的堆区空间指针int top; //维护栈顶下标,同时记录栈中的元素个数int capacity; //记录栈的容量
}ST;void StackInit(ST* Stack); //栈对象的初始化
STDataType StackTop(ST*Stack); //返回栈顶元素
void StackPush(ST* Stack,STDataType val); //元素入栈
void StackPop(ST* Stack); //元素出栈
int StackSize(ST* Stack); //返回栈对的元素个数的接口;
bool StackEmpty(ST* Stack); //判断栈是否为空的接口
void StackDestroy(ST* Stack); //销毁栈 栈初始化接口 void StackInit(ST* Stack)
{assert(Stack);Stack-arry NULL;Stack-capacity 0;Stack-top 0;
}返回栈顶元素的接口 STDataType StackTop(ST* Stack)
{assert(Stack);assert(Stack-top 0);return Stack-arry[Stack-top - 1];
} 返回栈数据个数的接口 int StackSize(ST* Stack)
{assert(Stack);return Stack-top;
} 判断栈是否为空的接口 bool StackEmpty(ST* Stack)
{assert(Stack);return (Stack-top 0);
} 数据入栈操作接口 void StackPush(ST* Stack, STDataType val)
{assert(Stack);if (Stack-capacity Stack-top) //检查容量是否足够{int newcapacity (0 Stack-capacity) ? 4 : 2 * Stack-capacity;//如果容量为零,则将容量设置为4,其他情况下按照两倍扩容方式增容STDataType* tem (STDataType*)realloc(Stack-arry, newcapacity*sizeof(STDataType));if (NULL tem)//判断realloc是否成功{perror(realloc failed:);exit(-1);}Stack-capacity newcapacity;Stack-arry tem;}//元素入栈Stack-arry[Stack-top] val;Stack-top;
} 数据出栈操作接口: void StackPop(ST* Stack)
{assert(Stack);assert(Stack-top 0);Stack-top--;
} 销毁栈的接口: void StackDestroy(ST* Stack)
{assert(Stack);if (Stack-arry){free(Stack-arry);}Stack-arry NULL;Stack-capacity 0;Stack-top 0;
} 二.数据结构--队列
1.队列的基本介绍 队列是一种数据先进先出,后进后出的数据结构. 数据只能从队尾入,从队头出 队列一般用单链表实现,原因在于队列涉及数据的头删操作,单链表的数据头删操作时间复杂度为O(1).2.队列的实现 队列总体图解: 队列的头文件: #pragma once
#include stdio.h
#include stdlib.h
#include stdbool.h
#include assert.htypedef int QDataType;typedef struct QueueNode //单链表结构体
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue //维护队列的结构体
{QNode* head;QNode* tail;
}Queue;void QueueInit(Queue* queue); //队列的初始化接口
void QueueDestroy(Queue* queue); //销毁队列的接口
void QueuePush(Queue* queue,QDataType val); //数据入队接口
void QueuePop(Queue* queue); //数据出队接口
QDataType QueueFront(Queue* queue); //返回队头数据接口
QDataType QueueBawck(Queue* queue); //返回队尾数据接口
int QueueSize(Queue* queue); //返回队列数据个数的接口
bool QueueEmpty(Queue* queue); //判断队列是否为空的接口 队列的初始化接口: void QueueInit(Queue* queue) //队列初始化
{assert(queue);queue-head NULL;queue-tail NULL;
} 返回队头数据的接口: QDataType QueueFront(Queue* queue) //返回队列头部数据
{assert(queue);assert(queue-head);return queue-head-data;
} 返回队尾数据的接口: QDataType QueueBawck(Queue* queue) //返回队列尾部数据
{assert(queue);assert(queue-tail);return queue-tail-data;
} 返回队列数据个数的接口: int QueueSize(Queue* queue) //返回队列节点个数
{assert(queue);int count 0;QNode* tem queue-head;while(tem){count;tem tem-next;}return count;
} 判断队列是否为空的接口: bool QueueEmpty(Queue* queue) //判断队列是否为空
{assert(queue);return (NULL queue-head);
} 数据入队接口: void QueuePush(Queue* queue,QDataType val) //链表尾插数据(数据从队列尾入队)
{assert(queue);QNode* NewNode (QNode*)malloc(sizeof(QNode));//申请堆区链表节点if (NULL NewNode){perror(malloc failed:);exit(-1);}NewNode-data val;NewNode-next NULL;if (NULL queue-tail) //链表为空时的数据插入操作{assert(NULL queue-head);queue-tail NewNode;queue-head NewNode;}else //链表非空时的数据插入操作{queue-tail-next NewNode;queue-tail NewNode;}
} 数据出队的接口: void QueuePop(Queue* queue) //删去链表头节点(数据从队列头部出队)
{assert(queue);assert(queue-head queue-tail);QNode* Next queue-head-next;free(queue-head);queue-head Next;if (NULL queue-head) //若删去的是链表的最后一个元素,则要将尾指针也置空{queue-tail NULL;}
} 销毁队列的接口: void QueueDestroy(Queue* queue) //销毁链表(队列)
{assert(queue);QNode* tem queue-head;while (tem){QNode* Next tem-next;free(tem);tem Next;}queue-head NULL;queue-head NULL;
} 三.栈的运用(Leetcode20. 有效的括号225) 20. 有效的括号 - 力扣Leetcode 1.问题描述 给定一个只包括 ( , ) , { , } , [ , ] 的字符串 s 判断字符串是否有效。 有效字符串需满足 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。示例: 输入s ()[]{}
输出true C题解接口: bool isValid(char * s)
{} 2.问题分析 从左向右遍历字符串的情况下的括号匹配思路: 由于在遍历字符串时,我们无法确定当前的左括号会和哪一个右括号匹配,因此匹配的思路应该是先找到第一个右括号,然后再向前寻找相应的左括号,若匹配失败则返回false,若匹配成功则继续寻找下一个右括号重复上述过程,直到结束 暴力匹配算法动画解析:根据上面的分析可知暴力匹配法的时间复杂度为O(N^2) 然而本题如果使用辅助栈来求解,则可以达到用空间来换取时间效率的目的。 基本思路如下: 用一个指针遍历字符串,每当遇到左括号,我们就将其压入栈中每当遇到右括号,我们就将其与栈顶括号进行匹配,若匹配失败则说明字符串不满足条件,接口返回false,若匹配成功则弹出栈顶元素,并继续遍历字符串重复上述步骤直到找到\0则接口返回true算法动画图解: 我们可以将实现好的栈(本期第一节中)用于解题(顺便还可以验证我们栈的实现有没有bug) 题解代码 用于题解的栈 typedef char STDataType;
typedef struct Stack
{STDataType * arry; //栈的堆区空间指针int top; //维护栈顶下标,同时记录栈中的元素个数int capacity; //记录栈的容量
}ST;void StackInit(ST* Stack)
{assert(Stack);Stack-arry NULL;Stack-capacity 0;Stack-top 0;
}STDataType StackTop(ST* Stack)
{assert(Stack);assert(Stack-top 0);return Stack-arry[Stack-top - 1];
}void StackPush(ST* Stack, STDataType val)
{assert(Stack);if (Stack-capacity Stack-top) //检查容量是否足够{int newcapacity (0 Stack-capacity) ? 4 : 2 * Stack-capacity;STDataType* tem (STDataType*)realloc(Stack-arry, newcapacity*sizeof(STDataType));if (NULL tem){perror(realloc failed:);exit(-1);}Stack-capacity newcapacity;Stack-arry tem;}Stack-arry[Stack-top] val;Stack-top;
}void StackPop(ST* Stack)
{assert(Stack);assert(Stack-top 0);Stack-top--;
}int StackSize(ST* Stack)
{assert(Stack);return Stack-top;
}bool StackEmpty(ST* Stack)
{assert(Stack);return (Stack-top 0);
}void StackDestroy(ST* Stack)
{assert(Stack);if (Stack-arry){free(Stack-arry);}Stack-arry NULL;Stack-capacity 0;Stack-top 0;
}两个辅助判断接口代码: //判断指针指向的括号是否为右括号的接口bool CheckRightQutoe(const char quote) //左括号返回true,有括号返回false{if({ quote || ( quote || [ quote){return true;}else{return false;}}//判断两个括号是否匹配的接口bool JudgeMatch(const char right,const char left){if((} right { left) || (] right [ left) || () right ( left) ){return true;}return false;} 题解接口代码: bool isValid(char * s)
{ST ans;StackInit(ans); //创建一个栈int lenth strlen(s); //字符串有效字符个数为奇数直接返回falseif(lenth % 2 1) {return false;}char * tem s; //tem用于遍历字符串while(\0 ! *tem){if(CheckRightQutoe(*tem)) //遇到右括号则入栈{StackPush(ans,*tem);}else //遇到左括号则与栈顶右括号匹配{if(StackEmpty(ans) || !JudgeMatch(*tem,StackTop(ans))){return false; //匹配前注意判断栈是否为空}StackPop(ans); //匹配完后弹出栈顶括号 }tem ;}if(!StackEmpty(ans)) //栈为空说明全部括号都完成了匹配{return false;}return true;
} 该方法充分利用了栈数据后进先出的特点算法的时间复杂度为O(N) 四.用两个队列实现栈(225. 用队列实现栈 - 力扣Leetcode) 本题并没有什么实际意义,求解它的目的仅仅在于加深对栈和队列这两种数据结构的理解 用两个队列实现数据的先进后出题解接口: typedef struct
{} MyStack;//创建MyStack结构体
MyStack* myStackCreate()
{}//向MyStack两个队列成员中的非空队列中插入数据
//(若两个队列都为空则向任意一个队列插入数据都可以)
void myStackPush(MyStack* obj, int x)
{}//删除栈顶元素(同时返回栈顶元素的值)
int myStackPop(MyStack* obj)
{}//栈顶的数据其实就是非空队列尾的数据
int myStackTop(MyStack* obj)
{}//返回栈顶的数据
bool myStackEmpty(MyStack* obj)
{}//销毁栈
void myStackFree(MyStack* obj)
{} 我们可以给自己设置一个规定:用队列实现的栈的接口中,我们只能使用队列的标准操作接口来操作栈中的元素的进出. 本题我们利用本期第二节实现好的队列来实现栈用两个队列实现栈的数据结构总体图解: 两个队列实现一个栈的结构体的定义: typedef struct
{Queue queue1;Queue queue2;
} MyStack; 数据入栈接口: void myStackPush(MyStack* obj, int x) 向MyStack两个队列成员中的非空队列中插入数据(若两个队列都为空则向任意一个队列插入数据都可以) //向MyStack两个队列成员中的非空队列中插入数据
//(若两个队列都为空则向任意一个队列插入数据都可以)
void myStackPush(MyStack* obj, int x)
{if(!QueueEmpty((obj-queue1))){QueuePush((obj-queue1),x);}else{QueuePush((obj-queue2),x);}
} 数据出栈接口: int myStackPop(MyStack* obj) 数据出栈过程动画图解: //删除栈顶元素(同时返回栈顶元素的值)
int myStackPop(MyStack* obj)
{int ret 0;//将非空队列里面的(除了队尾的元素)移到另外一个空队列中if(!QueueEmpty((obj-queue1)) QueueEmpty((obj-queue2))){while(obj-queue1.head ! obj-queue1.tail) //转移数据{QueuePush((obj-queue2),(obj-queue1).head-data);QueuePop((obj-queue1)); }ret QueueFront((obj-queue1)); //记录要弹出的数据QueuePop((obj-queue1)); //弹出数据}else{while(obj-queue2.head ! obj-queue2.tail) //转移数据{QueuePush((obj-queue1),(obj-queue2).head-data);QueuePop((obj-queue2));}ret QueueFront((obj-queue2)); //记录要弹出的数据QueuePop((obj-queue2)); //弹出数据}return ret; //返回被弹出的数据
} 通过两个队列的交互我们便完成了数据的先进后出题解代码: 用于题解的队列: typedef int QDataType;typedef struct QueueNode //队列链表节点结构体
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue //维护队列的结构体
{QNode* head;QNode* tail;
}Queue;void QueueInit(Queue* queue); //队列初始化
void QueueDestroy(Queue* queue); //销毁链表(队列)
void QueuePush(Queue* queue,QDataType val); //链表尾插数据(数据从队列尾入队)
void QueuePop(Queue* queue); //删去链表头节点(数据从队列头部出队)
QDataType QueueFront(Queue* queue); //返回队列头部数据
QDataType QueueBawck(Queue* queue); //返回队列尾部数据
int QueueSize(Queue* queue); //返回队列节点个数
bool QueueEmpty(Queue* queue); //判断队列是否为空void QueueInit(Queue* queue) //队列初始化
{assert(queue);queue-head NULL;queue-tail NULL;
}
void QueueDestroy(Queue* queue) //销毁链表(队列)
{assert(queue);QNode* tem queue-head;while (tem) //逐个节点释放链表{QNode* Next tem-next;free(tem);tem Next;}queue-head NULL;queue-head NULL;
}void QueuePush(Queue* queue,QDataType val) //链表尾插数据(数据从队列尾入队)
{assert(queue);QNode* NewNode (QNode*)malloc(sizeof(QNode));if (NULL NewNode) //在堆区申请节点空间{perror(malloc failed:);exit(-1);}NewNode-data val;NewNode-next NULL;if (NULL queue-tail) //注意判断队列是否为空队列并分类讨论完成元素插入{assert(NULL queue-head);queue-tail NewNode; //队列为空时tail和head指向同一个节点queue-head NewNode;}else{queue-tail-next NewNode; //队列非空时令tail指向队尾数据queue-tail NewNode;}
}void QueuePop(Queue* queue) //删去链表头节点(数据从队列头部出队)
{assert(queue);assert(queue-head queue-tail);QNode* Next queue-head-next;free(queue-head);queue-head Next;if (NULL queue-head) //注意判断完成删除元素后队列是否变为空队列{queue-tail NULL;}
}QDataType QueueFront(Queue* queue) //返回队列头部数据
{assert(queue);assert(queue-head);return queue-head-data;
}
QDataType QueueBawck(Queue* queue) //返回队列尾部数据
{assert(queue);assert(queue-tail);return queue-tail-data;
}int QueueSize(Queue* queue) //返回队列节点个数
{assert(queue);int count 0;QNode* tem queue-head;while(tem) //计算节点个数{count;tem tem-next;}return count;
}bool QueueEmpty(Queue* queue) //判断队列是否为空
{assert(queue);return (NULL queue-head);
} 题解的栈: typedef struct
{Queue queue1;Queue queue2;
} MyStack;//创建MyStack结构体
MyStack* myStackCreate()
{MyStack * tem (MyStack *)malloc(sizeof(MyStack));if(NULL tem){perror(malloc failed:);exit(-1);}QueueInit((tem-queue1));QueueInit((tem-queue2));return tem;
}//向MyStack两个队列成员中的非空队列中插入数据
//(若两个队列都为空则向任意一个队列插入数据都可以)
void myStackPush(MyStack* obj, int x)
{if(!QueueEmpty((obj-queue1))){QueuePush((obj-queue1),x);}else{QueuePush((obj-queue2),x);}
}//删除栈顶元素(同时返回栈顶元素的值)
int myStackPop(MyStack* obj)
{int ret 0;//将非空队列里面的(除了队尾的元素)移到另外一个空队列中if(!QueueEmpty((obj-queue1)) QueueEmpty((obj-queue2))){while(obj-queue1.head ! obj-queue1.tail) //转移数据{QueuePush((obj-queue2),(obj-queue1).head-data);QueuePop((obj-queue1)); }ret QueueFront((obj-queue1)); //记录要弹出的数据QueuePop((obj-queue1)); //弹出数据}else{while(obj-queue2.head ! obj-queue2.tail) //转移数据{QueuePush((obj-queue1),(obj-queue2).head-data);QueuePop((obj-queue2));}ret QueueFront((obj-queue2)); //记录要弹出的数据QueuePop((obj-queue2)); //弹出数据}return ret; //返回被弹出的数据
}//栈顶的数据其实就是非空队列尾的数据
int myStackTop(MyStack* obj)
{if(!QueueEmpty((obj-queue1))){return obj-queue1.tail-data;}else{return obj-queue2.tail-data;}
}//返回栈顶的数据
bool myStackEmpty(MyStack* obj)
{return QueueEmpty((obj-queue1)) QueueEmpty((obj-queue2));
}//销毁栈
void myStackFree(MyStack* obj)
{QueueDestroy((obj-queue1));QueueDestroy((obj-queue2));free(obj);obj NULL;
} 五.用两个栈实现队列(232. 用栈实现队列 - 力扣Leetcode) 思路图解 题解代码: typedef struct
{ST PushStack;ST PopStack;
} MyQueue;MyQueue* myQueueCreate() //队列初始化接口
{MyQueue* tem (MyQueue *)malloc(sizeof(MyQueue));if(NULL tem){perror(malloc failed:);exit(-1);}StackInit((tem-PushStack));StackInit((tem-PopStack));return tem;
}void myQueuePush(MyQueue* obj, int x)
{StackPush((obj-PushStack),x);//数据入队
}int myQueuePop(MyQueue* obj)
{assert(!StackEmpty((obj-PushStack)) || !StackEmpty((obj-PopStack)));//数据出队前保证队列不为空if(StackEmpty((obj-PopStack))) //PopStack为空则要将PushStack数据转移进来{while(!StackEmpty((obj-PushStack))){StackPush((obj-PopStack),StackTop((obj-PushStack)));//将PushStack栈顶数据压入PopStack栈中StackPop((obj-PushStack));//完成数据转移后弹出PushStack的栈顶数据}}int ret StackTop((obj-PopStack)); //记录队头元素StackPop((obj-PopStack)); //元素出队return ret; //返回队头元素
}int myQueuePeek(MyQueue* obj)
{assert(!StackEmpty((obj-PushStack)) || !StackEmpty((obj-PopStack)));//保证队列不为空if(StackEmpty((obj-PopStack))) //PopStack为空则要将PushStack数据转移进来{while(!StackEmpty((obj-PushStack))){StackPush((obj-PopStack),StackTop((obj-PushStack)));//将PushStack栈顶数据压入PopStack栈中StackPop((obj-PushStack));//完成数据转移后弹出PushStack的栈顶数据}}return StackTop((obj-PopStack));//返回PopStack栈顶元素作为队列队头元素
}bool myQueueEmpty(MyQueue* obj)
{return StackEmpty((obj-PopStack)) StackEmpty((obj-PushStack));//判断队列是否为空
}void myQueueFree(MyQueue* obj)
{StackDestroy((obj-PopStack));StackDestroy((obj-PushStack));free(obj);obj NULL;
} 题解中我们运用的是本期第一节中实现好的栈
