如何用队列实现栈结构，以处理长尾词查询？

本文共计1928个文字，预计阅读时间需要8分钟。

我们先复习一下栈和队列的特点。栈的特点是后进先出（LIFO），也就是最后进入的元素最先出来。比如你输入1234，输出的顺序就是4321。而队列的特点是先进先出（FIFO），即最早进入的元素最先出来。如果输入1234，输出的顺序就是1234。

下面我们来解决问题：请使用两个队列实现一个栈的功能。

我们先来复习一下栈和队列的特点，栈的特点是后进先出，也就是你输入1234输出的是4321，而队列的特点是你输入1234，输出的也是1234。

下面我们来看题目：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop和empty）。

实现MyStack类：

• void push(int x)将元素 x 压入栈顶。
• int pop()移除并返回栈顶元素。
• int top()返回栈顶元素。
• boolean empty()如果栈是空的，返回true；否则，返回false。

解题思路

我们可以往不为空的队列1中输入数据（如果两个都为空任选一个输入），直到输入完毕，当我们要输出数据的时候我们先找到有数据的队列1，将这个队列1里的数据往空队列2里面导入，直到队列1中的数据只有1个数据时输出这个数据。

首先我们往空队列中输入数据1234

现在要输出4，我们就将队列1里面4之前的数据导入队列2中

最后我们将队列1中的数据删除。

如果我们现在又要增加一个数据4那么只需要往不为空的队列中增加新数据即可。

解题

因为队列在c中没有所以我们先写出一个队列。若想要知道如何写以一个队列请参考我的上一篇博客。

typedef int QDataType; typedef struct QListNode { struct QListNode* _pNext; QDataType _data; }QNode;//我们是运用的链表实现的队列，队列的特点是先进先出 //这一个结构体代表的就是一个节点 // 队列的结构 typedef struct Queue { QNode* _front; QNode* _rear; int size;//用以储存有效数据的个数 }Queue;//这个结构体代表的就是入队和出队指向的指针 // 初始化队列 void QueueInit(Queue* q); // 队尾入队列 void QueuePush(Queue* q, QDataType data); // 队头出队列 void QueuePop(Queue* q); // 获取队列头部元素 QDataType QueueFront(Queue* q); // 获取队列队尾元素 QDataType QueueBack(Queue* q); // 获取队列中有效元素个数 int QueueSize(Queue* q); // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 bool QueueEmpty(Queue* q); // 销毁队列 void QueueDestroy(Queue* q); // 初始化队列 void QueueInit(Queue* q) { assert(q);//理由依旧是这是一个结构体指针只有外面存在结构体以后才会有结构体指针所以结构体指针绝对不可能为NULL //这里我们只用使用一级指针就可以改变front和rear因为这两个指针都存在于queue的结构体里面我们使用queue的指针就可以改变里面的值 q->_front = NULL; q->_rear = NULL;//刚开始时队列中没有元素 q->size = 0; } // 队尾入队列 void QueuePush(Queue* q, QDataType data) { assert(q); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->_data = data; newnode->_pNext = NULL;//创建一个储存了有效数据的新节点 //这里就是尾插但是依旧分两种情况 //情况一：队列为空 if (q->_front == NULL) { assert(q->_rear == NULL); q->_front = q->_rear = newnode; } else//情况二：队列不为空 { q->_rear->_pNext = newnode; q->_rear = newnode; } q->size++; } // 队头出队列 void QueuePop(Queue* q) { //和头删差不多 assert(q); assert(!QueueEmpty(q));//注意当队列为空时直接断言 if (q->_front->_pNext == NULL) { free(q->_front); q->_front = q->_rear = NULL; } else { QNode* tmp = q->_front; q->_front = q->_front->_pNext; free(tmp); } q->size--; } // 获取队列头部元素 QDataType QueueFront(Queue* q) { assert(q); assert(!QueueEmpty(q));//当队列为空的时候我们就不能获取元素 return q->_front->_data; } // 获取队列队尾元素 QDataType QueueBack(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q->_rear->_data; } // 获取队列中有效元素个数 int QueueSize(Queue* q) { assert(q); return q->size; } // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 bool QueueEmpty(Queue* q) { assert(q); return (q->_front == NULL) && (q->_rear == NULL); //return q->size == 0; } // 销毁队列 void QueueDestroy(Queue* q) { assert(q); QNode* cur = q->_front; while (cur) { QNode* tmp = cur->_pNext; free(cur); cur = tmp; } q->_front = q->_rear = NULL; q->size = 0; }//首先我们要完成一个队列

下面我们来解题：

typedef struct { Queue a; Queue b; } MyStack;//mystack需要两个队列 MyStack* myStackCreate() {//这里要求我们创建一个MyStack并且必须使用malloc来创建， //否则在离开这个作用域之后obj就会销毁 MyStack* obj = (MyStack*)malloc(sizeof(MyStack));// //下面要初始化两个队列 QueueInit(&obj->a); QueueInit(&obj->b); return obj; } void myStackPush(MyStack* obj, int x) { //找到不为空的队列即可放入数据，若两者皆为空任选一个放入数据 if(!QueueEmpty(&obj->a)) { //a不为空，则往a中输入 QueuePush(&obj->a,x); } else//若a为空往b中输入数据，若两个都为空往b中输入数据也是可以的 { QueuePush(&obj->b,x); } } int myStackPop(MyStack* obj) { //删除数据也很简单，不为空的队列往空的队列中导入数据直到最后一个要删除的数据 //这里可以使用两种方法来写一种是使用if语句判断如果a不为空，elseb不为空 //我这里使用另外一种方法 Queue* emptyQ = &obj->a;//我这里就假设a为空队列 Queue* noemptyQ = &obj->b;//假设b为不空队列 if(!QueueEmpty(emptyQ))//如果a为不空队列，就修改一下 { emptyQ = &obj->b; noemptyQ = &obj->a; } while(QueueSize(noemptyQ)>1)//当不为空队列中的数据只有1个时停之导数据 { QueuePush(emptyQ,QueueFront(noemptyQ));//将不为空队列中的数据导入到空队列中 QueuePop(noemptyQ); } int front = QueueFront(noemptyQ);//因为题目要求我们要将删除的数据返回 QueuePop(noemptyQ); return front; } int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->a)) { return QueueBack(&obj->a);//如果a不为空就返回a最后的元素 } else { return QueueBack(&obj->b);//反之返回b最后的元素 } } bool myStackEmpty(MyStack* obj) { //当两个队列都为空的时候代表mystack为空 return QueueEmpty(&obj->a)&&QueueEmpty(&obj->b); } void myStackFree(MyStack* obj) { //先销毁队列 QueueDestroy(&obj->a); QueueDestroy(&obj->b); free(obj); }

这里面最值得我记住的一点就是如果你不知道哪一个队列为空，那么你可以使用假设法，如果假设失败调整错误就可以了。

做题链接：leetcode.cn/problems/implement-stack-using-queues/submissions/433051070/