【使用两个队列实现栈】

---

---

前言

本文章主要介绍栈和队列的相互转换。

---

使用两个队列实现栈

我们知道，栈的特点是后进先出，而队列的特点是先进先出。

栈的特点：

队列的特点：

使用两个队列实现栈的思路是：

1.向两个队列中的任一队列放入元素
2.取出元素时，队列的功能是先进先出，要达到后进先出，需要将前面的所有元素取出，存入另一个空队列中，然后将剩下的最后一个元素释放掉即可。

比如：

后面如果想继续插入元素的话，应该将插入的元素放在非空队列中，这样就实现了栈的功能。

这样实现的原因是，两个队列中必有其中一个队列是空队列，保证了栈的后进先出的特点。

下面给出一道题目
两个队列实现栈

这里我用c语言来实现，所以先先写好队列的基本功能，再将接口函数引入。

1.队列接口函数引入

typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}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);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* del = cur;cur = cur->next;free(del);//del = NULL;}pq->head = pq->tail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;if (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(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* del = pq->head;pq->head = pq->head->next;free(del);}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;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL && pq->tail == NULL;
}// 1G = 1024MB
// 1024MB = 1024*1024KB
// 1024*1024KB = 1024*1024*1024Byteint QueueSize(Queue* pq)
{assert(pq);/*int size = 0;QNode* cur = pq->head;while (cur){cur = cur->next;++size;}return size;*/return pq->size;
}

2.栈的初始化

MyStack* myStackCreate() {MyStack*st = (MyStack*)malloc(sizeof(MyStack));QueueInit(&st->q1);QueueInit(&st->q2);return st;
}

栈的初始化就是将两个队列进行初始化。

3.向栈中插入元素

保证其中一个队列不为空
//首先需要判断哪个队列为空，可以用ifelse来判断，但是这样操作冗余的，所以可以使用假设
int myStackPop(MyStack*
void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}

由于无法得知哪一个队列为空，则需要判断或者假设，使用判断的化，代码比较冗余，在这里我使用假设，假设第一个队列是空。

4.出栈操作

int myStackPop(MyStack* obj) {Queue*EmptyQ = &obj->q1;Queue*NonEmptyQ = &obj->q2;if(!QueueEmpty(&obj->q1)){//如果q1不为空，返回假，！就返回真，进入if//意思就是我们假设错误了。EmptyQ = &obj->q2;NonEmptyQ = &obj->q1;}//来到这里已经知道哪个是空了,把所有元素导入非空队列，将最后一个不导while(QueueSize(NonEmptyQ)>1){QueuePush(EmptyQ,QueueFront(NonEmptyQ));QueuePop(NonEmptyQ);}int top = QueueFront(NonEmptyQ);QueuePop(NonEmptyQ);return top;}

5.取出栈顶元素

int myStackTop(MyStack* obj) {//取出栈顶元素//在首先的队列中，我们虽然不能删除队尾元素，但是我们可以取出队尾的元素if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}

6.判断栈是否为空

bool myStackEmpty(MyStack* obj) 
{   //判断栈是否为空，需要判断两个队列是否为空return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

判断栈是否为空，需要判断两个队列是否为空

7.释放内存空间

void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}

注意，由于两个队列的维护是依靠指针，所以两个队列申请的空间先释放，再释放栈结构体空间

---

总结

本文章介绍了两个队列实现栈的方法。
使用队列实现栈和使用栈实现队列都是可以的
下篇文章介绍使用两个栈实现队列