数据结构与算法⑨(第三章_下)队列的概念和实现(力扣：225+232+622)（上）-阿里云开发者社区

一、队列（Queue）

队列的概念：

① 队列只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。

② 入队列，进行插入操作的一端称为队尾。出队列，进行删除操作的一端称为队头。

③ 队列中的元素遵循先进先出的原则，即 FIFO 原则（First In First Out）

队列的结构：

二、队列的定义

链式队列

typedef int QueueDataType;   //队列类型
 
typedef struct QueueNode 
{
    struct QueueNode* next;  //指向下一个节点
    QueueDataType data;      //数据
} QueueNode;
 
typedef struct Queue 
{
    QueueNode* pHead;        //头指针
    QueueNode* pTail;        //尾指针
} Queue;

和栈不一样的是，栈使用数组和链表差别不大，只是数组更优。

队列使用数组就很麻烦了，只能使用链表。

为什么定义两个指针？

单链表我们只定义了一个指针指向头，没有定义尾指针。因为定义尾指针解决不了问题，比如尾删和任意位置的插入删除。（因为即使定义了也找不到尾指针的前一个）所以我们没有必要定义一个结构体把他们封到一起。这里我们再定义一个头指针 head 一个尾指针 tail ，这两个指针才有意义。因为根据队列的性质，我们只会在队尾插入，在队头删除。所以这个尾指针的价值就得到了完美的体现，实际中定义几个指针是看你的需求确定的。

另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。

如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。

环形队列可以使用数组实现，也可以使用循环链表实现。

下面的讲解的力扣OJ力扣622题就是设计一种循环队列

三、队列的实现（完整代码）

Queue.h

#pragma once
 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
 
typedef int QueueDataType;   //队列类型
 
typedef struct QueueNode 
{
    struct QueueNode* next;  //指向下一个节点
    QueueDataType data;      //数据
} QueueNode;
 
typedef struct Queue//如果不设置成结构体就需要传二级指针，还要传两个参数
{
    QueueNode* pHead;
    QueueNode* pTail;
} Queue;
 
void QueueInit(Queue* pQ);//初始化队列
void QueueDestroy(Queue* pQ);//销毁队列
bool QueueEmpty(Queue* pQ);//判断队列是否为空
void QueuePush(Queue* pQ, QueueDataType x);//入队
void QueuePop(Queue* pQ);//出队
QueueDataType QueueFront(Queue* pQ);//返回队头数据
QueueDataType QueueBack(Queue* pQ);//返回队尾数据
int QueueSize(Queue* pQ);//返回队列大小

Queue.c

#include "Queue.h"
 
void QueueInit(Queue* pQ) 
{
    assert(pQ);
 
    pQ->pHead = pQ->pTail = NULL;
}
 
void QueueDestroy(Queue* pQ) 
{
    assert(pQ); 
 
    QueueNode* cur = pQ->pHead;
    while (cur != NULL) 
    {
        QueueNode* curNext = cur->next;  //防止释放cur后找不到其下一个节点
        free(cur);                     
        cur = curNext;                   
    }
    pQ->pHead = pQ->pTail = NULL; 
}
 
bool QueueEmpty(Queue* pQ) 
{
    assert(pQ); 
 
    return pQ->pHead == NULL;//如果成立则为True，不成立则为False
}
 
//入队：队尾插入数据，队头出(删)数据。如果是第一个入队的(队列为空)则既要当头又当尾
void QueuePush(Queue* pQ, QueueDataType x) 
{
    assert(pQ);
 
    QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
    if (new_node == NULL)
    {
        printf("malloc failed!\n");
        exit(-1);
    }
    new_node->data = x;     //待插入的数据
    new_node->next = NULL;  //新的数据指向空
 
    if (pQ->pHead == NULL)//情况1: 队列为空
    {           
        pQ->pHead = pQ->pTail = new_node;
    }
    else //情况2: 队列不为空   队尾入数据
    {                              
        pQ->pTail->next = new_node;  //在现有尾的后一个节点放置new_node
        pQ->pTail = new_node;        //更新pTail，使它指向新的尾
    }
}
 
void QueuePop(Queue* pQ) // 出队：队尾入数据，队头出(删)数据
{
    assert(pQ);                          
    assert(!QueueEmpty(pQ));  
 
    QueueNode* headNext = pQ->pHead->next; //队头出数据，防止释放pHead后找不到其下一个节点
    free(pQ->pHead);
    pQ->pHead = headNext;                  //更新头 
 
    if (pQ->pHead == NULL)//删完之后（队列空了）pHead == NULL 了 pTail 还是野指针
    {
        pQ->pTail = NULL;//处理一下尾指针，将尾指针置空
    }
}
 
