【C】队列与栈的相互转换

栈与队列是两种特点相反的数据结构，一个特点是后进先出，一个特点是先进先出，但是他们之间是可以相互转换的。

1 用队列实现栈

1）题目解析

2）算法解析

（1）结构(MyStack)

（2）初始化(myStackCreate)

（3）入栈(myStackPush)

（4）出栈(myStackPop)

（5）取栈顶元素(myStackTop)

（6）判空(myStackEmpty)

（7）销毁栈(myStackFree)

3）代码

2 用栈来实现队列

1）题目解析

2）算法解析

3）代码

1 用队列实现栈

leetcode链接https://leetcode.cn/problems/implement-stack-using-queues/

1）题目解析

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

我们再来看一下题目中所给的函数：

typedef struct {} MyStack;MyStack* myStackCreate() {}void myStackPush(MyStack* obj, int x) {}int myStackPop(MyStack* obj) {}int myStackTop(MyStack* obj) {}bool myStackEmpty(MyStack* obj) {}void myStackFree(MyStack* obj) {}

显然，这个题是想要让我们通过两个队列来实现一个栈，其中栈具有初始化(myStackCreate)、入栈(myStackPush)、出栈(myStackPop)、取栈顶元素(myStackTop)、判空(myStackEmpty)以及销毁栈(myStackFree)，只不过这里需要注意是Pop的返回值为int，也就是要返回栈顶元素。

2）算法解析

要完成用队列实现栈我们应该充分考虑他们俩之间的特点。接下来是我们来看这四个几个函数的实现：

（1）结构(MyStack)

题目中说了用两个队列来实现一个栈，所以MyStack里面只需要有两个队列就可以了，我们将这两个队列命名为 q1 和 q2。

（2）初始化(myStackCreate)

上面的函数要求我们返回一个 MyStack 的指针，所以首先我们需要用 malloc 函数开辟一块 MyStack 的空间，然后初始化该结构里面的两个队列就可以了，最后返回那个指针即可。

（3）入栈(myStackPush)

入栈的时候，我们选择往非空的队列里面入数据，这样会更好的配合出栈的逻辑。

（4）出栈(myStackPop)

入栈的时候是一直向非空的队列里面入数据，所以出栈的时候肯定会有一个空队列，一个非空队列，所以执行出栈操作的时候，我们可以让非空队列除队尾最后一个元素外的数据全都入到空队列里，然后先保存非空队列里的队尾最后一个数据，然后让最后一个数据出队列，返回这个值即可，其过程如图所示：

通过两个队列之间把数据来回调换，就可以实现数据的后入先出，而且这样也可以保证出栈之后，仍是一个空队列和一个非空队列，下一次入栈和出栈的时候也不会出问题。

（5）取栈顶元素(myStackTop)

既然入栈的时候有一个空队列和一个非空队列，要取到栈顶元素，也就是最后一个入栈的数据，这里只需要返回非空队列的队尾数据就可以了。

（6）判空(myStackEmpty)

判空很简单，只需判断两个队列 q1 和 q2 是否都为空就可以了，如果都为空，那就返回 true，如果都不为空，那就返回 false。

（7）销毁栈(myStackFree)

销毁栈就是销毁结构中的两个队列，只需要调用 QueueDestroy 销毁两个队列就可以了，只不过需要注意的是在初始化的时候开辟了一块 MyStack 的空间，所以最后不要忘记把这块空间也释放掉。

3）代码

typedef int QDataType;
//定义队列节点的结构
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;//对头 -- 删除数据QNode* ptail;//队尾 -- 插入数据
}Queue;//队列的初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;
}
//队列的销毁
void QueueDestroy(Queue* pq)
{assert(pq);QNode* pcur = pq->phead;while (pcur){QNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;
}
//入队
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail!\n");exit(1);}newnode->data = x;newnode->next = NULL;//如果队列为空if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{//队列不为空pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}
}
//判断是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}//出队
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;}
}
//取队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}
//取对头元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}
//返回元素个数
int QueueSize(Queue* pq)
{assert(pq);int size = 0;QNode* pcur = pq->phead;while (pcur){size++;pcur = pcur->next;}return size;
}数据结构队列///typedef struct {//创建两个队列Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() 
{MyStack* st = (MyStack*)malloc(sizeof(MyStack));QueueInit(&(st->q1));QueueInit(&(st->q2));return st;
}void myStackPush(MyStack* obj, int x) 
{//往非空队列里面插入数据if (!QueueEmpty(&(obj->q1))){QueuePush(&(obj->q1), x);}else{QueuePush(&(obj->q2), x);}
}bool myStackEmpty(MyStack* obj) 
{//只要判断两个队列为不为空就可以return QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2));
}int myStackPop(MyStack* obj) 
{//把非空队列的除最后一个元素之外的元素入队到另一个队列Queue* pn = &(obj->q1);Queue* ph = &(obj->q2);if (QueueEmpty(&(obj->q2))){pn = &(obj->q2);ph = &(obj->q1);}while (QueueSize(ph) > 1){//入空队列QueuePush(pn, QueueFront(ph));//出队QueuePop(ph);}//把最后一个元素出队int ret = QueueFront(ph);QueuePop(ph);return ret;
}int myStackTop(MyStack* obj) 
{//返回非空队列的队尾元素if (!QueueEmpty(&(obj->q1))){return QueueBack(&(obj->q1));}else{return QueueBack(&(obj->q2));}
}void myStackFree(MyStack* obj) 
{QueueDestroy(&(obj->q1));   QueueDestroy(&(obj->q2));free(obj);obj = NULL;   
}

2 用栈来实现队列

leetcode链接https://leetcode.cn/problems/implement-queue-using-stacks/submissions/601751470/

1）题目解析

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。

