昆山建设信息网站,wordpress和dede区别,创建全国文明城市总结,施工企业oa办公系统文章目录 用队列实现栈用栈实现队列设计循环队列 用队列实现栈
链接#xff1a;用队列实现栈 这道题是让我们用两个队列实现一个栈#xff0c;简单来说#xff0c;就是利用队列来实现一个先入后出的功能#xff0c;我们知道队列是先入先出#xff0c;如何用两个队列来实… 文章目录 用队列实现栈用栈实现队列设计循环队列 用队列实现栈
链接用队列实现栈 这道题是让我们用两个队列实现一个栈简单来说就是利用队列来实现一个先入后出的功能我们知道队列是先入先出如何用两个队列来实现后入先出呢比如说 我们现在有五个数据进入了第一个队列 之后我们如果要按照栈的形式取出数据的话要取出5只靠队列一肯定是不行了要把前四个数据挪到队列二再把五取出来就可以了 这时取出4还是一样的操作挪动在取出。如果要插入呢肯定要插在4的后面不知道你有没有发现两个队列总是一个为空另一个可能空刚开始什么数据都没有也可能不空。 总结插入的话就插入非空的队列取出的话就是先挪动在取出。 typedef struct {
Que queue1;
Que queue2;
} MyStack;MyStack* myStackCreate() {
MyStack*obj(MyStack*)malloc(sizeof(MyStack));
QueueInit(obj-queue1);
QueueInit(obj-queue2);
return obj;
}void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(obj-queue1)){QueuePush(obj-queue1,x);
}
else{QueuePush(obj-queue2,x);
}
}int myStackTop(MyStack* obj) {
if(!QueueEmpty(obj-queue1)){
return QueueBack(obj-queue1);
}
else{return QueueBack(obj-queue2);
}
}int myStackPop(MyStack* obj) {
Que* Emptyobj-queue1;
Que* UnEmptyobj-queue2;
if(!QueueEmpty(obj-queue1)){Emptyobj-queue2;UnEmptyobj-queue1;
}
while(QueueSize(UnEmpty)1){QDataType tmp QueueFront(UnEmpty);QueuePop(UnEmpty);QueuePush(Empty,tmp);
}QDataType tmp QueueFront(UnEmpty);QueuePop(UnEmpty);return tmp;
}bool myStackEmpty(MyStack* obj) {
return QueueEmpty(obj-queue1)QueueEmpty(obj-queue2);
}void myStackFree(MyStack* obj) {
QueueDestroy(obj-queue1);
QueueDestroy(obj-queue2);
free(obj);
}这里只有实现的栈的函数代码当然我们需要把自己实现的队列的代码粘贴到题中也可以看我的另外一篇博客那里面有源码 链接栈和队列
用栈实现队列
链接用栈实现队列 这个跟上个题非常的类似要求都是一样的就是实现的思想不太一样栈是要求后进先出我们如何用两个栈实现先入先出呢比如说 我们先给一个栈中放上五个数据 我们现在要取出栈一当中的1无可厚非也是倒数据嘛对不对先把2345倒到栈二再把一取出就可以了。 如果现在我们要取出2呢好像这次不用倒了直接取就行。我要插入数据呢得插到栈一因为插到栈二数据就乱了栈二的数据取出完了就把栈一的数据倒到栈二依次类推就可以得到一个队列了。不知道你有没有发现栈一只需要插入数据栈二只需要取出数据。 总结一个栈负责插入数据一个栈负责出数据出数据的栈没了数据就从插入数据的栈中倒过来。 typedef struct {
ST push;
ST pop;
} MyQueue;MyQueue* myQueueCreate() {
MyQueue*tmp(MyQueue*)malloc(sizeof(MyQueue));
STInit(tmp-push);
STInit(tmp-pop);
return tmp;
}void myQueuePush(MyQueue* obj, int x) {
STPush(obj-push,x);
}int myQueuePeek(MyQueue* obj) {if(!STEmpty(obj-pop)){return STTop(obj-pop);}
while(!STEmpty(obj-push)){//倒数据STDataType tmpSTTop(obj-push);STPop(obj-push);STPush(obj-pop,tmp);
}return STTop(obj-pop);
}int myQueuePop(MyQueue* obj) {
myQueuePeek(obj);
STDataType tmpSTTop(obj-pop);STPop(obj-pop);
return tmp;
}bool myQueueEmpty(MyQueue* obj) {
return STEmpty(obj-pop)STEmpty(obj-push);
}void myQueueFree(MyQueue* obj) {
STDestroy(obj-pop);
STDestroy(obj-push);
free(obj);
}同理这个也是需要栈的代码的链接在上面
设计循环队列
链接设计循环队列 什么叫循环队列呢就是说一个队列的长度是一定的只要有空间我们要一直从尾插入头出即使这个尾在头的前面。这个循环队列用数组来实现是非常理想的我们还可以多开辟一个空间来区分空和满。 我们还是画图来解释一下 比如说我们开辟一个六个空间的数组一开始头和尾都在开头位置我们要插入的话要在tail的位置插入并且tail要走向后一个 比如说我们插入五个数据这时就满了因为我们如果要插入6个数据的话空和满不能区分head都是等于tail但现在tail的下一个为head就证明满了如果要出的话也简单 这是再插入就要在返回数组的前边插入了具体代码实现就是取余 这样就实现了循环功能 typedef struct {
int*a ;
int head;
int tail;
int size;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue*tmp(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
tmp-a(int*)malloc(sizeof(int)*(k1));
tmp-head0;
tmp-tail0;
tmp-sizek1;
return tmp;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if((obj-tail1)%obj-sizeobj-head){return false;
}
else{obj-a[obj-tail]value;obj-tail(obj-tail1)%(obj-size);return true;
}
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(obj-headobj-tail){return false;
}
else{obj-head(obj-head1)%(obj-size);return true;
}
}int myCircularQueueFront(MyCircularQueue* obj) {
if(obj-headobj-tail){return -1;
}
else{return obj-a[obj-head];
}
}int myCircularQueueRear(MyCircularQueue* obj) {
if(obj-headobj-tail){return -1;
}
else{return obj-a[(obj-tailobj-size-1)%obj-size];
}
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj-headobj-tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj-tail1)%obj-sizeobj-head;
}void myCircularQueueFree(MyCircularQueue* obj) {
free(obj-a);
free(obj);
}中间有很多的取余操作目的就是找到逻辑上的下一个位置但在物理上它确实是在前面。