QueueDataType QueueFront(Queue* pQ) //返回队头数据
{
    assert(pQ);                           
    assert(!QueueEmpty(pQ));    
 
    return pQ->pHead->data;
}
 
QueueDataType QueueBack(Queue* pQ) //返回队尾数据
{
    assert(pQ);
    assert(!QueueEmpty(pQ));
 
    return pQ->pTail->data;
}
 
int QueueSize(Queue* pQ) //返回队列大小
{
    assert(pQ);
 
    int count = 0;
    QueueNode* cur = pQ->pHead;
    while (cur != NULL) 
    {
        count++;
        cur = cur->next;
    }
    return count;
}

Test.c

#include "Queue.h"
 
void TestQueue1() 
{
    Queue q;
    QueueInit(&q);
 
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);
 
    QueuePop(&q);
    QueuePop(&q);
    QueuePop(&q);
    QueuePop(&q);
    //QueuePop(&q);
 
    QueueDestroy(&q);
}
 
void TestQueue2() 
{
    Queue q;
    QueueInit(&q);
 
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    //QueueDataType front = QueueFront(&q);
    //printf("%d ", front);
    //QueuePop(&q);  //pop掉去下一个
 
    QueuePush(&q, 3);
    QueuePush(&q, 4);
 
    //假设先入了1 2，让1出来，再继续入，它的顺序还是不会变。永远保持先进先出
    while (!QueueEmpty(&q)) 
    {
        QueueDataType front = QueueFront(&q);
        printf("%d ", front);
        QueuePop(&q);  //pop掉去下一个
    }
    printf("\n");
 
    QueueDestroy(&q);
}
 
int main(void) 
{
    //TestQueue1();
    TestQueue2();
    return 0;
}

四、力扣OJ题

力扣链接：225. 用队列实现栈

难度简单

请你仅使用两个队列实现一个后入先出（LIFO）的栈，

并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。

int pop() 移除并返回栈顶元素。

int top() 返回栈顶元素。

boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和

is empty 这些操作。

你所使用的语言也许不支持队列。你可以使用 list （链表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：

["MyStack", "push", "push", "top", "pop", "empty"]

[[], [1], [2], [], [], []]

输出：

[null, null, null, 2, 2, false]

解释：

MyStack myStack = new MyStack();

myStack.push(1);

myStack.push(2);

myStack.top(); // 返回 2

myStack.pop(); // 返回 2

myStack.empty(); // 返回 False

提示：

1 <= x <= 9

最多调用100 次 push、pop、top 和 empty

每次调用 pop 和 top 都保证栈不为空

（选C给的代码：）

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) {
 
}
 
/**
 * 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);
*/

解析代码：

核心思路：

（先入先出转为先入后出）

1.入数据，往不为空的队列入，保持另一个队列为空

2.出数据，依次出队头的数据，转移到另一个队列保存，只剩最后一个时Pop掉

和上一篇栈的OJ题一样，用C++写就很好写，但用C写就要自己创建栈/队列

把我们刚才写的Queue.h和Queue.c复制粘贴过去后删掉头文件就行了

typedef int QueueDataType;   //队列类型
 
typedef struct QueueNode 
{
    struct QueueNode* next;  //指向下一个节点
    QueueDataType data;      //数据
} QueueNode;
 
typedef struct Queue//如果不设置成结构体就需要传二级指针，还要传两个参数
{
    QueueNode* pHead;
    QueueNode* pTail;
} Queue;
 
void QueueInit(Queue* pQ);//初始化队列
void QueueDestroy(Queue* pQ);//销毁队列
bool QueueEmpty(Queue* pQ);//判断队列是否为空
void QueuePush(Queue* pQ, QueueDataType x);//入队
void QueuePop(Queue* pQ);//出队(删数据)
QueueDataType QueueFront(Queue* pQ);//返回队头数据
QueueDataType QueueBack(Queue* pQ);//返回队尾数据
int QueueSize(Queue* pQ);//返回队列大小
 
void QueueInit(Queue* pQ) 
{
    assert(pQ);
 
    pQ->pHead = pQ->pTail = NULL;
}
 
