特价网站建设价格低,安徽六安什么时候解封,天河建设网站设计,设计师必备的网站有哪些目录
一.【Leetcode225】队列实现栈
1.链接
2.题目再现 3.解法
二.【Leetcode232】栈实现队列
1.链接
2.题目再现
3.解法 一.【Leetcode225】队列实现栈
1.链接
队列实现栈
2.题目再现 3.解法 这道题给了我们两个队列#xff0c;要求去实现栈#xff1b; 首先… 目录
一.【Leetcode225】队列实现栈
1.链接
2.题目再现 3.解法
二.【Leetcode232】栈实现队列
1.链接
2.题目再现
3.解法 一.【Leetcode225】队列实现栈
1.链接
队列实现栈
2.题目再现 3.解法 这道题给了我们两个队列要求去实现栈 首先我们要知道栈和队列的特征 栈后进先出只能从栈顶入数据和出数据 队列先进先出从队尾入数据队头出数据 根据这些特点我们可以采用两边倒的方法来实现 具体来说 1.入栈时就是在不为空的队列插入数据若两个队列都为空就随便插入到一个队列中 2.出栈时将不为空的队列的数据倒入为空的队列中当不为空的队列就剩一个数据时就停止向空队列倒数据然后再删点那最后一个数据 3.判空时需要两个队列都为空才算栈为空 4.取栈顶元素即取不为空的队列的队尾元素在取栈顶元素前要判断栈是否为空 5.销毁栈时要先销毁其中的两个队列然后再销毁栈。 因为是用C语言实现的所以得自己手搓个队列。 typedef int Qdatatype;typedef struct QueueNode
{struct QueeuNode* next;Qdatatype data;
}QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tail;
}Queue;
void Queueinit(Queue* pq)
{assert(pq);pq-head NULL;pq-tail NULL;
}void Queuedestroy(Queue* pq)
{assert(pq);QueueNode* cur pq-head;while (cur ! pq-tail){QueueNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;
}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-head NULL){pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}
}void Queuepop(Queue* pq)
{assert(pq);assert(pq-head);QueueNode* next pq-head-next;if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{free(pq-head);pq-head next;}
}Qdatatype Queuefront(Queue* pq)
{assert(pq);assert(pq-head);return pq-head-data;
}Qdatatype Queueback(Queue* pq)
{assert(pq);assert(Queuesize(pq) 0);return pq-tail-data;
}int Queuesize(Queue* pq)
{assert(pq);int size 0;QueueNode* cur pq-head;while (cur ! pq-tail-next){size;cur cur-next;}return size;
}bool Queueempty(Queue* pq)
{assert(pq);return pq-head NULL;
}typedef struct
{Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack*obj(MyStack*)malloc(sizeof(MyStack));if(objNULL)exit(-1);Queueinit(obj-q1);Queueinit(obj-q2);return obj;
}void myStackPush(MyStack* obj, int x)
{if(!Queueempty(obj-q1)){Queuepush(obj-q1,x);}else{Queuepush(obj-q2,x);}
}int myStackPop(MyStack* obj) {Queue*emptyobj-q1;Queue*noemptyobj-q2;if(!Queueempty(obj-q1)){emptyobj-q2;noemptyobj-q1;}while(Queuesize(noempty)1){Queuepush(empty,Queuefront(noempty));Queuepop(noempty);}int frontQueuefront(noempty);Queuepop(noempty);return front;
}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);
}二.【Leetcode232】栈实现队列
1.链接
栈实现队列
2.题目再现 3.解法 这个的解法和上面的类似只不过这个不用总是来回倒 根据栈和队列的特征我们会发现将一个栈中的数据倒入另一个栈时数据的顺序刚好符合队列的要求不需要再重复地倒数据所以我们可以让一个栈专门用来入数据Pushst一个栈专门用来出数据Popst当我们要出数据而这个栈为空时我们才将用来入数据的栈中的数据倒入用来出数据的栈 。 如图 1.判空时需要两个栈都为空队列才为空 2.返回队头数据时和出数据的操作类似只是不需要删除队头的数据还有在之前要判断队列是否为空 3.销毁队列前要先销毁两个栈。 同样因为是C语言得先手搓个栈。 #define MR_CAP 5
typedef int STdatatype;typedef struct Stack
{STdatatype* arr;int top;int capacity;
}ST;void Stackinit(ST* ps)
{assert(ps);ps-arr (STdatatype*)malloc(MR_CAP * sizeof(STdatatype));if (ps-arr NULL){perror(Stackinit malloc);exit(-1);}ps-top 0;ps-capacity MR_CAP;
}void Stackdestroy(ST* ps)
{assert(ps);free(ps-arr);ps-arr NULL;ps-top 0;ps-capacity 0;
}void Stackpush(ST* ps, STdatatype x)
{assert(ps);if (ps-top ps-capacity){STdatatype* tmp (STdatatype*)realloc(ps-arr, ps-capacity * 2 * sizeof(STdatatype));if (tmp NULL){perror(Stackpush realloc);exit(-1);}else{ps-arr tmp;ps-capacity * 2;}}ps-arr[ps-top] x;ps-top;
}void Stackpop(ST* ps)
{assert(ps);assert(ps-top 0);ps-top--;
}STdatatype Stacktop(ST* ps)
{assert(ps);return ps-arr[ps-top - 1];
}int Stacksize(ST* ps)
{assert(ps);return ps-top;}bool Stackempty(ST* ps)
{assert(ps);if (ps-top 0){return true;}elsereturn false;}typedef struct {ST Pushst;ST Popst;
} MyQueue;MyQueue* myQueueCreate() {MyQueue*obj(MyQueue*)malloc(sizeof(MyQueue));if(objNULL)exit(-1);Stackinit(obj-Pushst);Stackinit(obj-Popst);return obj;
}void myQueuePush(MyQueue* obj, int x) {Stackpush(obj-Pushst,x);
}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);}int myQueuePop(MyQueue* obj) {int frontmyQueuePeek(obj);Stackpop(obj-Popst);return front;
}bool myQueueEmpty(MyQueue* obj) {return Stackempty(obj-Pushst)Stackempty(obj-Popst);
}void myQueueFree(MyQueue* obj) {Stackdestroy(obj-Pushst);Stackdestroy(obj-Popst);free(obj);
}这两道题的讲解就到这里了若有错误或是建议欢迎小伙伴们指出。 希望小伙伴们可以多多支持博主哦。 谢谢你的阅读。
