使用棧實現隊列的下列操作：

• push(x) -- 將一個元素放入隊列的尾部。
• pop() -- 從隊列首部移除元素。
• peek() -- 返回隊列首部的元素。
• empty() -- 返回隊列是否為空。

MyQueue queue = new MyQueue();queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false

說明：

• 你只能使用標準的棧操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊列）來模擬一個棧，只要是標準的棧操作即可。
• 假設所有操作都是有效的 （例如，一個空的隊列不會調用 pop 或者 peek 操作）。

棧的思想是先進后出，那我們怎么實現利用棧來實現先進先出的隊列呢？

我們先來看張圖

進入隊列的順序為1》2》3，那我們就把這三個元素放進input棧中，再把input棧中的元素放進output棧里，那么我們可以看見，我們從output讀取的數據就是1》2》3了

那么我們一個一個方法來看：

push：對于push方法，我們只需要把元素放進input棧中即可

pop：對于pop方法，我們要從output棧中獲取棧頂元素，如果output棧中為空，那么我們就要從input棧中把元素都放進output棧中，再從output棧中取出棧頂元素即可，如果兩個棧都是空的，那就啥事都不干

peek：對于peek方法，與pop方法基本是一樣，只是讀取而已，不用去除元素

empty：只需要判斷input棧和output棧的容量合起來是不是不為空即可

核心代碼：

package maintype MyQueue struct {InputStack []int //輸入棧OutputStack []int //輸出棧 }/** Initialize your data structure here. */ func Constructor() MyQueue {queue := MyQueue{[]int{}, []int{}}return queue }/** Push element x to the back of queue. */ func (this *MyQueue) Push(x int) {this.InputStack = append(this.InputStack, x) }/** Removes the element from in front of queue and returns that element. */ func (this *MyQueue) Pop() int {//當輸出棧不為空的，那就直接取出輸出棧頂元素if len(this.OutputStack) != 0 {x := this.OutputStack[len(this.OutputStack)-1]this.OutputStack = this.OutputStack[:len(this.OutputStack)-1]return x}//如果輸出棧為空，但是輸入棧不為空，那就把輸入棧的元素放進輸出棧，并去除棧頂元素if len(this.InputStack) != 0 {for i := len(this.InputStack); i > 0; i-- {this.OutputStack = append(this.OutputStack, this.InputStack[i-1])this.InputStack = this.InputStack[:len(this.InputStack)-1]}x := this.OutputStack[len(this.OutputStack)-1]this.OutputStack = this.OutputStack[:len(this.OutputStack)-1]return x}return 0 //兩個棧都是空的 }/** Get the front element. */ func (this *MyQueue) Peek() int {if len(this.OutputStack) != 0 {return this.OutputStack[len(this.OutputStack)-1]}if len(this.InputStack) != 0 {for i := len(this.InputStack); i > 0; i-- {this.OutputStack = append(this.OutputStack, this.InputStack[i-1])this.InputStack = this.InputStack[:len(this.InputStack)-1]}return this.OutputStack[len(this.OutputStack)-1]}return 0 }/** Returns whether the queue is empty. */ func (this *MyQueue) Empty() bool {if len(this.InputStack)+len(this.OutputStack) == 0 {return true}return false }func main() {queue := Constructor()queue.Push(1)queue.Push(2)_ = queue.Peek()_ = queue.Pop()_ = queue.Empty() }

?

轉載于:https://www.cnblogs.com/TimLiuDream/p/10087768.html

總結

以上是生活随笔為你收集整理的用栈来实现队列的golang实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。