【手撕数据结构】栈和队列高频面试题

目录括号匹配问题用队列实现栈用栈实现队列括号匹配问题给定一个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串 s 判断字符串是否有效。有效字符串需满足1.左括号必须用相同类型的右括号闭合。2.左括号必须以正确的顺序闭合。3.每个右括号都有一个对应的相同类型的左括号。要求时间复杂度O(n)题目解析:根据第一条要求可知,必须是如(),[],{}这类同类型的闭合第二条则是告诉我们只有[()]这种顺顺序闭合,不能出现[(])这种第三条则是告诉我们,右括号一定有一个相同类型的左括号示例 1输入s “()”输出true示例 2输入s “()[]{}”输出true示例 3输入s “(]”输出false思路:该题是栈的典型应用满足后进先出的规则后入栈的前括号将优先与先出现的后括号相匹配遍历字符串遇到前括号直接入栈。遇到后括号判断该后括号与栈顶的前括号是否匹配若此时栈为空该括号没有匹配的前括号入栈如]若不匹配则字符串无效若匹配则删除栈顶元素继续遍历字符串直到字符串遍历完毕。当字符串遍历完后检测栈是否为空若为空则字符串有效(解决了只有入栈前括号没有后括号匹配出栈问题如(( )若不为空说明有前括号未匹配字符串无效。typedefcharSTDataType;//方便以后修改栈的存储数据类型typedefstructStack{STDataType*arr;inttop;intcapacity;}ST;voidSTDestroy(ST*ps){assert(ps);if(ps-arr){free(ps-arr);ps-arrNULL;ps-capacityps-top0;}}voidSTInit(ST*ps){assert(ps);ps-arrNULL;ps-capacityps-top0;}boolSTEmpty(ST*ps){assert(ps);returnps-top0;}voidSTPush(ST*ps,STDataType x){assert(ps);//检查空间是否足够if(ps-topps-capacity){intNewCapacityps-capacity0?4:2*ps-capacity;STDataType*tmp(STDataType*)realloc(ps-arr,NewCapacity*sizeof(STDataType));//有可能开辟空间失败if(tmpNULL){perror(realloc failed);exit(1);}else{ps-arrtmp;ps-capacityNewCapacity;}}ps-arr[ps-top]x;}voidSTPop(ST*ps){assert(ps);assert(!STEmpty(ps));//不要忘记判空栈必须得有数据才能出栈ps-top--;}STDataTypeSTTop(ST*ps){assert(ps);assert(!STEmpty(ps));returnps-arr[ps-top-1];}boolisValid(char*s){char*pss;ST st;STInit(st);while(*ps!\0){if(*ps(||*ps{||*ps[){STPush(st,*ps);}else{if(STEmpty(st)){returnfalse;}charretSTTop(st);if((ret(*ps))||(ret[*ps])||(ret{*ps})){STPop(st);}else{STDestroy(st);returnfalse;}}ps;}bool retSTEmpty(st)true;//这里必须要栈为空为空表示每个括号匹配成功,不为空表示没匹配到比如只有一个[STDestroy(st);returnret;}用队列实现栈请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通队列的全部四种操作push、top、pop 和 empty。实现 MyStack 类void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的返回 true 否则返回 false 。思路使用两个队列来回倒数据如果需要入栈随便从其中选一个队列进行入栈操作。如果需要出栈则将有数据的队列的size-1个元素移倒另外一个空队列中将剩下的元素进行出栈。以此类推。注意取栈顶元素很容易与出栈一样的操作误认为只需要不进行删除就行。但是我们进行入栈和出栈的前提是一定有一个空的队列进行移动所以我们只需取栈尾元素即可typedefintQDataType;//方便以后修改存储的数据类型typedefstructQueueNode//队列中的节点{QDataType val;structQueueNode*next;}QueueNode;typedefstructQueue{QueueNode*phead;QueueNode*ptail;intsize;//不要忘了保存数列的有效数据个数}Queue;voidQueueInit(Queue*pq){assert(pq);pq-pheadpq-ptailNULL;pq-size0;}boolQEmpty(Queue*pq){assert(pq);returnpq-size0;}QueueNode*QBuyNode(QDataType x){QueueNode*tmp(QueueNode*)malloc(sizeof(QueueNode));if(tmpNULL){perror(malloc failed);exit(1);}tmp-valx;tmp-nextNULL;returntmp;}voidQueuePush(Queue*pq,QDataType x){assert(pq);QueueNode*newnodeQBuyNode(x);//注意考虑队列为空的情况if(pq-pheadNULL)//队列为空{pq-pheadpq-ptailnewnode;}else{pq-ptail-nextnewnode;pq-ptailnewnode;}pq-size;}voidQueuePop(Queue*pq){assert(pq);assert(!QEmpty(pq));//只有一个结点的情况避免ptail变成野指针if(pq-ptailpq-phead){free(pq-phead);pq-pheadpq-ptailNULL;}else{//删除队头元素、QueueNode*nextpq-phead-next;free(pq-phead);pq-pheadnext;}--pq-size;}QDataTypeQueueFront(Queue*pq){assert(pq);assert(!QEmpty(pq));//assert为假会触发returnpq-phead-val;}QDataTypeQueueBack(Queue*pq){assert(pq);assert(!QEmpty(pq));//assert为假会触发returnpq-ptail-val;}intQueueSize(Queue*pq){assert(pq);returnpq-size;}voidQueueDestroy(Queue*pq){assert(pq);while(pq-phead!pq-ptail){QueueNode*delpq-phead;pq-pheadpq-phead-next;free(del);delNULL;}free(pq-phead);pq-pheadNULL;pq-ptailNULL;//不要忘了把ptail也设置NULL,虽然他们是指向同一块空间但是指针变量不是同一块空间pq-size0;//不要忘了把size设置0}//用两个队列来实现栈typedefstruct{Queue q1;Queue q2;}MyStack;MyStack*myStackCreate(){MyStack*pst(MyStack*)malloc(sizeof(MyStack));QueueInit(pst-q1);QueueInit(pst-q2);returnpst;}voidmyStackPush(MyStack*obj,intx){if(!QEmpty(obj-q1)){QueuePush(obj-q1,x);}else{QueuePush(obj-q2,x);}}intmyStackPop(MyStack*obj){//找不为空的队列Queue*EmpQobj-q1;//这里obj-q1是第一个队列的地址假设q1为空Queue*NoneQobj-q2;if(!QEmpty(obj-q1)){NoneQobj-q1;EmpQobj-q2;}//将不为空队列中size-1个数据倒入到空队列中while(QueueSize(NoneQ)1){intfrontQueueFront(NoneQ);QueuePush(EmpQ,front);QueuePop(NoneQ);}//非空队列只剩下一个数据intpopQueueFront(NoneQ);QueuePop(NoneQ);//出栈也要删除数据returnpop;}//取栈顶元素一定要保证两个队列其中一个队列为空这里很容易把出栈复制过来删掉pop就是出栈但是删掉pop后那么两个队列都不为空出栈和入栈就不能根据为空进行操作了//所以这里直接进行取队尾元素进行取栈顶元素intmyStackTop(MyStack*obj){if(!QEmpty(obj-q1)){returnQueueBack(obj-q1);}else{returnQueueBack(obj-q2);}}boolmyStackEmpty(MyStack*obj){returnQEmpty(obj-q1)QEmpty(obj-q2);}voidmyStackFree(MyStack*obj){QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);objNULL;}/** * Your MyStack struct will be instantiated and called as such: * MyStack* obj myStackCreate(); * myStackPush(obj, x); * int param_2 myStackPop(obj); * int param_3 myStackTop(obj); * bool param_4 myStackEmpty(obj); * myStackFree(obj); */用栈实现队列请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty。实现 MyQueue 类void push(int x) 将元素 x 推到队列的末尾。int pop() 从队列的开头移除并返回元素。int peek() 返回队列开头的元素。boolean empty() 如果队列为空返回 true 否则返回 false。思路与用队列实现栈思路基本一样用一个栈来入队列一个栈来出队列。如果要出队列就把入队列的栈一直取栈顶导入为空的出队列中,这样原本1 2 3 4 的由于先进后出就达到了另外一栈存储的是4 3 2 1 这样的顺序符合队列的先进先出原则。如果要取队头元素也只需将出队列的栈取栈顶元素即可。typedefintSTDataType;//方便以后修改栈的存储数据类型typedefstructStack{STDataType*arr;inttop;intcapacity;}ST;voidSTInit(ST*ps){assert(ps);ps-arrNULL;ps-capacityps-top0;}voidSTDestroy(ST*ps){assert(ps);if(ps-arr){free(ps-arr);ps-arrNULL;ps-capacityps-top0;}}boolSTEmpty(ST*ps){assert(ps);returnps-top0;}voidSTPush(ST*ps,STDataType x){assert(ps);//检查空间是否足够if(ps-topps-capacity){intNewCapacityps-capacity0?4:2*ps-capacity;STDataType*tmp(STDataType*)realloc(ps-arr,NewCapacity*sizeof(STDataType));//有可能开辟空间失败if(tmpNULL){perror(realloc failed);exit(1);}else{ps-arrtmp;ps-capacityNewCapacity;}}ps-arr[ps-top]x;}voidSTPop(ST*ps){assert(ps);assert(!STEmpty(ps));//不要忘记判空栈必须得有数据才能出栈ps-top--;}STDataTypeSTTop(ST*ps){assert(ps);assert(!STEmpty(ps));returnps-arr[ps-top-1];}STSize(ST*ps){assert(ps);returnps-top;}typedefstruct{ST PushST;ST PopST;}MyQueue;MyQueue*myQueueCreate(){MyQueue*pst(MyQueue*)malloc(sizeof(MyQueue));STInit(pst-PushST);STInit(pst-PopST);returnpst;}voidmyQueuePush(MyQueue*obj,intx){STPush(obj-PushST,x);}intmyQueuePop(MyQueue*obj){//1.检查popst是否为空//不为空出数据//为空从pushst倒数据if(STEmpty(obj-PopST)){while(!STEmpty(obj-PushST)){STPush(obj-PopST,STTop(obj-PushST));STPop(obj-PushST);}}inttopSTTop(obj-PopST);STPop(obj-PopST);returntop;}intmyQueuePeek(MyQueue*obj){if(STEmpty(obj-PopST)){while(!STEmpty(obj-PushST)){STPush(obj-PopST,STTop(obj-PushST));STPop(obj-PushST);}}returnSTTop(obj-PopST);}boolmyQueueEmpty(MyQueue*obj){returnSTEmpty(obj-PushST)STEmpty(obj-PopST);}voidmyQueueFree(MyQueue*obj){STDestroy(obj-PushST);STDestroy(obj-PopST);free(obj);objNULL;}/** * Your MyQueue struct will be instantiated and called as such: * MyQueue* obj myQueueCreate(); * myQueuePush(obj, x); * int param_2 myQueuePop(obj); * int param_3 myQueuePeek(obj); * bool param_4 myQueueEmpty(obj); * myQueueFree(obj); */