队列基础练习（C语言实现）

队列基础练习

用队列实现栈

用栈实现队列

设计循环队列

队列基础练习

用队列实现栈

题目链接：225. 用队列实现栈 - 力扣（LeetCode）

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（ push、 top、 pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

思路解析：

本题要求用两个队列实现一个栈，队列的入队和出队顺序为先进先出，而栈的入栈和出栈顺序为后进先出，则在设计时可以参考以下思路：

因为队列满足先进先出，所以一个队列中的数据转移到另一个队列时不改变原来队列中数据的排列顺序，但是栈的数据是后进先出，所以当非空队列向空队列转移数据时只需要保留非空队列中的最后一个数据，再让该数据出队即可，而栈和队列的添加数据顺序相同，都是放在最后一个数据后的位置，所以插入数据只需要插入到当前非空队列的尾部即可

参考答案：

/*
 * @lc app=leetcode.cn id=225 lang=c
 *
 * [225] 用队列实现栈
 */

// @lc code=start

// 队列头文件
// 定义队列数据类型
typedef int QDataType;

// 定义队列的数据节点
typedef struct QueueNode
{
    QDataType data;
    struct QueueNode *next; // 下一个数据节点的位置
} QNode;

// 定义管理队列的结构
typedef struct Queue
{
    QNode *phead; // 队列头
    QNode *ptail; // 队列尾，便于找尾结点，省去每次入队都需要遍历队列
    int size;     // 队列的数据个数
} Queue;

// 初始化队列
void QueueInit(Queue *q);
// 销毁队列
void QueueDestroy(Queue *q);
// 数据入队
void QueuePush(Queue *q, QDataType x);
// 数据出队
void QueuePop(Queue *q);
// 获取队尾数据
QDataType QueueRear(Queue *q);
// 获取队头数据
QDataType QueueFront(Queue *q);
// 判断队列是否为空
bool QueueEmpty(Queue *q);
// 获取队列元素个数
int QueueSize(Queue *q);

// 队列实现
// 初始化队列
void QueueInit(Queue *q)
{
    // 判断是否存在队列
    assert(q);

    q->phead = q->ptail = NULL;
    q->size = 0;
}
// 销毁队列
void QueueDestroy(Queue *q)
{
    // 确保有队列的存在
    assert(q);
    // 删除队列的每一个节点
    // 注意循环条件不要用!QueueEmpty(q)，因为如果!QueueEmpty(q)只能说明队列不为空，但是q->phead是否为空不确定
    while (q->phead)
    {
        QNode *next = q->phead->next;
        free(q->phead);
        q->phead = next;
    }
    q->phead = q->ptail = NULL;
    q->size = 0;
}
// 数据入队
void QueuePush(Queue *q, QDataType x)
{
    // 确保存在队列
    assert(q);

    // 为数据创建节点
    QNode *newNode = (QNode *)malloc(sizeof(QNode));
    assert(newNode);
    newNode->data = x;
    newNode->next = NULL;
    // 插入数据
    // 队列为空，更新头和尾节点
    // 队列不为空，更新尾结点
    // 尾插思路
    if (!q->ptail)
    {
        q->phead = q->ptail = newNode;
    }
    else
    {
        q->ptail->next = newNode;
        q->ptail = q->ptail->next; // 更新ptail到新的节点
    }

    // 注意更新size
    q->size++;
}
// 数据出队
void QueuePop(Queue *q)
{
    // 确保有队列存在
    assert(q);
    // 如果队列为空不执行删除
    assert(!QueueEmpty(q));

    // 头删思路
    if (q->phead == q->ptail)
    {
        // 注意考虑到最后一个指针的ptail需要置空问题，防止野指针
        q->ptail = NULL;
    }
    QNode *next = q->phead->next;
    free(q->phead);
    q->phead = next;

    // 注意更新size
    q->size--;
}
// 获取队尾数据
QDataType QueueRear(Queue *q)
{
    // 确保有队列存在
    assert(q);
    // 确保队列不为空
    assert(!QueueEmpty(q));

    // 返回ptail指向的位置的值
    return q->ptail->data;
}
// 获取队头数据
QDataType QueueFront(Queue *q)
{
    // 确保有队列存在
    assert(q);
    // 确保队列不为空
    assert(!QueueEmpty(q));

    // 返回phead指向的位置的值
    return q->phead->data;
}
// 判断队列是否为空
bool QueueEmpty(Queue *q)
{
    // 确保有队列的存在
    assert(q);

    //&&只有全部满足才返回为真
    return q->phead == NULL && q->ptail == NULL && q->size == 0;
}
// 获取队列元素个数
int QueueSize(Queue *q)
{
    // 确保有队列的存在
    assert(q);

    return q->size;
}

typedef struct
{
    // 定义两个队列结构
    Queue q1;
    Queue q2;
} MyStack;

