栈与队列练习题

作者前言

🎂 ✨✨✨✨✨✨🍧🍧🍧🍧🍧🍧🍧🎂
🎂 作者介绍： 🎂🎂
🎂 🎉🎉🎉🎉🎉🎉🎉 🎂
🎂作者id：老秦包你会， 🎂
简单介绍：🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂
喜欢学习C语言和python等编程语言，是一位爱分享的博主，有兴趣的小可爱可以来互讨 🎂🎂🎂🎂🎂🎂🎂🎂
🎂个人主页::小小页面🎂
🎂gitee页面:秦大大🎂
🎂🎂🎂🎂🎂🎂🎂🎂
🎂 一个爱分享的小博主欢迎小可爱们前来借鉴🎂

练习题

**作者前言**
有效的括号
用队列实现栈
用栈实现队列
总结

有效的括号

有效的括号
在这里插入图片描述
思路: 我们可以使用一个栈来解决这个问题, 我们用栈来存储左括号,当遇见右括号就取出栈顶元素出来比较,如果符合就继续匹配,否则就返回false, 或者最后栈还要数据,或者栈没有数据但还要右括号都是不匹配成功的

typedef char TackDataType;
typedef struct Stack
{TackDataType * a;int top; //栈顶元素int capacity;
}Stack;
//初始化
void TackInit(Stack *pst)
{assert(pst);pst->a = NULL;pst->top = -1;pst->capacity = 0;
}
// 入栈
void TackPush(Stack *pst, TackDataType elemest)
{assert(pst);//判断是否满了if ((pst->top) +1 == pst->capacity){pst->capacity = (pst->capacity == 0? 4 : pst->capacity * 2);TackDataType* tmp = (TackDataType*)realloc(pst->a,sizeof(Stack) * pst->capacity);if (tmp == NULL){perror("realloc");return;}pst->a = tmp;}pst->a[++(pst->top)] = elemest;}
//出栈
void TackPop(Stack *pst)
{assert(pst);if(pst->top != -1)pst->top--;
}
//长度
int TackSize(Stack *pst)
{assert(pst);return (pst->top) + 1;
}
//是否为空
bool TackEmpty(Stack *pst)
{assert(pst);return pst->top == -1; 
}
//栈顶元素
TackDataType TackTop(Stack *pst)
{assert(pst);return pst->a[pst->top];
}
//释放
void TackDestroy(Stack *pst)
{free(pst->a);pst->a = NULL;pst->top = -1;pst ->capacity = 0;
}bool isValid(char* s) 
{Stack pst;//初始化TackInit(&pst);while(*s){if(*s == '{' || *s == '[' || *s == '('){//入栈TackPush(&pst, *s);}else{//是否为空if (TackEmpty(&pst)){TackDestroy(&pst);return false;}//栈顶元素if ((*s == '}' &&  TackTop(&pst) == '{')|| (*s == ']' &&  TackTop(&pst) == '[')||(*s == ')' &&  TackTop(&pst) == '(')){//出栈TackPop(&pst);}else{return false;}}s++;}//是否为空if (!TackEmpty(&pst)){TackDestroy(&pst);return false;}TackDestroy(&pst);    return true;}

用队列实现栈

用队列实现栈
在这里插入图片描述

这道题主要的就是在删除和插入数据中要下点功夫,
插入: 我们只需往不为空的队列插入,因为这样必定有一个队列为空,如果刚开始两个队列都为空,我们只需随意插入一个队列就行
删除: 我们删除栈的栈顶元素,是直接删除最新插入的元素,而队列的特点就是先进先出,我们可以借助空队列把非空队列的最后一个元素保留下来,然后把多余的元素插入到空队列中,需要注意的是,插入的最后一个元素的下一个next一定要修改为NULL,不然在释放会有野指针,然后保留的最后一个元素再free掉,
剩下的就是释放空间:
我们要先释放掉链表的空间,然后再释放两个队列的空间,

删除:
在这里插入图片描述

typedef int QDataType;
//链表节点
typedef struct QNode
{QDataType val;struct QNode *next;
}QNode;
//队列结构
typedef struct Queue
{QNode* head;QNode* tail; //队尾int size;
}Queue;//创建两个队列
typedef struct
{Queue stack1;Queue stack2;} MyStack;MyStack* myStackCreate() 
{//创建两个队列MyStack * Queuetack = (MyStack*)malloc(sizeof(MyStack));//创建哨兵位Queuetack->stack1.head = (QNode*)malloc(sizeof(QNode));Queuetack->stack1.head->next = NULL;Queuetack->stack1.size = 0;Queuetack->stack1.tail = Queuetack->stack1.head;//创建哨兵位Queuetack->stack2.head = (QNode*)malloc(sizeof(QNode));Queuetack->stack2.head->next = NULL;Queuetack->stack2.size = 0;Queuetack->stack2.tail = Queuetack->stack2.head;return Queuetack;}void myStackPush(MyStack* obj, int x) 
{assert(obj);if (obj->stack2.size){//创建节点QNode* newnode = (QNode*)malloc(sizeof(QNode));newnode->val = x;newnode->next = NULL;//插入obj->stack2.tail->next = newnode;obj->stack2.tail = newnode;obj->stack2.size++;}else{//创建节点QNode* newnode = (QNode*)malloc(sizeof(QNode));assert(newnode);newnode->val = x;newnode->next = NULL;//插入obj->stack1.tail->next = newnode;obj->stack1.tail = newnode;obj->stack1.size++;}
}int myStackPop(MyStack* obj) 
{if (!obj->stack2.size && !obj->stack1.size)return 0;if (obj->stack2.size){while (obj->stack2.head->next != obj->stack2.tail){QNode* node = obj->stack2.head->next;obj->stack2.head->next = node->next;obj->stack1.tail->next = node;obj->stack1.tail = node;obj->stack1.size++;}obj->stack1.tail->next = NULL;int a = obj->stack2.tail->val;free(obj->stack2.tail);obj->stack2.tail = obj->stack2.head;obj->stack2.head->next = NULL;obj->stack2.size = 0;return a;}else{while (obj->stack1.head->next != obj->stack1.tail){QNode* node = obj->stack1.head->next;obj->stack1.head->next = node->next;obj->stack2.tail->next = node;obj->stack2.tail = node;obj->stack2.size++;}obj->stack2.tail->next = NULL;int a = obj->stack1.tail->val;free(obj->stack1.tail);obj->stack1.tail = obj->stack1.head;obj->stack1.head->next = NULL;obj->stack1.size = 0;return a;}}int myStackTop(MyStack* obj) 
{if (!obj->stack2.size && !obj->stack1.size)return 0;if (!obj->stack2.size){return obj->stack1.tail->val;}else{return obj->stack2.tail->val;}
}bool myStackEmpty(MyStack* obj) 
{return obj->stack2.size== 0 && obj->stack1.size ==0;
}void myStackFree(MyStack* obj) 
{QNode *cur = obj->stack1.head->next;while(cur){QNode *cur1 = cur->next;free(cur);cur = cur1;}free(obj->stack1.head);obj->stack1.head = NULL;obj->stack1.size = 0;obj->stack1.tail = NULL;cur = obj->stack2.head->next;while(cur){QNode *cur1 = cur->next;free(cur);cur = cur1;}free(obj->stack2.head);obj->stack2.head = NULL;obj->stack2.size = 0;obj->stack2.tail = NULL;free(obj);
}

用栈实现队列

在这里插入图片描述
这道题的思路和上面的题目思路是相同的,我们借助两个栈来实现队列,
有点差别就是
删除:

删除我们不能从top那边开始拉数据,而是要从left开始,
我们还要注意的就是队列插入的时候一定判断栈是否要扩大空间,

typedef int StackDAtaType;
typedef struct Stack
{StackDAtaType *data;int top;//栈顶元素下一个int capacity;}Stack;typedef struct 
{Stack stack1;Stack stack2;
} MyQueue;MyQueue* myQueueCreate() 
{//初始化MyQueue *queue = (MyQueue*)malloc(sizeof(MyQueue));//第一个栈queue->stack1.data = NULL;queue->stack1.top = 0;//栈顶元素的下一个queue->stack1.capacity = 0;//第二个栈queue->stack2.data = NULL;queue->stack2.top = 0;queue->stack2.capacity = 0;return queue;
}void myQueuePush(MyQueue* obj, int x) 
{if(obj->stack1.top){//第一个栈插入//判断是否满栈if(obj->stack1.top == obj->stack1.capacity){obj->stack1.capacity = (obj->stack1.capacity == 0 ? 4 : obj->stack1.capacity * 2);StackDAtaType *tmp =  (StackDAtaType*)realloc(obj->stack1.data, sizeof(StackDAtaType) * obj->stack1.capacity);if (tmp == NULL){perror("realloc");return ;}obj->stack1.data = tmp;}obj->stack1.data[obj->stack1.top++] = x;}else{//第二个栈插入//判断是否满栈if(obj->stack2.top == obj->stack2.capacity){obj->stack2.capacity = (obj->stack2.capacity == 0 ? 4 : obj->stack2.capacity * 2);StackDAtaType *tmp =  (StackDAtaType*)realloc(obj->stack2.data, sizeof(StackDAtaType) * obj->stack2.capacity);if (tmp == NULL){perror("realloc");return ;}obj->stack2.data = tmp;}obj->stack2.data[obj->stack2.top++] = x;}
}int myQueuePop(MyQueue* obj)
{if (!obj->stack2.top && !obj->stack1.top)return 0;//判断是否满栈if (obj->stack1.top == obj->stack1.capacity){obj->stack1.capacity = (obj->stack1.capacity == 0 ? 4 : obj->stack1.capacity * 2);StackDAtaType* tmp = (StackDAtaType*)realloc(obj->stack1.data, sizeof(StackDAtaType) * obj->stack1.capacity);if (tmp == NULL){perror("realloc");return 0;}obj->stack1.data = tmp;}//判断是否满栈if (obj->stack2.top == obj->stack2.capacity){obj->stack2.capacity = (obj->stack2.capacity == 0 ? 4 : obj->stack2.capacity * 2);StackDAtaType* tmp = (StackDAtaType*)realloc(obj->stack2.data, sizeof(StackDAtaType) * obj->stack2.capacity);if (tmp == NULL){perror("realloc");return 0;}obj->stack2.data = tmp;}int a = 1;if (obj->stack2.top){//取出第二栈的元素 插入到第一栈while (obj->stack2.top > a){obj->stack1.data[obj->stack1.top] = obj->stack2.data[a++];obj->stack1.top++;}obj->stack2.top = 0;return obj->stack2.data[obj->stack2.top];}else{//取出第一栈的元素 插入到第二栈while (obj->stack1.top > a){obj->stack2.data[obj->stack2.top++] = obj->stack1.data[a++];}obj->stack1.top = 0;return obj->stack1.data[obj->stack1.top];}}int myQueuePeek(MyQueue* obj) 
{if(!obj->stack2.top && !obj->stack1.top)return 0;if(obj->stack2.top){return obj->stack2.data[0];}else{return obj->stack1.data[0];}}bool myQueueEmpty(MyQueue* obj) 
{return obj->stack1.top == 0 && obj->stack2.top == 0;
}void myQueueFree(MyQueue* obj) 
{free(obj->stack1.data);obj->stack1.data = NULL;obj->stack1.top = 0;obj->stack1.capacity = 0;free(obj->stack2.data);obj->stack2.data = NULL;obj->stack2.top = 0;obj->stack2.capacity = 0;free(obj);}