建设厅网站查询电工证件,网站建设的关键,成都微信开发小程序,微信公众平台申请入口思路 思路#xff1a;用两个队列实现栈后进先出的特性 #xff0c;两个队列为空时#xff0c;先将数据都导向其中一个队列。 当要模拟出栈时#xff0c;将前面的元素都导入另一个空队列#xff0c;再将最后一个元素移出队列 实现 实现#xff1a; 因为C语言没有库可以…
思路 思路用两个队列实现栈后进先出的特性 两个队列为空时先将数据都导向其中一个队列。 当要模拟出栈时将前面的元素都导入另一个空队列再将最后一个元素移出队列 实现 实现 因为C语言没有库可以现成使用所以我们将写好的队列导入 先创建MyStack结构体包含两个队列结构体。再malloc动态申请MyStack结构体的空间最后将两个队列传入初始化函数进行初始化记得要加上取地址符号 压栈过程我们就先判断队列q1是否为空如果不为空则往q1中导入数据因为不为空证明前面已经有数据放进去了如果为空则证明要么两个队列都是空要么一开始向q2导入了数据这时我们就将数据导入队列q2中。 一句话总结谁有数据就放谁都无数据放q2一开始随便放哪个都行这里我们选择q2 出栈过程就分为两个部分。第一个部分是创建空队列和非空队列指针因为我们不知道此时q1和q2哪个是空哪个非空后面加上判断如果初始赋值错误则翻转过来。 第二个部分就是一开始的核心思路利用循环将前面的元素都导入另一个空队列再获取最后一个元素注意每次导入一个元素就要进行出队操作pop 获取栈顶元素就是出栈过程的删减版判断完空与非空队列直接取出非空队列队尾的元素即可 判断栈是否为空只要当两个队列q1和q2全为空时栈才为空返回true否则返回false 最后释放栈空间可能有人只写了最后一句也给过了但是其实这是不对的。正确做法是先将两个队列都销毁销毁链表再将MyStack空间给释放掉这样才不会造成内存泄漏 完整代码附上
typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//获取队头元素
QDataType QueueFront(Queue* pq);
//获取队尾元素
QDataType QueueBack(Queue* pq);
//检测队列中有效元素个数
int QueueSize(Queue* pq);
//检测队列是否为空
bool QueueEmpty(Queue* pq);void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;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;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-data x;newnode-next NULL;if (pq-ptail NULL){assert(pq-phead NULL);pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));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--;
}QDataType QueueFront(Queue* pq)
{assert(pq);return pq-phead-data;
}QDataType QueueBack(Queue* pq)
{assert(pq);return pq-ptail-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* obj (MyStack*)malloc(sizeof(MyStack));if (obj NULL){perror(malloc fail);return NULL;}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* pEmptyQ obj-q1;Queue* pNonEmptyQ obj-q2;if (!QueueEmpty(obj-q1)){pEmptyQ obj-q2;pNonEmptyQ obj-q1;}while (QueueSize(pNonEmptyQ) 1){QueuePush(pEmptyQ, QueueFront(pNonEmptyQ));QueuePop(pNonEmptyQ);}int top QueueFront(pNonEmptyQ);QueuePop(pNonEmptyQ);return top;
}int myStackTop(MyStack* obj) {Queue* pEmptyQ obj-q1;Queue* pNonEmptyQ obj-q2;if (!QueueEmpty(obj-q1)){pEmptyQ obj-q2;pNonEmptyQ obj-q1;}int top QueueBack(pNonEmptyQ);return top;
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj-q1) QueueEmpty(obj-q2);
}void myStackFree(MyStack* obj) {QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);
}/*** 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);
*/