void QueueDestroy(Queue* pQ) 
{
    assert(pQ); 
 
    QueueNode* cur = pQ->pHead;
    while (cur != NULL) 
    {
        QueueNode* curNext = cur->next;  //防止释放cur后找不到其下一个节点
        free(cur);                     
        cur = curNext;                   
    }
    pQ->pHead = pQ->pTail = NULL; 
}
 
bool QueueEmpty(Queue* pQ) 
{
    assert(pQ); 
 
    return pQ->pHead == NULL;//如果成立则为True，不成立则为False
}
 
//入队：队尾插入数据，队头出(删)数据。如果是第一个入队的(队列为空)则既要当头又当尾
void QueuePush(Queue* pQ, QueueDataType x) 
{
    assert(pQ);
 
    QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
    if (new_node == NULL)
    {
        printf("malloc failed!\n");
        exit(-1);
    }
    new_node->data = x;     //待插入的数据
    new_node->next = NULL;  //新的数据指向空
 
    if (pQ->pHead == NULL)//情况1: 队列为空
    {           
        pQ->pHead = pQ->pTail = new_node;
    }
    else //情况2: 队列不为空   队尾入数据
    {                              
        pQ->pTail->next = new_node;  //在现有尾的后一个节点放置new_node
        pQ->pTail = new_node;        //更新pTail，使它指向新的尾
    }
}
 
void QueuePop(Queue* pQ) // 出队：队尾入数据，队头出(删)数据
{
    assert(pQ);                          
    assert(!QueueEmpty(pQ));  
 
    QueueNode* headNext = pQ->pHead->next; //队头出数据，防止释放pHead后找不到其下一个节点
    free(pQ->pHead);
    pQ->pHead = headNext;                  //更新头 
 
    if (pQ->pHead == NULL)//删完之后（队列空了）pHead == NULL 了 pTail 还是野指针
    {
        pQ->pTail = NULL;//处理一下尾指针，将尾指针置空
    }
}
 
QueueDataType QueueFront(Queue* pQ) //返回队头数据
{
    assert(pQ);                           
    assert(!QueueEmpty(pQ));    
 
    return pQ->pHead->data;
}
 
QueueDataType QueueBack(Queue* pQ) //返回队尾数据
{
    assert(pQ);
    assert(!QueueEmpty(pQ));
 
    return pQ->pTail->data;
}
 
int QueueSize(Queue* pQ) //返回队列大小
{
    assert(pQ);
 
    int count = 0;
    QueueNode* cur = pQ->pHead;
    while (cur != NULL) 
    {
        count++;
        cur = cur->next;
    }
    return count;
}
 
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;
 
 
MyStack* myStackCreate() {
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&st->q1);//q1是结构体，还要取地址
    QueueInit(&st->q2);//q2是结构体，还要取地址
    return st;
}
 
void myStackPush(MyStack* obj, int x) {
    if (!QueueEmpty(&obj->q1))//q1不为空（入到q1）
    {
        QueuePush(&obj->q1, x);
    }
    else//q2不为空（入到q2），或者两个都为空（入到哪都行）
    {
        QueuePush(&obj->q2, x);
    }
}
 
int myStackPop(MyStack* obj) {
    //题目要求int pop() 移除并返回栈顶元素。
    //法一：
    //if (!QueueEmpty(&obj->q1))//q1不为空,转移到q2保存，只剩最后一个时Pop掉
    //{
    //    while (QueueSize(&obj->q1) > 1)
    //    {
    //        QueuePush(&obj->q2, QueueFront(&obj->q1));//从q1取数据Push到q2
    //        QueuePop(&obj->q1);
    //    }
    //    int ret = QueueFront(&obj->q1);
    //    QueuePop(&obj->q1);//题目要求int pop() 移除并返回栈顶元素。
    //    return ret;
    //}
    //else//q2不为空,转移到q1保存，只剩最后一个时Pop掉
    //{
    //    while (QueueSize(&obj->q2) > 1)
    //    {
    //        QueuePush(&obj->q1, QueueFront(&obj->q2));//从q2取数据Push到q1
    //        QueuePop(&obj->q2);
    //    }
    //    int ret = QueueFront(&obj->q2);
    //    QueuePop(&obj->q2);
    //    return ret;
    //}
    //法二：
    Queue* emptyQ = &obj->q1;//假设q1为空 q2非空
    Queue* nonemptyQ = &obj->q2;
    if (!QueueEmpty(&obj->q1))//假设失败，倒过来
    {
        emptyQ = &obj->q2;
        nonemptyQ = &obj->q1;
    }
    while (QueueSize(nonemptyQ) > 1)
    {
        QueuePush(emptyQ, QueueFront(nonemptyQ));//从非空队列取数据Push到空队列
        QueuePop(nonemptyQ);
    }
    int ret = QueueFront(nonemptyQ);
    QueuePop(nonemptyQ);
    return ret;
}
 
