专做宠物的网站,wordpress什么样,怎么自己做网站挣钱,营销网站设计上海天气题目#xff1a;用队列实现栈 思路
队列的特点是先进先出#xff0c;而栈的特点是后进先出。所以想要用队列实现模拟栈#xff0c;我们可以使用两个队列#xff0c;一个队列负责压栈#xff0c;一个队列负责出栈。压栈很简单就是检空再调用队列的push就好#xff0c;那出… 题目用队列实现栈 思路
队列的特点是先进先出而栈的特点是后进先出。所以想要用队列实现模拟栈我们可以使用两个队列一个队列负责压栈一个队列负责出栈。压栈很简单就是检空再调用队列的push就好那出栈呢这里可以利用另外一个空队列先把一部分数据给空队列原来的队列只保留最后一个数据就好这时再对这个队列出栈再Pop掉。始终保持一个队列有数据一个队列为空。两个队列相互交换数据达到模拟实现栈的效果。
这里的结构实际就是一个套娃栈包含队列队列里包含链表 具体实现
首先手搓一个队列如果是其他语言也可以直接调用库这里是用c语言。接着实现题目给的函数。
myStackCreate
MyStack* myStackCreate() {MyStack* pst(MyStack*)malloc(sizeof(MyStack));if(pstNULL){perror(Malloc Failed\n);return NULL;}QueueInit(pst-q1);QueueInit(pst-q2);return pst;
}
这里创建栈要想清楚结构有三层其中两层你已经再队列里完成。所以这里我们还需要再创建一个栈动态开辟一个指针用这个指针来维护栈和实现各种功能
myStackPush
void myStackPush(MyStack* obj, int x) {if(!(QueueEmpty(obj-q1))){QueuePush(obj-q1,x);}else{QueuePush(obj-q2,x);}
}
这里压栈还是比较简单首先检查一下队列是否为空如果为空就入队另一个队列。当然刚开始入队两个都为空。所以在检查完一个队列为空后直接就入队到另一个队列就行了。不用再多余判断了。
myStackPop
int myStackPop(MyStack* obj) {Queue* emptyobj-q1;Queue* nonemptyobj-q2;if(!QueueEmpty(obj-q1)){emptyobj-q2;nonemptyobj-q1;}while(QueueSize(nonempty) 1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int retQueueFront(nonempty);QueuePop(nonempty);return ret;
}
这里出栈是有点复杂设计到两个队列相互转化。所以为了逻辑清晰。我们直接创建两个新队列分别命名为empty和nonempty。这样容易区分不容易逻辑混乱。
这里我们可以直接选择一个队列赋值给empty另一个队列赋值给nonempty。在进行检空如果不对在进行交换就行。接下来就是依次出队把头部元素依次入队到empty,依次Pop nonempty队列。当只剩一个数据循环停止。退出循环后把剩余的数据出队Pop队列返回。这样就实现了后进先出的效果。
myStackTop
int myStackTop(MyStack* obj) {if(!QueueEmpty(obj-q1)){return QueueBack(obj-q1);}else{return QueueBack(obj-q2);}
}这里可以检空再调用QueueBack这里也把这个函数体现的淋漓尽致。虽然从队列定义看这个函数是不合理的。但是这个函数再很多地方都会用到。所以我们不妨写一下。cSTL中就也有这个函数。
myStackEmpty
bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj-q1)QueueEmpty(obj-q2);
}
这里返回的是两个队列的检空因为这个栈是由这两两个队列实现的
myStackFree
void myStackFree(MyStack* obj) {QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);objNULL;
}
这里释放可不能直接free栈。我们这里队列还需要一个一个释放。如果你直接释放掉栈那就会内存泄漏。所以我们先调用下队列的销毁函数把两个队列释放掉,再free栈最后记得置空
代码
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;
void QueueInit(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
//队尾入队列
void QueuePush(Queue* pq, QDataType x);
//队头出队列
void QueuePop(Queue* pq);
//获取队列头部yuansu
QDataType QueueFront(Queue* pq);
//获取队列尾部元素
QDataType QueueBack(Queue* pq);
//获取队列中有效数据个数
int QueueSize(Queue* pq);
//检测队列是否为空检空
bool QueueEmpty(Queue* pq);
void QueueInit(Queue* pq)
{pq-head pq-tail NULL;pq-size 0;
}
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;pq-size 0;
}
void QueuePush(Queue* pq, QDataType x)
{QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(Malloc Failed\n);return;}newnode-next NULL;newnode-data x;if (pq-head NULL){assert(pq-tail NULL);pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size;
}
void QueuePop(Queue* pq)
{assert(pq);assert(pq-head ! NULL);/*QNode* next pq-head-next;free(pq-head);pq-head next;if (pq-head NULL){pq-tail NULL;}*/if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* next pq-head-next;free(pq-head);pq-head next;}pq-size--;
}
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-data;
}
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst(MyStack*)malloc(sizeof(MyStack));if(pstNULL){perror(Malloc Failed\n);return NULL;}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) {Queue* emptyobj-q1;Queue* nonemptyobj-q2;if(!QueueEmpty(obj-q1)){emptyobj-q2;nonemptyobj-q1;}while(QueueSize(nonempty) 1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int retQueueFront(nonempty);QueuePop(nonempty);return ret;
}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);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);
*/总结
这里复杂的主要是结构在具体的函数实现上如果你思路清晰其实是比较简单的。比较复杂的就是出栈这个函数需要多想一下
题目链接225. 用队列实现栈 - 力扣LeetCode
