做宣传的网站,外贸网站推广企业,昆明网站seo优化,乐平城市建设局网站孜孜不倦#xff1a;孜孜#xff1a;勤勉#xff0c;不懈怠。指工作或学习勤奋不知疲倦。#x1f493;#x1f493;#x1f493; 目录 说在前面
题目一#xff1a;括号匹配问题
题目二#xff1a;用队列实现栈
题目三#xff1a;用栈实现队列
题目四#xff1a;设… 孜孜不倦孜孜勤勉不懈怠。指工作或学习勤奋不知疲倦。 目录 说在前面
题目一括号匹配问题
题目二用队列实现栈
题目三用栈实现队列
题目四设计循环队列
SUMUP结尾 说在前面 dear朋友们大家好我们又见面了有到了我们数据结构的刷题时间了。我们上次刚学完了栈和队列现在正好练练手~ 友友们点击这里进入力扣leetcode学习 以下是leetcode题库界面 点击这里进入牛客网NowCoder刷题学习 以下是NowCoder题库界面
题目一括号匹配问题
题目链接20. 有效的括号 - 力扣LeetCode
题目描述
题目分析 思路由于C语言没有单独提供栈的实现我们首先需要把我们之前写的栈的实现的接口都复制到题当中接口如下
typedef char STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;//栈的初始化
void STInit(ST* pst)
{assert(pst);pst-a NULL;//top指的是栈顶数据的下一个位置pst-top pst-capacity 0;
}//扩容
static void STCheckCapacity(ST* pst)
{if (pst-top pst-capacity){int NewCapacity pst-capacity 0 ? 4 : 2 * pst-capacity;STDataType* temp (STDataType*)realloc(pst-a, NewCapacity * sizeof(STDataType));if (temp NULL){perror(realloc operation failed);exit(1);}pst-a temp;pst-capacity NewCapacity;}
}//入栈
void STPush(ST* pst, STDataType x)
{assert(pst);STCheckCapacity(pst);pst-a[pst-top] x;
}//出栈
void STPop(ST* pst)
{assert(pst pst-top);pst-top--;
}//获取栈顶元素
STDataType STTop(ST* pst)
{assert(pst pst-top);return pst-a[pst-top - 1];
}//检测栈是否为空
bool STEmpty(ST* pst)
{assert(pst);return pst-top 0;
}//获取栈中有效元素个数
int STSize(ST* pst)
{assert(pst);return pst-top;
}//栈的销毁
void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top pst-capacity 0;
}
在此基础上我们才能完成题解。
这题为什么会想到用栈来解决呢我们可以认为每次得到一个右括号都和从右边往左的第一个左括号进行匹配如果匹配成功就是对的如果有哪一次匹配失败了说明不正确返回false。那么我们观察左括号很明显就有个特点就是最后输入的左括号要先和右括号匹配这和我们栈的LIFOLast In First Out是一样的。
比如 像上面这个例子我们可以用栈存放左括号。如果是三种左括号的一种我们就把它压入栈中如果是三种右开括号的一种我们取出栈顶的左括号和它进行匹配。 当放入这三个左括号我们输入了一个右括号此时我们需要得到栈顶的括号STTop和当前右有括号对比看是否匹配。如果匹配成功我们还需要将这个数据删除然后继续这个操作也就是每次对比都会消耗一个左括号。 显然两个左括号都匹配成功此时再继续压栈。最后两个右括号刚好也和两个左括号匹配成功所以最后我们可以判断栈是否为空STEmpty来判断是否整体都是匹配成功的。
代码如下 bool isValid(char* s) {ST st;STInit(st);while(*s){//左括号入栈if(*s ( || *s [ || *s {){STPush(st, *s);}else//右括号去栈顶左括号尝试匹配{if(STEmpty(st))//栈为空{STDestroy(st);return false;}char top STTop(st);STPop(st);//匹配失败if(*s ) top ! (|| *s ] top ! [|| *s } top ! {)return false;}s;}bool ret STEmpty(st);STDestroy(st);return ret;}
最后有一个地方需要注意就是如果我们刚开始就进入右括号此时没有做括号匹配那么直接就跳出循环栈也是为空的就返回了true这显然是错误的。所以我们在输入右括号的时候也要判断一下栈是否为空若为空直接返回false。
题目二用队列实现栈
题目链接225. 用队列实现栈 - 力扣LeetCode
题目描述
题目分析 思路和题目一同样的我们需要将队列的实现的所有接口都复制到题目当中才能在接下来使用队列接口如下
typedef int QDataType;typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue
{struct QueueNode* phead;struct QueueNode* ptail;int size;
}Queue;//队列的初始化
void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc operation failed);exit(1);}newnode-next NULL;newnode-val x;if (pq-ptail NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}//队头出队列
void QueuePop(Queue* pq)
{assert(pq pq-size);if (pq-phead-next NULL){free(pq-phead);pq-phead pq-ptail NULL;}else{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}//获取队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}//获取队列头部元素
QDataType QueueFront(Queue* pq)
{assert(pq pq-phead);return pq-phead-val;
}//获取队列尾部元素
QDataType QueueBack(Queue* pq)
{assert(pq pq-ptail);return pq-ptail-val;
}//检测队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}
有了上述接口以后我们思考接下来如何用两个队列实现栈。
我们知道栈是后入先出的而队列是先入先出的。函数需要我们实现栈的基本操作push压栈、pop弹栈、top取栈顶元素、empty判空。对于压栈来说其实可以直接实现我们把一个队列的队头当做栈底队尾入队列QueuePush就相当于压栈。问题是如何弹栈呢队列只能是一端入另一端出没办法直接实现删除队尾的数据。这个时候我们可以借助另一个队列。我们可以将队列中的数据从队头开始都入到另一个队列的中只留下最后一个队尾的数据然后再删除这个数据就可以了。 这也是这道题中重要的思想 去栈顶元素可以直接用QueueBack实现而判空就是两个队列都为空即为空同时要注意压栈应该压入到不为空的队列中栈顶元素返回的也是不为空的队列中的尾元素请大家注意。
代码如下
//创建包含两个队列的匿名结构体
typedef struct {Queue q1;Queue q2;
} MyStack;//初始化这两个队列
MyStack* myStackCreate() {MyStack* pst (MyStack*)malloc(sizeof(MyStack));QueueInit(pst-q1);QueueInit(pst-q2);return pst;
}压栈即压入不为空的队列中如果都为空那就都行
void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(obj-q1)){QueuePush(obj-q1, x);}else{QueuePush(obj-q2, x);}
}//弹栈
int myStackPop(MyStack* obj) {//假设法假设q1是空的若不成立那就q2是空的Queue* empty obj-q1;Queue* noempty obj-q2;if(!QueueEmpty(empty)){empty obj-q2;noempty obj-q1;}//把不空的队列入到空队列中并留下最后一个while(QueueSize(noempty) - 1){QueuePush(empty, QueueFront(noempty));QueuePop(noempty);}int top QueueFront(noempty);QueuePop(noempty);return top;
}//取栈顶元素
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);
}题目三用栈实现队列
题目链接232. 用栈实现队列 - 力扣LeetCode
题目描述 题目分析 思路1和队列实现栈是基本类似的建议大家做了第二题再看这道题。不过这里有个地方不太一样就是Pop在队列实现栈中我们只需要将队列中的数据插入到另外一个队列中再删除剩下的那一个就行了但是栈实现队列将栈中的数据压栈到另外的一个栈删除栈底的那个数据后由于顺序反了我们还需要将另一个栈的数据再放回来才行。 也就是这里会有区别其他地方其实都和题目二是一样的。
代码如下
//创建包含两个栈的匿名结构体
typedef struct {ST st1;ST st2;
} MyQueue;//初始化结构体
MyQueue* myQueueCreate() {MyQueue* pq (MyQueue*)malloc(sizeof(MyQueue));STInit(pq-st1);STInit(pq-st2);return pq;
}//队尾入队列
void myQueuePush(MyQueue* obj, int x) {if(!STEmpty(obj-st1)){STPush(obj-st1, x);}else{STPush(obj-st2, x);}
}//队头出队列
int myQueuePop(MyQueue* obj) {ST* empty obj-st1;ST* noempty obj-st2;if(!STEmpty(empty)){empty obj-st2;noempty obj-st1;}while(STSize(noempty) 1){STPush(empty, STTop(noempty));STPop(noempty);}int top STTop(noempty);STPop(noempty);while(STSize(empty)){STPush(noempty, STTop(empty));STPop(empty);}return top;
}//获得队头数据
int myQueuePeek(MyQueue* obj) {ST* empty obj-st1;ST* noempty obj-st2;if(!STEmpty(empty)){empty obj-st2;noempty obj-st1;}while(STSize(noempty) 1){STPush(empty, STTop(noempty));STPop(noempty);}int top STTop(noempty);STPush(empty, STTop(noempty));STPop(noempty);while(STSize(empty)){STPush(noempty, STTop(empty));STPop(empty);}return top;
}//判空
bool myQueueEmpty(MyQueue* obj) {return STEmpty(obj-st1) STEmpty(obj-st2);
}//销毁队列
void myQueueFree(MyQueue* obj) {STDestroy(obj-st1);STDestroy(obj-st2);free(obj);
思路2除了思路1我们其实还有另外一种方法就是将一个栈的栈顶当做队头入数据另外一个栈的栈顶当做队尾出数据 那么入队列就相当于将数据压入到左边的栈pushst中出队列就相当于是删除右边的栈popst的栈顶数据如果右边的栈中没有数据了再把左边的栈的数据全部导入到右边这样往复就可以了。
代码如下
//创建包含两个栈的匿名结构体
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) {STPush(obj-pushst, x);//相当于压入pushst中
}//取得队头数据
int myQueuePeek(MyQueue* obj) {if(STEmpty(obj-popst))//如果popst中没有数据就把pushst中的数据导到popst中{while(!STEmpty(obj-pushst)){STPush(obj-popst, STTop(obj-pushst));STPop(obj-pushst);}}return STTop(obj-popst);
}//队头出队列
int myQueuePop(MyQueue* obj) {int front myQueuePeek(obj);//有数据直接获取没数据先将pushst导入STPop(obj-popst);return front;
}//判空
bool myQueueEmpty(MyQueue* obj) {return STEmpty(obj-pushst) STEmpty(obj-popst);
}//销毁队列
void myQueueFree(MyQueue* obj) {STDestroy(obj-pushst);STDestroy(obj-popst);free(obj);
}
题目四设计循环队列
题目链接622. 设计循环队列 - 力扣LeetCode
题目描述 题目分析 思路创建数组利用模运算使得操作控制在0~k元素范围内并保证tail不放数据。 我们一般的队列是用链表实现的但是对于循环队列数组的方法可能更好实现链表的方法并不比数组的方法简单多少。
//创建包含数组相关内容的匿名结构体
typedef struct {int* arr;int head;int tail;int k;
} MyCircularQueue;//初始化结构体中的各项数据
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* st (MyCircularQueue*)malloc(sizeof(MyCircularQueue));st-arr (int*)malloc((k 1) * sizeof(int));st-head 0;st-tail 0;st-k k;return st;
}//如果head和tail位置相同循环队列为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-head obj-tail;
}//如果head在tail的下一个位置循环队列为满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj-head (obj-tail 1) % (obj-k 1);
}//队尾入队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj-arr[obj-tail] value;obj-tail;obj-tail % (obj-k 1);return true;
}//队头出队列
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;obj-head;obj-head % (obj-k 1); return true;
}//取队头数据
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj-arr[obj-head];
}//取队尾数据
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj-tail 0 ? obj-arr[obj-k] : obj-arr[obj-tail - 1];//return obj-arr[(obj-tail obj-k) % (obj-k 1)];
}//销毁队列
void myCircularQueueFree(MyCircularQueue* obj) {free(obj-arr);free(obj);
}
这道题锻炼并加深了对模运算的理解对上面每个函数体中的模运算大家一定要理解清楚。那链表的方式为什么复杂呢原因就是因为在数组中我们取尾的前一个只要下标-1就可以了最多再加上模运算但是对于链表是不好找前一个尾节点的前一个节点的。当然有解决办法如改用双向链表或者记录tail的前一个节点prev也可以重新遍历链表。但是这些解决方法无一不大大增加了代码的复杂度且降低了可读性所以对于循环链表来说数组的解决方法是更好的。 SUMUP结尾 数据结构就像数学题需要刷题才能对它有感觉。之后还会更新数据结构相关的练习题、面试题希望大家一起学习共同进步~ 如果大家觉得有帮助麻烦大家点点赞如果有错误的地方也欢迎大家指出~