int myStackTop(MyStack* obj) {
    //题目要求int top() 返回栈顶元素。（队列尾）队列不能删尾，能取尾
    if (!QueueEmpty(&obj->q1))//q1不为空
    {
        return QueueBack(&obj->q1);
    }
    else//q2不为空
    {
        return QueueBack(&obj->q2);
    }
}
 
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
 
void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

解析代码：(看题解的思路)(两个队列)

用C++写后看题解，然后用C语言写，穿越回来贴一下：

typedef int QueueDataType;   //队列类型
 
typedef struct QueueNode 
{
    struct QueueNode* next;  //指向下一个节点
    QueueDataType data;      //数据
} QueueNode;
 
typedef struct Queue//如果不设置成结构体就需要传二级指针，还要传两个参数
{
    QueueNode* pHead;
    QueueNode* pTail;
} Queue;
 
void QueueInit(Queue* pQ);//初始化队列
void QueueDestroy(Queue* pQ);//销毁队列
bool QueueEmpty(Queue* pQ);//判断队列是否为空
void QueuePush(Queue* pQ, QueueDataType x);//入队
void QueuePop(Queue* pQ);//出队(删数据)
QueueDataType QueueFront(Queue* pQ);//返回队头数据
QueueDataType QueueBack(Queue* pQ);//返回队尾数据
int QueueSize(Queue* pQ);//返回队列大小
 
void QueueInit(Queue* pQ) 
{
    assert(pQ);
 
    pQ->pHead = pQ->pTail = NULL;
}
 
void QueueDestroy(Queue* pQ) 
{
    assert(pQ); 
 
    QueueNode* cur = pQ->pHead;
    while (cur != NULL) 
    {
        QueueNode* curNext = cur->next;  //防止释放cur后找不到其下一个节点
        free(cur);                     
        cur = curNext;                   
    }
    pQ->pHead = pQ->pTail = NULL; 
}
 
bool QueueEmpty(Queue* pQ) 
{
    assert(pQ); 
 
    return pQ->pHead == NULL;//如果成立则为True，不成立则为False
}
 
//入队：队尾入数据，队头出(删)数据。如果是第一个入队的(队列为空)则既要当头又当尾
void QueuePush(Queue* pQ, QueueDataType x) 
{
    assert(pQ);
 
    QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
    if (new_node == NULL)
    {
        printf("malloc failed!\n");
        exit(-1);
    }
    new_node->data = x;     //待插入的数据
    new_node->next = NULL;  //新的数据指向空
 
    if (pQ->pHead == NULL)//情况1: 队列为空
    {           
        pQ->pHead = pQ->pTail = new_node;
    }
    else //情况2: 队列不为空   队尾入数据
    {                              
        pQ->pTail->next = new_node;  //在现有尾的后一个节点放置new_node
        pQ->pTail = new_node;        //更新pTail，使它指向新的尾
    }
}
 
void QueuePop(Queue* pQ) // 出队：队尾入数据，队头出(删)数据
{
    assert(pQ);                          
    assert(!QueueEmpty(pQ));  
 
    QueueNode* headNext = pQ->pHead->next; //队头出数据，防止释放pHead后找不到其下一个节点
    free(pQ->pHead);
    pQ->pHead = headNext;                  //更新头 
 
    if (pQ->pHead == NULL)//删完之后 pHead == NULL 了 pTail 还是野指针
    {
        pQ->pTail = NULL;//处理一下尾指针，将尾指针置空
    }
}
 
QueueDataType QueueFront(Queue* pQ) //返回队头数据
{
    assert(pQ);                           
    assert(!QueueEmpty(pQ));    
 
    return pQ->pHead->data;
}
 
QueueDataType QueueBack(Queue* pQ) //返回队尾数据
{
    assert(pQ);
    assert(!QueueEmpty(pQ));
 
    return pQ->pTail->data;
}
 
int QueueSize(Queue* pQ) //返回队列大小
{
    assert(pQ);
 
    int count = 0;
    QueueNode* cur = pQ->pHead;
    while (cur != NULL) 
    {
        count++;
        cur = cur->next;
    }
    return count;
}
 