MyStack *myStackCreate()
{
    // 初始化队列和栈
    MyStack *stack = (MyStack *)malloc(sizeof(MyStack));

    // 初始化维护队列指针
    QueueInit(&(stack->q1));
    QueueInit(&(stack->q2));

    return stack;
}

void myStackPush(MyStack *obj, int x)
{
    assert(obj);
    // 向非空的队列中插入数据
    if (QueueEmpty(&(obj->q1)))
    {
        QueuePush(&(obj->q2), x);
    }
    else
    {
        QueuePush(&(obj->q1), x);
    }
}

int myStackPop(MyStack *obj)
{
    assert(obj);
    // 向非空的队列中插入数据
    // 获取非空队列和空队列
    Queue *pNotEmpty = &(obj->q1);
    Queue *pEmpty = &(obj->q2);
    if (QueueEmpty(&(obj->q1)))
    {
        pNotEmpty = &(obj->q2);
        pEmpty = &(obj->q1);
    }

    // 非空队列中留下一个数据，剩余数据转移到空队列
    while (pNotEmpty->phead != pNotEmpty->ptail)
    {
        QueuePush(pEmpty, QueueFront(pNotEmpty));
        QueuePop(pNotEmpty);
    }
    // 也可以通过size判断
    // while (QueueSize(pNotEmpty) > 1)
    // {
    //     QueuePush(pEmpty, QueueFront(pNotEmpty));
    //     QueuePop(pNotEmpty);
    // }

    int data = pNotEmpty->ptail->data;
    QueuePop(pNotEmpty);

    return data;
}

int myStackTop(MyStack *obj)
{
    assert(obj);
    // 获取非空队列的队头数据
    if (QueueEmpty(&(obj->q1)))
    {
        return obj->q2.ptail->data;
    }
    else
    {
        return obj->q1.ptail->data;
    }
}

bool myStackEmpty(MyStack *obj)
{
    assert(obj);
    return QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2));
}

