数据结构实现相关
2022/1/10 6:07:33
本文主要是介绍数据结构实现相关,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
232. Implement Queue using Stacks EasyImplement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push
, peek
, pop
, and empty
).
Implement the MyQueue
class:
void push(int x)
Pushes element x to the back of the queue.int pop()
Removes the element from the front of the queue and returns it.int peek()
Returns the element at the front of the queue.boolean empty()
Returnstrue
if the queue is empty,false
otherwise.
Notes:
- You must use only standard operations of a stack, which means only
push to top
,peek/pop from top
,size
, andis empty
operations are valid. - Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.
Example 1:
Input ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] Output [null, null, null, 1, 1, false] Explanation 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
Constraints:
1 <= x <= 9
- At most
100
calls will be made topush
,pop
,peek
, andempty
. - All the calls to
pop
andpeek
are valid.
Follow-up: Can you implement the queue such that each operation is amortized O(1)
time complexity? In other words, performing n
operations will take overall O(n)
time even if one of those operations may take longer.
解法1: push之前确保元素都在stack1(stack2是空的), pop/peek之前确保元素都在stack2(stack1是空的)
时间复杂度 peek/pop/push 均为O(N)
class MyQueue { private Stack<Integer> stack1; private Stack<Integer> stack2; public MyQueue() { stack1 = new Stack(); stack2 = new Stack(); } public void push(int x) { while(!stack2.isEmpty()) stack1.push(stack2.pop()); stack1.push(x); } public int pop() { while(!stack1.isEmpty()) stack2.push(stack1.pop()); return stack2.pop(); } public int peek() { while(!stack1.isEmpty()) stack2.push(stack1.pop()); return stack2.peek(); } public boolean empty() { return stack1.isEmpty() && stack2.isEmpty(); } } /** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */
优化后解法:push总是放到stack1,pop的时候先判定stack2是不是空的,如果是空的情况下才把stack1的元素都挪过来
时间复杂度 push为O(1), pop/peek amertized O(1)
class MyQueue { private Stack<Integer> stack1; private Stack<Integer> stack2; public MyQueue() { stack1 = new Stack(); stack2 = new Stack(); } public void push(int x) { stack1.push(x); } public int pop() { peek(); return stack2.pop(); } public int peek() { if(stack2.isEmpty()){ while(!stack1.isEmpty()) stack2.push(stack1.pop()); } return stack2.peek(); } public boolean empty() { return stack1.isEmpty() && stack2.isEmpty(); } } /** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */
这篇关于数据结构实现相关的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?