typedef struct {    //C++看题解的思路 push麻烦了点，但其它都简单了
    Queue q1;
    Queue q2;
} MyStack;
 
 
MyStack* myStackCreate() {
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&st->q1);//q1是结构体，还要取地址
    QueueInit(&st->q2);//q2是结构体，还要取地址
    return st;
}
 
void myStackPush(MyStack* obj, int x) {
    /*if (!QueueEmpty(&obj->q1))//q1不为空（入到q1）
    {
        QueuePush(&obj->q1, x);
    }
    else//q2不为空（入到q2），或者两个都为空（入到哪都行）
    {
        QueuePush(&obj->q2, x);
    }*/
 
    //C++看题解的思路
    QueuePush(&obj->q2, x); // q2入队列
    while (!QueueEmpty(&obj->q1)) // 把q1的元素全入到q2
    {
        QueuePush(&obj->q2, QueueFront(&obj->q1));
        QueuePop(&obj->q1);
    } 
    //swap(q1, q2); // 交换q1和q2,保证q1任何时候都是栈的属性
    //没有交换函数，此时q1为空，把q2元素push到q1，然后pop掉q2即可
    while(!QueueEmpty(&obj->q2))
    {
        QueuePush(&obj->q1, QueueFront(&obj->q2));
        QueuePop(&obj->q2);
    }
}
 
int myStackPop(MyStack* obj) {
    //题目要求int pop() 移除并返回栈顶元素。
    //法一：
    //if (!QueueEmpty(&obj->q1))//q1不为空,转移到q2保存，只剩最后一个时Pop掉
    //{
    //    while (QueueSize(&obj->q1) > 1)
    //    {
    //        QueuePush(&obj->q2, QueueFront(&obj->q1));//从q1取数据Push到q2
    //        QueuePop(&obj->q1);
    //    }
    //    int ret = QueueFront(&obj->q1);
    //    QueuePop(&obj->q1);//题目要求int pop() 移除并返回栈顶元素。
    //    return ret;
    //}
    //else//q2不为空,转移到q1保存，只剩最后一个时Pop掉
    //{
    //    while (QueueSize(&obj->q2) > 1)
    //    {
    //        QueuePush(&obj->q1, QueueFront(&obj->q2));//从q2取数据Push到q1
    //        QueuePop(&obj->q2);
    //    }
    //    int ret = QueueFront(&obj->q2);
    //    QueuePop(&obj->q2);
    //    return ret;
    //}
 
    //法二：
    /*Queue* emptyQ = &obj->q1;//假设q1为空 q2非空
    Queue* nonemptyQ = &obj->q2;
    if (!QueueEmpty(&obj->q1))//假设失败，倒过来
    {
        emptyQ = &obj->q2;
        nonemptyQ = &obj->q1;
    }
    while (QueueSize(nonemptyQ) > 1)
    {
        QueuePush(emptyQ, QueueFront(nonemptyQ));//从非空队列取数据Push到空队列
        QueuePop(nonemptyQ);
    }
    int ret = QueueFront(nonemptyQ);
    QueuePop(nonemptyQ);
    return ret;*/
 
    //C++看题解的思路
    int r = QueueFront(&obj->q1);
    QueuePop(&obj->q1);
    return r;
}
 
int myStackTop(MyStack* obj) {
    //题目要求int top() 返回栈顶元素。（队列尾）队列不能删尾，能取尾
    /*if (!QueueEmpty(&obj->q1))//q1不为空
    {
        return QueueBack(&obj->q1);
    }
    else//q2不为空
    {
        return QueueBack(&obj->q2);
    }*/
 
    //C++看题解的思路
    return QueueFront(&obj->q1);
}
 
bool myStackEmpty(MyStack* obj) {
    //return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
 
    //C++看题解的思路
    return QueueEmpty(&obj->q1);
}
 
void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

解析代码：(看题解的思路)(一个队列)

使用一个队列时，为了满足栈的特性，即最后入栈的元素最先出栈，同样需要满足队列前端的元素是最后入栈的元素。

入栈操作时，首先获得入栈前的元素个数 n，然后将元素入队到队列，再将队列中的前 n 个元素（即除了新入栈的元素之外的全部元素）依次出队并入队到队列，此时队列的前端的元素即为新入栈的元素，且队列的前端和后端分别对应栈顶和栈底。

由于每次入栈操作都确保队列的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除队列的前端元素并返回即可，获得栈顶元素操作只需要获得队列的前端元素并返回即可（不移除元素）。

