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

﹏ヽ暗。殇╰゛Y 2024-04-22 04:38 14阅读 0赞

![be4144439b7a441ea35f801e9265613e.png][]

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

**目录**

1.题目描述

2.解题思路+代码实现

方法：双栈

思路及算法：

代码实现：

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

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

[OJ链接][OJ] 【[leetcode][] 题号：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)` ，即使其中一个操作可能花费较长时间。

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

##### 方法：双栈 #####

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

将一个栈当作输入栈，用于压入push传入的数据；另一个栈当作输出栈，用于 pop和peek操作。

每次pop或peek时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

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

typedef int STDataType;
    typedef struct Stack
    {
    	STDataType* a;
    	int top;
    	int capacity;
    }ST;
     
    void STInit(ST* pst)
    {
    	assert(pst);
    	pst->a = NULL;
    	pst->top = 0;
    	pst->capacity = 0;
    }
     
    void STDestroy(ST* pst)
    {
    	assert(pst);
    	free(pst->a);
    	pst->a = NULL;
    	pst->top = 0;
    	pst->capacity = 0;
    }
     
    void STPush(ST* pst, STDataType x)
    {
    	if (pst->top == pst->capacity) {
    		int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
    		STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));
    		if (tmp == NULL) {
    			perror("realloc fail");
    			return;
    		}
    		pst->a = tmp;
    		pst->capacity = newCapacity;
    	}
    	pst->a[pst->top] = x;
    	pst->top++;
    }
     
    bool STEmpty(ST* pst)
    {
    	assert(pst);
    	return pst->top == 0;
    }
     
    void STPop(ST* pst)
    {
    	assert(pst);
    	assert(!STEmpty(pst));
    	pst->top--;
    }
     
    STDataType STTop(ST* pst)
    {
    	assert(pst);
    	assert(!STEmpty(pst));
    	return pst->a[pst->top - 1];
    }
     
    int STSize(ST* pst)
    {
    	assert(pst);
    	return pst->top;
    }
     
    //------以下为OJ提供-------
     
    typedef struct {
    	ST pushst;
    	ST popst;
    } MyQueue;
     
    MyQueue* myQueueCreate() {
    	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    	if (obj == NULL) {
    		perror("malloc fail");
    		return 0;
    	}
    	STInit(&obj->pushst);
    	STInit(&obj->popst);
    	return obj;
    }
     
    void myQueuePush(MyQueue* obj, int x) {
    	STPush(&obj->pushst, x);
    }
     
    int myQueuePop(MyQueue* obj) {
    	int front = myQueuePeek(obj);
    	STPop(&obj->popst);
    	return front;
    }
     
    int myQueuePeek(MyQueue* obj) {
    	if (STEmpty(&obj->popst)) {
    		while (!STEmpty(&obj->pushst)) {
    			STPush(&obj->popst, STTop(&obj->pushst));
    			STPop(&obj->pushst);
    		}
    	}
    	return STTop(&obj->popst);
    }
     
    bool myQueueEmpty(MyQueue* obj) {
    	return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
    }
     
    void myQueueFree(MyQueue* 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);
    */

复杂度分析

*  时间复杂度：push和empty为O(1)，pop和peek为均摊O(1)。对于每个元素，至多入栈和出栈各两次，故均摊复杂度为O(1)。
 *  空间复杂度：O(n)。其中n是操作总数。对于有n次push操作的情况，队列中会有n个元素，故空间复杂度为O(n)。

![a9b29b8482654533ae41edf11fc7ab6f.png][]

[be4144439b7a441ea35f801e9265613e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/993d2a08a0a945878e586ec5abe11442.png
[Link 1]: https://blog.csdn.net/m0_68662723
[LeetCode]: http://t.csdnimg.cn/j5fPj
[OJ]: https://leetcode.cn/problems/implement-queue-using-stacks/
[leetcode]: https://so.csdn.net/so/search?q=leetcode&spm=1001.2101.3001.7020
[a9b29b8482654533ae41edf11fc7ab6f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/11a2da028817498fa4fc5fc9537e92b1.png