232. 用棧實(shí)現(xiàn)隊(duì)列
使用棧實(shí)現(xiàn)隊(duì)列的下列操作：
- push(x) -- 將一個(gè)元素放入隊(duì)列的尾部址儒。
- pop() -- 從隊(duì)列首部移除元素术奖。
- peek() -- 返回隊(duì)列首部的元素嗤军。
- empty() -- 返回隊(duì)列是否為空。
示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
說(shuō)明:
- 你只能使用標(biāo)準(zhǔn)的棧操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的羊异。
- 你所使用的語(yǔ)言也許不支持棧砖顷。你可以使用 list 或者 deque（雙端隊(duì)列）來(lái)模擬一個(gè)棧喷众，只要是標(biāo)準(zhǔn)的棧操作即可浓恶。
- 假設(shè)所有操作都是有效的 （例如奋救，一個(gè)空的隊(duì)列不會(huì)調(diào)用 pop 或者 peek 操作）岭参。
解題思路
- 在Golang中,本身未提供棧數(shù)據(jù)結(jié)構(gòu),先基于數(shù)組實(shí)現(xiàn)棧結(jié)構(gòu)
- 優(yōu)化: 入隊(duì)時(shí),將元素壓入s1,出隊(duì)時(shí)，判斷s2是否為空尝艘，如不為空演侯，則直接彈出頂元素；如為空背亥，則將s1的元素逐個(gè)“倒入”s2秒际，把最后一個(gè)元素彈出并出隊(duì)
- 避免反復(fù)"倒"棧,僅在需要時(shí)才"倒"一次
- 細(xì)節(jié): 考慮沒(méi)有元素可供出隊(duì)時(shí)的處理（2個(gè)棧都為空的時(shí)候悬赏，出隊(duì)操作一定會(huì)引起異常）
代碼實(shí)現(xiàn)
/**
* Your MyQueue object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(x);
* param_2 := obj.Pop();
* param_3 := obj.Peek();
* param_4 := obj.Empty();
*/
// MyQueue defines Stack1 queue by two stacks
type MyQueue struct {
Stack1, Stack2 *stack
}
// Constructor Initialize your data structure here.
func Constructor() MyQueue {
return MyQueue{
Stack1: newStack(),
Stack2: newStack(),
}
}
// Push element x to the back of queue.
func (queue *MyQueue) Push(x int) {
queue.Stack1.push(x)
}
// Pop Removes the element from in front of queue and returns that element.
func (queue *MyQueue) Pop() int {
if queue.Stack2.isEmpty() {
//優(yōu)化: 棧a中留一個(gè)元素供pop,可以少一次操作
for queue.Stack1.len() > 1 {
queue.Stack2.push(queue.Stack1.pop())
}
return queue.Stack1.pop()
}
return queue.Stack2.pop()
}
// Peek Get the front element.
func (queue *MyQueue) Peek() int {
if queue.Stack2.isEmpty() {
if queue.Stack1.isEmpty() {
return -1
}
return queue.Stack1.nums[0]
}
return queue.Stack2.nums[queue.Stack2.len()-1]
}
// Empty Returns whether the queue is empty.
func (queue *MyQueue) Empty() bool {
return queue.Stack1.isEmpty() && queue.Stack2.isEmpty()
}
// stack defines Stack1 stack
type stack struct {
nums []int
}
// newStack creates a empty stack
func newStack() *stack {
return &stack{
nums: []int{},
}
}
func (s *stack) push(n int) {
s.nums = append(s.nums, n)
}
func (s *stack) pop() int {
if s.isEmpty() {
return -1
}
res := s.nums[len(s.nums)-1]
s.nums = s.nums[:len(s.nums)-1]
return res
}
func (s *stack) len() int {
return len(s.nums)
}
func (s *stack) isEmpty() bool {
return s.len() == 0
}
GitHub
- 源碼在這里
- 項(xiàng)目中會(huì)提供各種數(shù)據(jù)結(jié)構(gòu)及算法的Golang實(shí)現(xiàn),以及 LeetCode 解法