由于队列用于存储栈内的元素，判断栈是否为空时，只需要判断队列是否为空即可。

typedef int QueueDataType;   //队列类型
 
typedef struct QueueNode 
{
    struct QueueNode* next;  //指向下一个节点
    QueueDataType data;      //数据
} QueueNode;
 
typedef struct Queue//如果不设置成结构体就需要传二级指针，还要传两个参数
{
    QueueNode* pHead;
    QueueNode* pTail;
} Queue;
 
void QueueInit(Queue* pQ);//初始化队列
void QueueDestroy(Queue* pQ);//销毁队列
bool QueueEmpty(Queue* pQ);//判断队列是否为空
void QueuePush(Queue* pQ, QueueDataType x);//入队
void QueuePop(Queue* pQ);//出队(删数据)
QueueDataType QueueFront(Queue* pQ);//返回队头数据
QueueDataType QueueBack(Queue* pQ);//返回队尾数据
int QueueSize(Queue* pQ);//返回队列大小
 
void QueueInit(Queue* pQ) 
{
    assert(pQ);
 
    pQ->pHead = pQ->pTail = NULL;
}
 
void QueueDestroy(Queue* pQ) 
{
    assert(pQ); 
 
    QueueNode* cur = pQ->pHead;
    while (cur != NULL) 
    {
        QueueNode* curNext = cur->next;  //防止释放cur后找不到其下一个节点
        free(cur);                     
        cur = curNext;                   
    }
    pQ->pHead = pQ->pTail = NULL; 
}
 
bool QueueEmpty(Queue* pQ) 
{
    assert(pQ); 
 
    return pQ->pHead == NULL;//如果成立则为True，不成立则为False
}
 
//入队：队尾入数据，队头出(删)数据。如果是第一个入队的(队列为空)则既要当头又当尾
void QueuePush(Queue* pQ, QueueDataType x) 
{
    assert(pQ);
 
    QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
    if (new_node == NULL)
    {
        printf("malloc failed!\n");
        exit(-1);
    }
    new_node->data = x;     //待插入的数据
    new_node->next = NULL;  //新的数据指向空
 
    if (pQ->pHead == NULL)//情况1: 队列为空
    {           
        pQ->pHead = pQ->pTail = new_node;
    }
    else //情况2: 队列不为空   队尾入数据
    {                              
        pQ->pTail->next = new_node;  //在现有尾的后一个节点放置new_node
        pQ->pTail = new_node;        //更新pTail，使它指向新的尾
    }
}
 
void QueuePop(Queue* pQ) // 出队：队尾入数据，队头出(删)数据
{
    assert(pQ);                          
    assert(!QueueEmpty(pQ));  
 
    QueueNode* headNext = pQ->pHead->next; //队头出数据，防止释放pHead后找不到其下一个节点
    free(pQ->pHead);
    pQ->pHead = headNext;                  //更新头 
 
    if (pQ->pHead == NULL)//删完之后 pHead == NULL 了 pTail 还是野指针
    {
        pQ->pTail = NULL;//处理一下尾指针，将尾指针置空
    }
}
 
QueueDataType QueueFront(Queue* pQ) //返回队头数据
{
    assert(pQ);                           
    assert(!QueueEmpty(pQ));    
 
    return pQ->pHead->data;
}
 
QueueDataType QueueBack(Queue* pQ) //返回队尾数据
{
    assert(pQ);
    assert(!QueueEmpty(pQ));
 
    return pQ->pTail->data;
}
 
int QueueSize(Queue* pQ) //返回队列大小
{
    assert(pQ);
 
    int count = 0;
    QueueNode* cur = pQ->pHead;
    while (cur != NULL) 
    {
        count++;
        cur = cur->next;
    }
    return count;
}
 
typedef struct {    //C++看题解的思路（一个队列） push麻烦了点，但其它都简单了
    Queue q1;
} MyStack;
 
 
MyStack* myStackCreate() {
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&st->q1);//q1是结构体，还要取地址
    return st;
}
 