void myStackFree(MyStack *obj)
{
    assert(obj);
    QueueDestroy(&(obj->q1));
    QueueDestroy(&(obj->q2));
    free(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);
*/
// @lc code=end

用栈实现队列

题目链接：232. 用栈实现队列 - 力扣（LeetCode）

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（ 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（双端队列）来模拟一个栈，只要是标准的栈操作即可。

思路解析：

本题和上题思路类似，但是不建议直接照搬上一题的思路，参考以下思路：

定义两个栈，但是不同于上题的两个队列（两个队列没有区分），本题中的两个栈需要作区分，一个栈作为数据出模拟队列的栈，另一个作为数据入模拟队列的栈

因为数据出栈顺序为后进先出，所以在pushST中的数据转移到popST中后会改变原数据的顺序，而改变后的顺序中数据出栈刚好和队列中的数据出队相同，所以可以区分两个不同的栈，一个专用为存储进队列的数据，另一个专用为存储出队列的数据，当popST数据全部出完后再将pushST中数据转移到popST进行下一次的数据出队

参考答案：

/*
 * @lc app=leetcode.cn id=232 lang=c
 *
 * [232] 用栈实现队列
 */

// @lc code=start
// 栈的实现
typedef int STDataType;
typedef struct stack
{
    STDataType *data;
    int top;      // 栈顶位置
    int capacity; // 元素个数
} ST;

// 栈的初始化
void STInit(ST *st);
// 栈的销毁
void STDestroy(ST *st);
// 数据入栈
void STPush(ST *st, STDataType x);
// 数据出栈
void STPop(ST *st);
// 判断栈是否为空
bool STEmpty(ST *st);
// 获取栈顶元素
STDataType STTop(ST *st);
// 获取栈内数据个数
int STSize(ST *st);

// 栈的初始化
void STInit(ST *st)
{
    // 判断是否存在队列
    assert(st);
    // 初始化队列
    st->data = NULL;
    st->top = 0; // 栈顶指针指向存储数据的下一个位置，代表栈内无数据
    // st->top = -1;//栈顶指针指向存储数据的位置，代表栈内无数据
    st->capacity = 0;
}

// 栈的销毁
void STDestroy(ST *st)
{
    // 确保有栈的存在
    assert(st);
    // 销毁栈
    free(st->data);
    st->data = NULL;
    // top和capacity更改为无数据的位置
    st->top = st->capacity = 0;
}

// 数据入栈
void STPush(ST *st, STDataType x)
{
    // 确保有栈的存在
    assert(st);
    // 向top位置增加数据，并使top向后移动
    // 需要判断栈的容量大小
    if (st->top == st->capacity)
    {
        // 如果栈的空间为0，则开辟四个空间，如果栈容量不为0，则扩容原来容量的2倍
        int newCapacity = st->capacity == 0 ? 4 : st->capacity * 2;
        STDataType *tmp = (STDataType *)realloc(st->data, sizeof(STDataType) * newCapacity);
        assert(tmp);
        st->data = tmp;
        // 注意更新容量大小
        st->capacity = newCapacity;
    }

    // 数据压栈并改变top
    st->data[st->top++] = x;
}
// 数据出栈
void STPop(ST *st)
{
    // 确保有栈的存在
    assert(st);
    // 确保栈不会越界
    assert(!STEmpty(st));

    // 直接移动top指针，“看不见即删除”
    st->top--;
}
// 判断栈是否为空
bool STEmpty(ST *st)
{
    // 确保有栈的存在
    assert(st);
    // 栈为空返回真，栈不为空返回假
    return st->top == 0; // 判断表达式返回值只有1和0，如果为真返回1(true)，如果为假返回0(false)
}
// 获取栈顶元素
STDataType STTop(ST *st)
{
    // 确保栈存在
    assert(st);
    // 确保栈不为空
    assert(!STEmpty(st));
    // top为栈内数据的下一个位置，要获取当前位置的元素需要-1操作
    return st->data[st->top - 1];
}

// 获取栈内数据个数
int STSize(ST *st)
{
    assert(st);
    return st->top;
}

typedef struct
{
    ST pushST;
    ST popST;
} MyQueue;

MyQueue *myQueueCreate()
{
    // 初始化栈
    MyQueue *Queue = (MyQueue *)malloc(sizeof(MyQueue));
    STInit(&(Queue->pushST));
    STInit(&(Queue->popST));

    return Queue;
}

void myQueuePush(MyQueue *obj, int x)
{
    assert(obj);

    // 向pushSt栈中插入数据
    STPush(&(obj->pushST), x);
}

int myQueuePop(MyQueue *obj)
{
    assert(obj);
    // 复用myQueuePeek函数
    int data = myQueuePeek(obj);
    STPop(&(obj->popST));
    return data;
}

int myQueuePeek(MyQueue *obj)
{
    assert(obj);
    int data = 0;
    // 获取队列的头元素相当于栈的顶部元素
    // 如果popST不为空先执行popST
    if (!STEmpty(&(obj->popST)))
    {
        data = STTop(&(obj->popST));
        return data;
    }
    //  如果pushST中有数据并且popST为空，将数据移到popST中
    while (!STEmpty(&(obj->pushST)))
    {
        STPush(&(obj->popST), STTop(&(obj->pushST)));
        STPop(&(obj->pushST));
    }

    // 从popST中出数据
    data = STTop(&(obj->popST));
    return data;
}

bool myQueueEmpty(MyQueue *obj)
{
    assert(obj);
    return STEmpty(&(obj->pushST)) && STEmpty(&(obj->popST));
}

void myQueueFree(MyQueue *obj)
{
    assert(obj);
    STDestroy(&(obj->pushST));
    STDestroy(&(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);
*/
// @lc code=end

设计循环队列

题目链接：622. 设计循环队列 - 力扣（LeetCode）

设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

思路解析：

设计一个循环队列时需要考虑如何区分什么时候代表队列为满和队列为空，因为本题可以用数组来实现，故可以考虑当最后一个数据的位置的下一个位置为第一个元素所在的位置即为队列满状态，同样，可以定义一个记录有效数据的变量，当有效数据值为0时说明循环队列为空（注意不要使用该变量判断是否未满，因为数据在存储到数组中的最后一个有效位置时，还可以因为是循环回到数组的第一个有效位置开始继续存），下面是本题的每一个函数的基本思路：

循环队列的结构体设计

在循环队列中，需要有一个队列存在，故需要一个指向数组的指针data，另外需要一个数据的位置的下一个位置，故需要一个变量rear记录该位置，而因为需要获取队头数据，故需要一个变量front记录该位置（切忌认为数组的第一个数据即为队头数据），再者需要一个变量记录当前队列中的有效数据个数size，最后因为题目并未固定循环队列的大小，故需要一个变量k来确定数组在开辟时的大小

循环队列的初始化

在循环队列的初始化函数MyCircularQueue *myCircularQueueCreate(int k)中，函数参数为循环队列的大小，所以初始化过程中不可遗忘将该k给结构中的k，另外在初始化过程中，开辟的数组大小为k+1，但是数组的最后一个有效位置（即第k个位置）在队头指针front为数组的第一个元素的位置时不存储数据，其作用是在判断数组的下一个数据的位置时不会是因为循环回到了front的位置从而使rear == front

因为数组本身的物理结构是不可循环的（即数组下标不会在下一次访问越界时直接回到开头位置，需要人为控制），所以本题的主要思路是通过模运算来代替数组的下标，而因为当前数组的有效大小为k+1，此时数组最后一个有效数据下一个位置的下标为k（也即当前的rear位置），那么构成循环队列就是让rear指针指向的下一个有效数据位置为数组第一个元素的位置，那么因为数组实际开辟了6个空间，最后一个位置的下标为5，则有规律：小于6的数值取6的模可以得到原来被除数（即余数），大于等于6的数值取6的模可以得到被除数大于6的部分（即余数），此时直接用rear当做被除数，而k+1为除数来使下标构成循环，从而达到循环队列的目的，特殊情况例如，当rear越界为6时取6的模可以直接回到数组的第一个元素的位置，即rear % (k+1)

判断队列为空和判断队列为满

队列为空说明size == 0（或者front == rear时（注意这个判断用在开辟的空间为k+1时））；队列为满说明front == (rear + 1) % (k + 1)，即当前rear所在位置的下一个位置

数据入队和数据出队

数据入队时，首先需要判断是否队列为满，如果队列为满直接返回false，不为满时向rear%(k+1)的位置添加数据，同时更新rear = (rear + 1) % (k + 1)和size；数据出队时，需要判断队列是否为空，如果队列为空则直接放回false，不为空才可以删除数据，队列删除数据时会改变头的位置，所以需要更新front，即front = (front + 1) % (k + 1)，同时需要更新size

获取队列头数据和获取队列尾数据

如果队列不为空，则队列头数据即为front所在的位置的数据，否则无数据返回-1；如果队列不为空，则队列尾数据为rear所在位置的前一个位置的数据，但是注意rear为有效数据的下一个位置，所以需要获取rear的上一个位置的下标，参考取模思路，因为数组的最后一个元素下标为k，而模为k + 1，此时被除数取k + 1的模可以得到0~k值，因为rear % (k + 1)可以取到的范围已经是0 ~ k，所以此时需要加最大模值使被除数增大才可以使模从0开始，而最大增加数为k，所以此时取(rear + k) % (k + 1)即可返回到rear上一个元素的位置

循环队列空间释放

释放空间需要先释放数组的空间，再释放循环队列结构的空间

参考答案：

/*
 * @lc app=leetcode.cn id=622 lang=c
 *
 * [622] 设计循环队列
 */

// @lc code=start

// 数组实现
// 数组实现
typedef struct
{
    int *data; // 存储队列数据
    int k;     // 队列大小
    int size;  // 有效数据个数
    int front; // 队列头
    int rear;  // 队列尾
} MyCircularQueue;

MyCircularQueue *myCircularQueueCreate(int k)
{
    MyCircularQueue *Queue = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
    Queue->data = (int *)malloc(sizeof(int) * (k + 1));
    Queue->front = Queue->rear = 0;
    Queue->size = 0;
    Queue->k = k;

    return Queue;
}

bool myCircularQueueIsEmpty(MyCircularQueue *obj)
{
    assert(obj);
    if (obj->size == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool myCircularQueueIsFull(MyCircularQueue *obj)
{
    assert(obj);
    // 当rear的下一个为front时为队列满
    if (obj->front == (obj->rear + 1) % (obj->k + 1))
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool myCircularQueueEnQueue(MyCircularQueue *obj, int value)
{
    assert(obj);
    if (!myCircularQueueIsFull(obj))
    {
        // 队列未满时插入数据
        obj->data[obj->rear % (obj->k + 1)] = value;
        obj->rear = (obj->rear + 1) % (obj->k + 1);
        obj->size++;
        return true;
    }
    else
    {
        return false;
    }
}

bool myCircularQueueDeQueue(MyCircularQueue *obj)
{
    assert(obj);
    if (!myCircularQueueIsEmpty(obj))
    {
        // 队列不为空时删除数据
        obj->front = (obj->front + 1) % (obj->k + 1);
        obj->size--;
        return true;
    }
    else
    {
        return false;
    }
}

int myCircularQueueFront(MyCircularQueue *obj)
{
    assert(obj);
    if (!myCircularQueueIsEmpty(obj))
    {
        return obj->data[obj->front % (obj->k + 1)];
    }
    else
    {
        return -1;
    }
}

int myCircularQueueRear(MyCircularQueue *obj)
{
    assert(obj);
    if (!myCircularQueueIsEmpty(obj))
    {
        return obj->data[(obj->rear + obj->k) % (obj->k + 1)];
    }
    else
    {
        return -1;
    }
}

void myCircularQueueFree(MyCircularQueue *obj)
{
    assert(obj);
    free(obj->data);
    free(obj);
}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);

 * bool param_2 = myCircularQueueDeQueue(obj);

 * int param_3 = myCircularQueueFront(obj);

 * int param_4 = myCircularQueueRear(obj);

 * bool param_5 = myCircularQueueIsEmpty(obj);

 * bool param_6 = myCircularQueueIsFull(obj);

 * myCircularQueueFree(obj);
*/
// @lc code=end