再来看一下题目中所给的函数：

typedef struct {} MyQueue;MyQueue* myQueueCreate() {}void myQueuePush(MyQueue* obj, int x) {}int myQueuePop(MyQueue* obj) {}int myQueuePeek(MyQueue* obj) {}bool myQueueEmpty(MyQueue* obj) {}void myQueueFree(MyQueue* obj) {}

显然，这个也是像用两个队列实现一个栈一样，是用两个栈来实现一个队列，这个队列包含以下函数：定义结构(MyQueue)、初始化(myQueueCreate)、入队(myQueuePush)、出队(myQueuePop)、取队头元素(myQueuePeek)、判空(myQueueEmpty) 以及销毁队列(myQueueFree)。

2）算法解析

（1）结构(MyQueue)

像用队列实现栈一样，这里也是定义 MyQueue 也是定义两个栈，这里命名为 pushst 与 popst，一个用来入数据，一个用来出数据。

（2）初始化(myQueueCreate)

这里初始化也是让我们返回一个 MyQueue 结构的指针，所以首先先开辟一块 MyQueue 结构大小的空间，然后让里面的两个栈初始化就可以了。

（3）入队(myQueuePush)

入队比较简单，直接往 pushst 里面插入数据即可。

（4）出队(myQueuePop)

出队的时候分两种情况：

a. 如果 popst 不为空，那就直接让 popst 的栈顶元素出栈，然后返回刚才出栈的栈顶元素。

b. 如果 popst 为空，那就先依次将 pushst 的栈顶元素入到 popst 里面，直到 pushst 为空，然后再让 popst 出栈，再返回出栈的栈顶元素。

如先入队1, 2, 3, 4 四个数据，然后出队1，再入队 5 ，再出队 2 的过程如图所示：

通过先向 pushst 里面入数据，再将 pushst 里的数据入栈到 popst 里面，这样经过两次先进后出的调整数据，数据就会变成先进先出，如上面那个图，刚开始 pushst 里面由栈顶到栈底的数据为 4,3,2,1，但是入到 popst 里面，栈顶到栈底的数据就变成了1,2,3,4，这样就实现了数据的先入先出。

（5）取队头元素(myQueuePeek)

取队头元素是类似于出栈的过程的，只不过不需要将 popst 的栈顶元素出栈，直接返回 popst 的栈顶数据即可，依然分两种情况：

a. 如果 popst 不为空，那就直接返回 popst 的栈顶元素。

b. 如果 popst 为空，那就先依次将 pushst 的栈顶元素入到 popst 里面，直到 pushst 为空，然后返回 popst 的栈顶元素。

（6）判空(myQueueEmpty)

判空和用队列实现栈一样，判断 MyQueue 里面的两个栈是否同时为空即可，如果都为空，那么返回 true；如果不为空，那么返回 false。

（7）销毁队列(myQueueFree)

销毁队列也只需销毁底层的两个栈 pushst 和 popst 即可，只不过需要注意要让开辟出的 MyQueue 的那一块空间也释放掉，才不会出现内存泄露的情况。

3）代码

typedef int STDataType;
//定义栈的结构--用数组来实现
typedef struct Stack
{STDataType* arr;int top;//指向栈顶int capacity;//容量
}Stack;//初始化
void StackInit(Stack* ps)
{assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;
}
//销毁
void StackDestroy(Stack* ps)
{assert(ps);if (ps->arr)free(ps->arr);ps->capacity = ps->top = 0;
}
//入栈
void StackPush(Stack* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){//增容int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc fail!\n");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}ps->arr[ps->top++] = x;
}
//判空
bool StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}
//出栈
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}//取栈顶元素
STDataType StackTop(Stack* ps)
{assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}
//有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}数据结构栈/typedef struct {//定义两个栈，一个用来当做入队的队列，另一个当做出队的队列Stack pushst;Stack popst;
} MyQueue;MyQueue* myQueueCreate() 
{MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));if (q == NULL){perror("malloc fail！\n");exit(1);}//初始化队列中的两个栈StackInit(&q->pushst);StackInit(&q->popst);return q;
}void myQueuePush(MyQueue* obj, int x) 
{//将数据往入队的栈里面入栈StackPush(&obj->pushst, x);
}int myQueuePop(MyQueue* obj) 
{//如果出队的栈为空，那就把入队的栈的数据全部入栈到出队的栈    if (StackEmpty(&obj->popst)){while (StackSize(&obj->pushst) > 0){//取栈顶元素STDataType tmp = StackTop(&obj->pushst);//出栈StackPop(&obj->pushst);//入栈StackPush(&obj->popst, tmp);}}STDataType ret = StackTop(&obj->popst);StackPop(&obj->popst);return ret;
}int myQueuePeek(MyQueue* obj) 
{//如果出队的栈为空，那就把入队的栈的数据全部入栈到出队的栈    if (StackEmpty(&obj->popst)){while (StackSize(&obj->pushst) > 0){//取栈顶元素STDataType tmp = StackTop(&obj->pushst);//出栈StackPop(&obj->pushst);//入栈StackPush(&obj->popst, tmp);}}//不需要出队就可以STDataType ret = StackTop(&obj->popst);return ret;
}bool myQueueEmpty(MyQueue* obj) 
{//如果连个栈都为空，那么队列就为空return StackEmpty(&obj->popst) && StackEmpty(&obj->pushst);
}void myQueueFree(MyQueue* obj) 
{//销毁两个栈就可以if (!StackEmpty(&obj->popst)){StackDestroy(&obj->popst);}if (!StackEmpty(&obj->pushst)){StackDestroy(&obj->pushst);}//最后别忘了释放objfree(obj);obj = NULL;
}

通过栈与队列的相互转换，相信大家对于栈和队列的理解会更加深入。