void myStackPush(MyStack* obj, int x) {
    /*if (!QueueEmpty(&obj->q1))//q1不为空（入到q1）
    {
        QueuePush(&obj->q1, x);
    }
    else//q2不为空（入到q2），或者两个都为空（入到哪都行）
    {
        QueuePush(&obj->q2, x);
    }*/
 
    //C++看题解的思路
    /*QueuePush(&obj->q2, x); // q2入队列
    while (!QueueEmpty(&obj->q1)) // 把q1的元素全入到q2
    {
        QueuePush(&obj->q2, QueueFront(&obj->q1));
        QueuePop(&obj->q1);
    } 
    //swap(q1, q2); // 交换q1和q2,保证q1任何时候都是栈的属性
    //没有交换函数，此时q1为空，把q2元素push到q1，然后pop掉q2即可
    while(!QueueEmpty(&obj->q2))
    {
        QueuePush(&obj->q1, QueueFront(&obj->q2));
        QueuePop(&obj->q2);
    }*/
 
    //一个队列：
    QueuePush(&obj->q1, x);
    int n = QueueSize(&obj->q1) - 1;
    while(n--)
    {
        QueuePush(&obj->q1, QueueFront(&obj->q1));
        QueuePop(&obj->q1);
    }
}
 
int myStackPop(MyStack* obj) {
    //题目要求int pop() 移除并返回栈顶元素。
    //法一：
    //if (!QueueEmpty(&obj->q1))//q1不为空,转移到q2保存，只剩最后一个时Pop掉
    //{
    //    while (QueueSize(&obj->q1) > 1)
    //    {
    //        QueuePush(&obj->q2, QueueFront(&obj->q1));//从q1取数据Push到q2
    //        QueuePop(&obj->q1);
    //    }
    //    int ret = QueueFront(&obj->q1);
    //    QueuePop(&obj->q1);//题目要求int pop() 移除并返回栈顶元素。
    //    return ret;
    //}
    //else//q2不为空,转移到q1保存，只剩最后一个时Pop掉
    //{
    //    while (QueueSize(&obj->q2) > 1)
    //    {
    //        QueuePush(&obj->q1, QueueFront(&obj->q2));//从q2取数据Push到q1
    //        QueuePop(&obj->q2);
    //    }
    //    int ret = QueueFront(&obj->q2);
    //    QueuePop(&obj->q2);
    //    return ret;
    //}
 
    //法二：
    /*Queue* emptyQ = &obj->q1;//假设q1为空 q2非空
    Queue* nonemptyQ = &obj->q2;
    if (!QueueEmpty(&obj->q1))//假设失败，倒过来
    {
        emptyQ = &obj->q2;
        nonemptyQ = &obj->q1;
    }
    while (QueueSize(nonemptyQ) > 1)
    {
        QueuePush(emptyQ, QueueFront(nonemptyQ));//从非空队列取数据Push到空队列
        QueuePop(nonemptyQ);
    }
    int ret = QueueFront(nonemptyQ);
    QueuePop(nonemptyQ);
    return ret;*/
 
    //C++看题解的思路  //两个队列一个队列适用
    int r = QueueFront(&obj->q1);
    QueuePop(&obj->q1);
    return r;
}
 
int myStackTop(MyStack* obj) {
    //题目要求int top() 返回栈顶元素。（队列尾）队列不能删尾，能取尾
    /*if (!QueueEmpty(&obj->q1))//q1不为空
    {
        return QueueBack(&obj->q1);
    }
    else//q2不为空
    {
        return QueueBack(&obj->q2);
    }*/
 
    //C++看题解的思路 //两个队列一个队列适用
    return QueueFront(&obj->q1);
}
 
bool myStackEmpty(MyStack* obj) {
    //return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
 
    //C++看题解的思路 //两个队列一个队列适用
    return QueueEmpty(&obj->q1);
}
 
void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    free(obj);
}

力扣链接：232. 用栈实现队列

难度简单

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作

（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素

int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：

["MyQueue", "push", "push", "peek", "pop", "empty"]

[[], [1], [2], [], [], []]

输出：

[null, null, null, 1, 1, false]

解释：

MyQueue myQueue = new MyQueue();

myQueue.push(1); // queue is: [1]

myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)

myQueue.peek(); // return 1

myQueue.pop(); // return 1, queue is [2]

myQueue.empty(); // return false

提示：

1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty

假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）

进阶：

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

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) {
 
}
 
/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

解析代码：

我们知道，栈与队列的原理刚好相反，对于栈是【FILO】，对于队列是【FIFO】。

这就需要我们灵活地去使用这两种数据结构进行解题。对于本题，因为需要使用栈来实现队列，

那还需要像我们上一题那样将两个队列倒来倒去实现一个出栈的操作吗？

答案是：不需要，对于这一题而言，我们需要有一个明确的思路，

