Implement Queue using Stacks

Implement the following operations of a queue using stacks.

• push(x) – Push element x to the back of queue.
• pop() – Removes the element from in front of queue.
• peek() – Get the front element.
• empty() – Return whether the queue is empty.

Notes:

• You must use only standard operations of a stack – which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

提示	解題應用
Stack	Quene

Default:

type MyQueue struct {
    
}


/** Initialize your data structure here. */
func Constructor() MyQueue {
    
}


/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int)  {
    
}


/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
    
}


/** Get the front element. */
func (this *MyQueue) Peek() int {
    
}


/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
    
}


/**
 * 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();
 */

解答思路:

這次要用stack來實作quene就更怪了，這邊我以兩個stack來實作，其中一個stack是負責push也就是插入元素，另一個stack則是負責pop把元素取出，為什麼要這樣處理呢?想想看stack在插入新的元素時，新的總是在最上面，這就和quene新的總是在最後面是一樣的道理，至於pop對quene來說是要拿出最前面最舊的元素，我們如果把stack一個個元素取出，然後再倒入另一個stack時就會變成最舊的元素在最上面了，此時就可以順利的對pop做處理，所以利用這種方式不管是要用LinkedList或Array來實作大致概念都相同。

程式碼解說:

這邊我以LinkedList的方式來實作stack，所以需要節點的結構，而實作出來的Quene最主要存了三項位置，分別是push元素用的stack，pop元素用的stack及一個flag用來指向最舊節點的位置，而由於stack在操作上並不需要頭節點來確保操作一致性，所以在建構function時就直接回傳即可

type Node struct {
	Val  int
	Next *Node
}
type MyQueue struct {
	StackPush *Node
	StackPop  *Node
	Flag      *Node
}
func Constructor() MyQueue {
	return MyQueue{}
}

如解答思路所寫，在進行push或pop任一動作時，要先確定另一個stack是否已將元素倒入，而這邊我們就要看pop對應的stack是否為空，如果沒有則先暫存目前stack開頭的位置，將另一個stack元素搬來原本的頂端並接回原本存在舊的元素，然後才重覆上述動作直到確定另一stack的元素已完全倒入，最後就可以放心的新增一個節點帶入其值，一樣將舊的元素接上最後再將其指為頂端節點，要注意的是因為flag要存的是最舊節點位置，也就是quene的第一個節點，所以只有其為nil時才需要指派第一個節點的位置給它

func (this *MyQueue) Push(x int) {
	var tmp *Node
	for this.StackPop != nil {
		tmp = this.StackPush
		this.StackPush = this.StackPop
		this.StackPop = this.StackPop.Next
		this.StackPush.Next = tmp
	}
	newNode := &Node{}
	newNode.Val = x
	if this.Flag == nil {
		this.Flag = newNode
	}
	newNode.Next = this.StackPush
	this.StackPush = newNode
}

如前述確認另一stack是否完全倒入，此時stack頂端為最舊的節點也就是quene的第一個節頭，將其值暫存後就直指將頂端節點的位置往下指，因為pop出去後就不需要在理會，這邊也可以自行多加一行去釋放該節點的記憶體，記得在pop出去後flag也要跟著往下指向目前最舊節點的位置，最後回傳先前所儲存的值

func (this *MyQueue) Pop() int {
	var tmp *Node
	for this.StackPush != nil {
		tmp = this.StackPop
		this.StackPop = this.StackPush
		this.StackPush = this.StackPush.Next
		this.StackPop.Next = tmp
	}
	popValue := this.StackPop.Val
	this.StackPop = this.StackPop.Next
	this.Flag = this.StackPop
	return popValue
}

因為flag在處理時始終指向最舊節點的位置，所以只要直接回傳其節點位置的值就好

func (this *MyQueue) Peek() int {
	return this.Flag.Val
}

如果要確認是否為空，最簡單的方式就是確認兩stack的頭節點存不存在，如果都不存在就表示quene沒有任何的元素回傳true

func (this *MyQueue) Empty() bool {
	if this.StackPush == nil && this.StackPop == nil {
		return true
	}
	return false
}

完整程式碼:

type Node struct {
	Val  int
	Next *Node
}
type MyQueue struct {
	StackPush *Node
	StackPop  *Node
	Flag      *Node
}
func Constructor() MyQueue {
	return MyQueue{}
}
func (this *MyQueue) Push(x int) {
	var tmp *Node
	for this.StackPop != nil {
		tmp = this.StackPush
		this.StackPush = this.StackPop
		this.StackPop = this.StackPop.Next
		this.StackPush.Next = tmp
	}
	newNode := &Node{}
	newNode.Val = x
	if this.Flag == nil {
		this.Flag = newNode
	}
	newNode.Next = this.StackPush
	this.StackPush = newNode
}
func (this *MyQueue) Pop() int {
	var tmp *Node
	for this.StackPush != nil {
		tmp = this.StackPop
		this.StackPop = this.StackPush
		this.StackPush = this.StackPush.Next
		this.StackPop.Next = tmp
	}
	popValue := this.StackPop.Val
	this.StackPop = this.StackPop.Next
	this.Flag = this.StackPop
	return popValue
}
func (this *MyQueue) Peek() int {
	return this.Flag.Val
}
func (this *MyQueue) Empty() bool {
	if this.StackPush == nil && this.StackPop == nil {
		return true
	}
	return false
}

總結:

若需要以stack的方式來實作quene，可以使用兩個stack來達到目標，在push時其一先是用來插入元素，當需要pop元素時，可以將原本push所用的stack倒入另一個stack之中，此時最舊的元素就會在最頂端，若是透過這種方式實作，不管之後是要做push或pop，在動作之前都要先確認其動作所對應的stack，是不是已經將另一個stack的元素完全倒入，若確認無誤才開始處理。