【LeetCode刷题日志】225.用队列实现栈

妖狐艹你老母 2024-04-22 04:37 32阅读 0赞

![029e4c2ad845498ebf249bfa76c41a5f.png][]

>  *  ?个人主页：[库库的里昂][Link 1]
>  *  ?C/C++领域新星创作者
>  *  ?欢迎 ?点赞✍评论⭐收藏
>  *  ✨收录专栏：[LeetCode 刷题日志][LeetCode]
>  *  ?希望作者的文章能对你有所帮助，有不足的地方请在评论区留言指正，大家一起学习交流！?

**目录**

1.题目描述

2.解题思路+代码实现

方法一：两个队列

思路及算法：

代码实现：

方法二：一个队列

思路及算法：

代码实现：

--------------------

#### 1.题目描述 ####

[OJ链接][OJ] 【[leetcode][] 题号：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` 都保证栈不为空

**进阶：**你能否仅用一个队列来实现栈。

#### 2.解题思路+代码实现 ####

##### 方法一：两个队列 #####

###### 思路及算法： ######

为了满足栈的特性，即最后入栈的元素最先出栈，在使用队列实现栈时，应满足队列前端的元素是最后入栈的元素。可以使用两个队列实现栈的操作，其中q1用于存储栈内的元素，q2作为入栈操作的辅助队列。

入栈操作时，首先将元素入队到q2，然后将q1的全部元素依次出队并入队列q2 ，此时q2的前端的元素即为新入栈的元素，再将q1和q2互换，则q1的元素即为栈内的元素，q1的前端和后端分别对应栈顶和栈底。

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

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

###### 代码实现： ######

typedef int QDataType;
    typedef struct QueueNode
    {
        struct QueueNode* next;
        QDataType data;
    }QNode;
     
    typedef struct Queue
    {
        QNode* phead;
        QNode* ptail;
        int size;
    }Queue;
     
    void QueueInit(Queue* pq)
    {
        assert(pq);
        pq->phead = NULL;
        pq->ptail = NULL;
        pq->size = 0;
    }
    void QueueDestroy(Queue* pq)
    {
        assert(pq);
        QNode* cur = pq->phead;
        while (cur) {
            QNode* next = cur->next;
            free(cur);
            cur = next;
        }
        pq->phead = pq->ptail = NULL;
        pq->size = 0;
    }
    void QueuePush(Queue* pq, QDataType x)
    {
        assert(pq);
        QNode* newnode = (QNode*)malloc(sizeof(QNode));
        if (newnode == NULL) {
            perror("mallloc fail\n");
            return;
        }
        newnode->data = x;
        newnode->next = NULL;
        if (pq->ptail == NULL) {
            assert(pq->phead == NULL);
            pq->phead = pq->ptail = newnode;
        }
        else {
            pq->ptail->next = newnode;
            pq->ptail = newnode;
        }
        pq->size++;
    }
    bool QueueEmpty(Queue* pq)
    {
        assert(pq);
        return pq->size == 0;
    }
    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;
        }
        pq->size--;
    }
    QDataType QueueFront(Queue* pq)
    {
        assert(pq);
        assert(!QueueEmpty(pq));
        return pq->phead->data;
    }
    QDataType QueueBack(Queue* pq)
    {
        assert(pq);
        assert(!QueueEmpty(pq));
        return pq->ptail->data;
    }
    int QueueSize(Queue* pq)
    {
        assert(pq);
        return pq->size;
    }
     
    //------以下为OJ提供-------
     
    typedef struct {
        Queue q1;
        Queue q2;
    } MyStack;
     
    MyStack* myStackCreate() {
        MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
        if (obj == NULL) {
            perror("malloc fail");
            return NULL;
        }
        QueueInit(&obj->q1);
        QueueInit(&obj->q2);
        return obj;
    }
     
    void myStackPush(MyStack* obj, int x) {
        if (!QueueEmpty(&obj->q1)) {
            QueuePush(&obj->q1, x);
        }
        else {
            QueuePush(&obj->q2, x);
        }
    }
     
    int myStackPop(MyStack* obj) {
        Queue* pEmptyQ = &obj->q1;
        Queue* pNonEmptyQ = &obj->q2;
        if (!QueueEmpty(&obj->q1)) {
            pEmptyQ = &obj->q2;
            pNonEmptyQ = &obj->q1;
        }
        while (QueueSize(pNonEmptyQ) > 1) {
            QueuePush(pEmptyQ, QueueFront(pNonEmptyQ));
            QueuePop(pNonEmptyQ);
        }
        int top = QueueFront(pNonEmptyQ);
        QueuePop(pNonEmptyQ);
        return top;
    }
     
    int myStackTop(MyStack* obj) {
        if (!QueueEmpty(&obj->q1)) {
            return QueueBack(&obj->q1);
        }
        else {
            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);
    }

复杂度分析

*  时间复杂度：入栈操作O(n)，其余操作都是O(1)，其中n是栈内的元素个数。 入栈操作需要将q1中的n个元素出队，并入队n+1个元素到q2，共有2n+1次操作，每次出队和入队操作的时间复杂度都是O(1)，因此入栈操作的时间复杂度是 O(n)。 出栈操作对应将q1的前端元素出队，时间复杂度是 O(1)。 获得栈顶元素操作对应获得q1的前端元素，时间复杂度是O(1)。 判断栈是否为空操作只需要判断q1是否为空，时间复杂度是 O(1)。
 *  空间复杂度：O(n)，其中n是栈内的元素个数。需要使用两个队列存储栈内的元素。

##### 方法二：一个队列 #####

###### 思路及算法： ######

方法一使用了两个队列实现栈的操作，也可以使用一个队列实现栈的操作。

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

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

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

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

###### 代码实现： ######

typedef struct tagListNode {
        struct tagListNode* next;
        int val;
    } ListNode;
    
    typedef struct {
        ListNode* top;
    } MyStack;
    
    MyStack* myStackCreate() {
        MyStack* stk = calloc(1, sizeof(MyStack));
        return stk;
    }
    
    void myStackPush(MyStack* obj, int x) {
        ListNode* node = malloc(sizeof(ListNode));
        node->val = x;
        node->next = obj->top;
        obj->top = node;
    }
    
    int myStackPop(MyStack* obj) {
        ListNode* node = obj->top;
        int val = node->val;
        obj->top = node->next;
        free(node);
    
        return val;
    }
    
    int myStackTop(MyStack* obj) {
        return obj->top->val;
    }
    
    bool myStackEmpty(MyStack* obj) {
        return (obj->top == NULL);
    }
    
    void myStackFree(MyStack* obj) {
        while (obj->top != NULL) {
            ListNode* node = obj->top;
            obj->top = obj->top->next;
            free(node);
        }
        free(obj);
    }

复杂度分析

*  时间复杂度：入栈操作O(n)，其余操作都是O(1)，其中n是栈内的元素个数。 入栈操作需要将队列中的n个元素出队，并入队n+1个元素到队列，共有2n+1次操作，每次出队和入队操作的时间复杂度都是O(1)，因此入栈操作的时间复杂度是O(n)。 出栈操作对应将队列的前端元素出队，时间复杂度是O(1)。获得栈顶元素操作对应获得队列的前端元素，时间复杂度是O(1)。 判断栈是否为空操作只需要判断队列是否为空，时间复杂度是O(1)。
 *  空间复杂度：O(n)，其中n是栈内的元素个数。需要使用一个队列存储栈内的元素。

![24635f1b99a249a5b6a2488f1e379718.png][]

[029e4c2ad845498ebf249bfa76c41a5f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/d818807c588749efb3cb2ca3b7b6d5d7.png
[Link 1]: https://blog.csdn.net/m0_68662723
[LeetCode]: http://t.csdnimg.cn/j5fPj
[OJ]: https://leetcode.cn/problems/implement-stack-using-queues/
[leetcode]: https://so.csdn.net/so/search?q=leetcode&spm=1001.2101.3001.7020
[24635f1b99a249a5b6a2488f1e379718.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/d508a4db815140ee9c2cfcdd10289f0b.png