也是去定义两个栈，一个栈专门入数据，一个栈专门出数据，（专门入数据的栈的数据转移到专门出数据的栈，此时专门出数据的栈出数据就符合题意了，专门出数据的栈空后，再继续转移）（可以画图理解）具体的实现在下面

（和上题本质是一样的，但最优形态也有不一样的）（先入后出改为先入先出）

先把上篇写的栈复制粘贴过来（char改回int）链接：

数据结构与算法⑧(第三章_上)栈的概念和实现(力扣：20. 有效的括号)_GR C的博客-CSDN博客

typedef int StackDataType;
 
typedef struct Stack 
{
    StackDataType* array;  //数组
    int top;               //栈顶
    int capacity;          //容量
} Stack;
 
void StackInit(Stack* ps);
void StackDestroy(Stack* ps);
void StackPush(Stack* ps, StackDataType x);
bool StackEmpty(Stack* ps);
void StackPop(Stack* ps);
StackDataType StackTop(Stack* ps);
int StackSize(Stack* ps);
 
void StackInit(Stack* ps)//初始化
{
    assert(ps);
    ps->array = NULL;
    ps->top = 0;  // ps->top = -1
    ps->capacity = 0;
}
 
void StackDestroy(Stack* ps)//销毁
{
    assert(ps);
 
    free(ps->array);
    ps->array = NULL;
    ps->capacity = ps->top = 0;
}
 
void StackPush(Stack* ps, StackDataType x)//进栈
{
    assert(ps);
    if (ps->top == ps->capacity) 
    {
        int new_capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        StackDataType* tmp_arr =(StackDataType *) realloc(ps->array, sizeof(StackDataType) * new_capacity);
        if (tmp_arr == NULL) 
        {
            printf("realloc failed!\n");
            exit(-1);
        }
        // 更新
        ps->array = tmp_arr;
        ps->capacity = new_capacity;
    }
 
    ps->array[ps->top] = x;// 填入数据
    ps->top++;
}
 
bool StackEmpty(Stack* ps)//判断栈是否为空
{
    assert(ps);
 
    return ps->top == 0; //等于0就是空，就是真
}
 
void StackPop(Stack* ps)// 出栈
{
    assert(ps);
    //assert(ps->top > 0);  //防止top为空
    assert(!StackEmpty(ps));
 
    ps->top--;
}
 
StackDataType StackTop(Stack* ps)//返回栈顶数据
{
    assert(ps);
    //assert(ps->top > 0);  //防止top为空
    assert(!StackEmpty(ps));
 
    return ps->array[ps->top - 1];
}
 
int StackSize(Stack* ps) //计算栈的大小
{
    assert(ps);
 
    return ps->top;// 因为我们设定top是指向栈顶的下一个，所以top就是size
}
 
typedef struct {
    Stack pushST;
    Stack popST;
} MyQueue;
 
 
MyQueue* myQueueCreate() {
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&q->pushST);
    StackInit(&q->popST);
 
    return q;
}
 
void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushST, x);
}
 
int myQueuePop(MyQueue* obj) {
    //int pop() 从队列的开头移除并返回元素
    //如果popST中没有数据，就把pushST的数据拿过去
    //这样popST的数据就符合先进先出了
    if (StackEmpty(&obj->popST))
    {
        while (!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST, StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    //有数据就直接出（删后返回）
    int ret = StackTop(&obj->popST);
    StackPop(&obj->popST);
    return ret;
}
 
int myQueuePeek(MyQueue* obj) {
    //int peek() 返回队列开头的元素
    //如果popST中没有数据，就把pushST的数据拿过去
    if (StackEmpty(&obj->popST))
    {
        while (!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST, StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    return StackTop(&obj->popST);//不删，直接取
}
 
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}
 
void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->pushST);
    StackDestroy(&obj->popST);
    free(obj);
}
 
/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

数据结构与算法⑨(第三章_下)队列的概念和实现(力扣：225+232+622)（下）：https://developer.aliyun.com/article/1513407

数据结构与算法⑨(第三章_下)队列的概念和实现(力扣：225+232+622)（上）

一、队列（Queue）

队列的概念：

队列的结构：

二、队列的定义

链式队列

三、队列的实现（完整代码）

Queue.h

Queue.c

Test.c

四、力扣OJ题

力扣链接：225. 用队列实现栈

解析代码：

解析代码：(看题解的思路)(两个队列)

解析代码：(看题解的思路)(一个队列)

力扣链接：232. 用栈实现队列

解析代码：

热门文章

最新文章

相关课程

相关电子书

相关实验场景