前言
本文章主要介绍栈和队列的相互转换。
使用两个队列实现栈
我们知道，栈的特点是后进先出，而队列的特点是先进先出。
栈的特点：
队列的特点：
使用两个队列实现栈的思路是：
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*1024Byte int 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); }
注意，由于两个队列的维护是依靠指针，所以两个队列申请的空间先释放，再释放栈结构体空间
总结
本文章介绍了两个队列实现栈的方法。
使用队列实现栈和使用栈实现队列都是可以的
下篇文章介绍使用两个栈实现队列
