找个网站懂的网站,WordPress 简历库,外国网站的风格,防疫措施优化1. 栈#xff08;Stack#xff09;
1.1 栈的概念与结构
栈是一种特殊的线性表#xff0c;其只允许固定的一段插入和删除操作#xff1b;进行数据插入和删除的一段叫做栈顶#xff0c;另一端叫栈底#xff1b;栈中的元素符合后进先出LIFO#xff08;Last In First OutStack
1.1 栈的概念与结构
栈是一种特殊的线性表其只允许固定的一段插入和删除操作进行数据插入和删除的一段叫做栈顶另一端叫栈底栈中的元素符合后进先出LIFOLast In First Out的原则。入栈入栈就是往栈里放入数据出栈出栈就是从栈里拿出数据注意这两个操作都是对栈顶的数据进行操作 栈底层结构选型栈的实现选用的是数组选用链表也可以但在插入和删除操作更方便一些因为链表尾插需要遍历找到尾结点那么尾插的操作时间复杂度就为O(N)不过我们可以优化一下拿链表的头部作为栈顶插入和删除就为O(1)了但是由于我们可能还需要创建多个指针进行操作所以最优还是选择数组因为数据的尾插和尾删时间复杂度都为O(1)而且找到尾部的位置不需要创建什么指针啥的因为顺序表里本身就有一个size代表数组的大小而最后一个位置则是下标为size-1的位置
1.2 栈的实现 --定义栈的模型 由于栈底层可以使用顺序表实现那就和之前顺序表一样需要一个计算总空间有多大的capacity和一个储存有效元素个数的top在顺序表其实就是size但这里为了符合栈所以用top还有一个储存整型类型的数组但后面会出现增容的操作所以使用指针STDateType* arr如下代码所示
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int STDatetype;typedef struct Stack
{STDatetype* arr;int capacity; //栈空间大小int top; //栈顶
}ST; --栈的初始化和销毁
void STInit(ST* st)
{assert(st);st-arr NULL;st-capacity st-top 0;
}void STDestory(ST* st)
{assert(st);if(st-arr)free(st-arr);st-arr NULL;st-capacity st-top 0;
} --入栈操作的实现 入栈的实现首先我们要判空间是否足够而判断空间是否足够的条件就是栈顶是不是等于整个数组空间的容量如果等于就需要使用realloc进行扩容那么我们就需要创建一个Newcapacity作为扩容的空间我们按2倍进行扩容则2* capacity 但是如果说capacity为0的话那么就无法进行扩容因为0 * 任何数都等于0所以我们写一个三目运算符如果说capacity等于0的话就让Newcapacity等于4否则等于2* capacity后面我们就需要创建一个新的指针指向扩容的空间因为如果说扩容失败的话就会对整块空间造成影响所以我们需要创建一个新的空间进行扩容而入栈的实现其实就是在数组最后面插入元素代码实现如下
void StackPush(ST* ps, STDatetype x)
{assert(ps);if (ps-capacity ps-top ){int Newcapacity ps-capacity 0 ? 4 : 2 * ps-capacity;STDatetype* temp (STDatetype*)realloc(ps-arr, Newcapacity *sizeof(STDatetype) );if (temp NULL){perror(realloc fail!);exit(1);}ps-arr temp;ps-capacity Newcapacity;}ps-arr[ps-top] x;
} --判断栈是否为空 判空实现其实就是看看栈顶是否为0当栈顶都为0那肯定就是没有数据了代码实现如下
bool StackEmpty(ST* ps)
{assert(ps);return ps-top 0;
}--出栈操作的实现 出栈的实现实际上其实就是顺序表进行尾删操作那我们就直接让数组内的有效元素减少一个就可以即size--但是我们还需要判断栈是否为空如果为空那就没有元素可以出代码如下
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));--ps-top;
} --取栈顶元素 取栈顶元素取栈顶元素则是直接返回数组的尾部元素即是ps-arr[ps-top-1]为什么要-1因为top是有效元素的个数但下标的起始位置是0所以要-1如下代码所示
//取栈顶元素
STDatetype StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps-arr[ps-top-1];
}--获得栈中有效元素的个数 由上可知有效元素的个数其实就是top所以直接返回即可如下代码所示
//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps-top;
}1.3 栈的完整代码
Stack.h
#pragma once#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int STDatetype;typedef struct Stack
{STDatetype* arr;int capacity; //栈空间大小int top; //栈顶
}ST;//首先创建这些都是要实现初始化
void STInit(ST* st);
void STDestory(ST* st);//栈顶---入数据、出数据
void StackPush(ST* ps, STDatetype x);
void StackPop(ST* ps);//取栈顶元素
STDatetype StackTop(ST* ps);bool StackEmpty(ST* ps);//获取栈中有效元素个数
int STSize(ST* ps);
Stack.cpp
#includeStack.hvoid STInit(ST* st)
{assert(st);st-arr NULL;st-capacity st-top 0;
}
void STDestory(ST* st)
{assert(st);if(st-arr)free(st-arr);st-arr NULL;st-capacity st-top 0;
}void StackPush(ST* ps, STDatetype x)
{assert(ps);if (ps-capacity ps-top ){int Newcapacity ps-capacity 0 ? 4 : 2 * ps-capacity;STDatetype* temp (STDatetype*)realloc(ps-arr, Newcapacity *sizeof(STDatetype) );if (temp NULL){perror(realloc fail!);exit(1);}ps-arr temp;ps-capacity Newcapacity;}ps-arr[ps-top] x;
}bool StackEmpty(ST* ps)
{assert(ps);return ps-top 0;
}void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));--ps-top;
}//取栈顶元素
STDatetype StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps-arr[ps-top-1];
}//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps-top;
} 2. 队列Queue
2.1 队列的概念与结构
概念只允许在一端插入数据和从另一端进行删除数据操作的特殊线性表队列具有先进先出FIFOFirst In First Out入队列进行插入操作的一端称为队尾出队列进行删除操作的一端称为队头队列的底层结构选型队列底层结构选的是链表因为要进行入队列和出队列的操作如果说用顺序表的话在进行出队列的操作的时候删除了头部数据那就得让后面数据往前走那时间复杂度就为O(N)所以我们使用链表但使用链表的时候要注意我们需要头结点出数据实现出队列操作尾结点入数据实现入队列操作不然的话我们要遍历到尾结点删除数据实现出队列 时间复杂度又为O(N)了
2.2 队列的实现 --定义队列的模型 队列的底层实现就是用链表来实现那么我们就要定义结点还有队列的模型为什么要定义两个呢因为我们还需要一个指向头结点和指向尾结点的指针还有一个整型size记录队列内的数据
#pragma once
#includeiostream
#includestdlib.h
#includeassert.h
using namespace std;typedef int QDataType;
//每个结点
typedef struct QueueNode
{QDataType data;QueueNode* next;
}QueueNode;//队列
typedef struct Queue
{QueueNode* phead;QueueNode* tail;int size;
}Queue;--队列的初始化和销毁 队列的销毁其实就和链表的销毁一样首先创建一个指向头结点下一个节点的next指针然后把头结点销毁掉在让头结点指针指向next指针next指针再走向头结点的下一个指针一直循环到头结点为NULL的时候结束‘代码如下
void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-tail NULL;pq-size 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* pcur pq-phead;while (pcur){QueueNode* next pcur-next;free(pcur);pcur next;}pq-phead pq-tail NULL;pq-size 0;
}--入队列的实现 入队列的实现需要结合链表的buynode动态申请一个结点空间来实现首先我们先申请一个newnode的空间让其指向空data x再就要判断队列是否为空如果说队列为空的话那就说明队列里面没有结点那就需要让phead和ptail指针指向该结点如果有结点的话就让ptail-next指针指向newnode再让ptail走到newnode的位置最后还要记得size因为size是计算队列内有效元素的个数如下图和代码所示
队列为空
队列不为空
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode));if (newnode NULL){perror(malloc fail!);exit(1);}newnode-data x;newnode-next NULL;//说明链表为空if (pq-phead NULL){pq-phead pq-tail newnode;}else{pq-tail-next newnode;pq-tail pq-tail-next;}pq-size;
} --队列判空操作 队列判空其实就是看头结点和尾结点的指针是否都指向NULL如果都指向NULL就为空代码如下
//队列判空
bool QueueEmpty(Queue* pq)
{return pq-phead NULL pq-tail NULL;
} --出队列的操作 出队列的操作本质上就是链表删除头结点我们只需要定义一个Del指针指向当前的头结点pcur再让当前的头结点走到头结点的下一个结点pcur pcur-next然后free掉Del结点即可图和代码如下
// 出队列队头
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//只有一个结点if (pq-tail pq-phead){free(pq-phead);pq-phead NULL;pq-tail NULL;}else{QueueNode* Del pq-phead;pq-phead pq-phead-next;free(Del);}--pq-size;
}
注意我们还需要单独判断只有一个结点的时候当ptail和phead都指向同一个空间的时候就代表队列中只有一个结点那么这时候我们还进行phead phead-next就是让phead走向一块未知的空间进行非法访问 --取队头和队尾数据 因为有指针指向队头和队尾就不过多阐述了注意一点就是我们要判断队列是否为空代码如下所示
//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-phead-data;
}
//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
} --取队列有效元素个数 因为我们一开始就已经创建了一个size 对队列的有效元素个数进行记录所以直接返回size即可如下代码所示
//队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
} 2.3 队列的完整代码
Queue.h
#pragma once
#includeiostream
#includestdlib.h
#includeassert.h
using namespace std;typedef int QDataType;
//每个结点
typedef struct QueueNode
{QDataType data;QueueNode* next;
}QueueNode;//队列
typedef struct Queue
{QueueNode* phead;QueueNode* tail;int size;
}Queue;void QueueInit(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
// 出队列队头
void QueuePop(Queue* pq);//队列判空
bool QueueEmpty(Queue* pq);//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);//销毁队列
void QueueDestroy(Queue* pq);
Queue.cpp
#includeQueue.hvoid QueueInit(Queue* pq)
{assert(pq);pq-phead pq-tail NULL;pq-size 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode));if (newnode NULL){perror(malloc fail!);exit(1);}newnode-data x;newnode-next NULL;//说明链表为空if (pq-phead NULL){pq-phead pq-tail newnode;}else{pq-tail-next newnode;pq-tail pq-tail-next;}pq-size;
}//队列判空
bool QueueEmpty(Queue* pq)
{return pq-phead NULL pq-tail NULL;
}// 出队列队头
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//只有一个结点if (pq-tail pq-phead){free(pq-phead);pq-phead NULL;pq-tail NULL;}else{QueueNode* Del pq-phead;pq-phead pq-phead-next;free(Del);}--pq-size;
}//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-phead-data;
}
//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}
//队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* pcur pq-phead;while (pcur){QueueNode* next pcur-next;free(pcur);pcur next;}pq-phead pq-tail NULL;pq-size 0;
}3.栈和队列的OJ题
3.1 有效的括号
原题链接20. 有效的括号 - 力扣LeetCode 思路我们可以创建一个栈先把开口向右的括号全部入栈里面当栈不为空的时候取栈顶元素这步的操作其实就是实现当有【 这三个括号的时候能直接取到(然后再和左开口的括号进行比较如果说取出的栈顶元素是“(”并且数组的下一个元素是“”的话就是匹配上了然后pos当不符合的时候直接返回false如果不返回false一直到循环结束的时候就返回true因为这说明全部括号都匹配上了如下图和代码所示
#includestdbool.h
typedef char STDateType;
typedef struct Stack
{STDateType* arr;int top ;int capacity;
}ST;void STInit(ST* st)
{st-arrNULL;st-top 0;st-capacity 0;
}void STPush(ST* st, STDateType x)
{if(st-capacityst-top){int Newcapacity st-capacity0?4:2*st-capacity;STDateType* temp (STDateType*)realloc(st-arr, Newcapacity* sizeof(STDateType));if(tempNULL){perror(realloc fails!);exit(1);}st-arr temp;st-capacity Newcapacity;}st-arr[st-top] x;
}bool STempty(ST* st)
{return st-top0;
}STDateType StackTop(ST* st)
{return st-arr[st-top-1];
}void STPop(ST* st)
{assert(!STempty(st));--st-top;
}void STDestory(ST* st)
{free(st-arr);st-arr NULL;st-capacity 0;st-top 0;
}bool isValid(char* s)
{ST st;STInit(st);char* ps s;while(*ps!\0){if(*ps(||*ps{||*ps[){STPush(st, *ps);}else{if(STempty(st)){return false;}char ch StackTop(st);if((*ps)ch()||(*ps]ch[)||(*ps}ch{)){STPop(st);}else{STDestory(st);return false;}}ps;}bool ret STempty(st)true;STDestory(st);return ret;
}
这里还有几个需要注意的点是
当栈为空的时候就代表没有开口向右的括号那就没有意义再进行下去了因为没有括号可以匹配在我们取栈顶元素比较完后要删除比较过的元素因为取栈顶元素只是取值并没有实现取并删到最后我们需要判断栈是否为空栈不为空则说明多出了一个开口向右的括号例如{ [ ( ) ]这样是不符合的 3.2 用队列实现栈
原题链接225. 用队列实现栈 - 力扣LeetCode 思路首先我们先分析队列是先进先出栈是后进先出那我们就先来使用1234进行模拟如果把1234放到栈里面再取出来的话就是4321
那么如果说我们想用两个队列来实现的话就得换一种思路因为队列是先进先出那么我们就可以尝试先把数据放到一个队列里面然后把size-1个数据放到另一个空队列里面再把剩下的那个数据取出来一直这样循环如下图所示
typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;//队列
typedef struct Queue
{QueueNode* phead;QueueNode* tail;int size;
}Queue;
void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-tail NULL;pq-size 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode));if (newnode NULL){perror(malloc fail!);exit(1);}newnode-data x;newnode-next NULL;//说明链表为空if (pq-phead NULL){pq-phead pq-tail newnode;}else{pq-tail-next newnode;pq-tail pq-tail-next;}pq-size;
}//队列判空
bool QueueEmpty(Queue* pq)
{return pq-phead NULL pq-tail NULL;
}// 出队列队头
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//只有一个结点if (pq-tail pq-phead){free(pq-phead);pq-phead NULL;pq-tail NULL;}else{QueueNode* Del pq-phead;pq-phead pq-phead-next;free(Del);}--pq-size;
}//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-phead-data;
}
//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}
//队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* pcur pq-phead;while (pcur){QueueNode* next pcur-next;free(pcur);pcur next;}pq-phead pq-tail NULL;pq-size 0;
}typedef struct
{Queue q1;Queue q2;
} MyStack;//初始化
MyStack* myStackCreate()
{MyStack* temp (MyStack*)malloc(sizeof(MyStack));QueueInit(temp-q1);QueueInit(temp-q2);return temp;
}void myStackPush(MyStack* obj, int x)
{//首先我们找哪个队列为空if(!QueueEmpty(obj-q1)){QueuePush(obj-q1,x);}elseQueuePush(obj-q2,x);
}int myStackPop(MyStack* obj)
{Queue* empQ obj-q1;Queue* noneQ obj-q2;if(!QueueEmpty(obj-q1)){noneQ obj-q1;empQ obj-q2;}while(QueueSize(noneQ)1) //大于1的原因是要留一个数据{int front QueueFront(noneQ);QueuePush(empQ, front);QueuePop(noneQ);}int pop QueueFront(noneQ);QueuePop(noneQ);return pop;
}int myStackTop(MyStack* obj)
{if(!QueueEmpty(obj-q1)){return QueueBack(obj-q1);}else{return QueueBack(obj-q2);}
}bool myStackEmpty(MyStack* obj)
{ return QueueEmpty(obj-q1)QueueEmpty(obj-q2);
}void myStackFree(MyStack* obj)
{QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);obj NULL;}
3.3 用栈实现队列
原题链接232. 用栈实现队列 - 力扣LeetCode 思路首先我们分析用两个栈实现队列的话栈是先进后出而队列是先进先出我们使用1234来进行模拟
队列是怎么进怎么出1234进1234出
那么我们来看一下首先是堆如果说我们直接把1234放进去再取出来的话那就是4321但是我们通过两个堆可以改变这个先让1234入一个名为pushST的堆然后再让pushST堆的数据堆顶数据入一个名为popST的堆这时候popST的堆的数据就为1234了再取出来即可那么用栈实现队列push数据到队列末尾的则只需要直接把数据放到堆顶即可删除数据就如刚刚上面所说取堆顶然后把最后一个数据留下来再把该数据删除就可以实现取队头元素的实现也是如此判空则是看两个堆是否都为空都为空返回1即可如下图和代码所示
typedef int STDatetype;typedef struct Stack
{STDatetype* arr;int capacity; //栈空间大小int top; //栈顶
}ST;void STInit(ST* st)
{st-arr NULL;st-capacity st-top 0;
}
void STDestory(ST* st)
{if(st-arr)free(st-arr);st-arr NULL;st-capacity st-top 0;
}void StackPush(ST* ps, STDatetype x)
{if (ps-capacity ps-top ){int Newcapacity ps-capacity 0 ? 4 : 2 * ps-capacity;STDatetype* temp (STDatetype*)realloc(ps-arr, Newcapacity *sizeof(STDatetype) );if (temp NULL){perror(realloc fail!);exit(1);}ps-arr temp;ps-capacity Newcapacity;}ps-arr[ps-top] x;
}bool StackEmpty(ST* ps)
{return ps-top 0;
}void StackPop(ST* ps)
{assert(!StackEmpty(ps));--ps-top;
}//取栈顶元素
STDatetype StackTop(ST* ps)
{return ps-arr[ps-top-1];
}//获取栈中有效元素个数
int STSize(ST* ps)
{return ps-top;
}typedef struct
{ST pushST;ST popST;
} MyQueue;MyQueue* myQueueCreate()
{MyQueue* pst (MyQueue*)malloc(sizeof(MyQueue));STInit(pst-pushST);STInit(pst-popST);return pst;
}void myQueuePush(MyQueue* obj, int x)
{StackPush(obj-pushST, x);
}int myQueuePop(MyQueue* obj)
{if(StackEmpty(obj-popST)){//为空就把pushST的数据放到popST里面来while(!StackEmpty(obj-pushST)){StackPush(obj-popST,StackTop(obj-pushST));StackPop(obj-pushST);}}int top StackTop(obj-popST);StackPop(obj-popST);return top;
}int myQueuePeek(MyQueue* obj)
{if(StackEmpty(obj-popST)){while(!StackEmpty(obj-pushST)){StackPush(obj-popST, StackTop(obj-pushST));StackPop(obj-pushST);}}return StackTop(obj-popST);
}bool myQueueEmpty(MyQueue* obj)
{return StackEmpty(obj-pushST) StackEmpty(obj-popST);
}void myQueueFree(MyQueue* obj)
{STDestory(obj-pushST);STDestory(obj-popST);free(obj);obj NULL;
} END!
