Implement Stack using Queues

2017-01-29

Implement Stack using Queues

Implement the following operations of a stack using queues.

push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
empty() – Return whether the stack is empty.

Note:

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

提示	解題應用
Stack	Quene

Default:

type MyStack struct {
    
}
/** Initialize your data structure here. */
func Constructor() MyStack {
    
}
/** Push element x onto stack. */
func (this *MyStack) Push(x int)  {
    
}
/** Removes the element on top of the stack and returns that element. */
func (this *MyStack) Pop() int {
    
}
/** Get the top element. */
func (this *MyStack) Top() int {
    
}
/** Returns whether the stack is empty. */
func (this *MyStack) Empty() bool {
    
}
/**
 * Your MyStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.Empty();
 */

解答思路:

這題要你設計一個stack，不過說穿了不盡然是個stack，而是要用quene的方式去模擬，要利用隊列的特性來實作stack也就是先進先出，這邊我仍採用linkedlist方式來實作，最主要關注在物件的兩個function:push與pop，以原本的stack設計來說，push新的節點都是在最頂端，而舊的則是接在後頭，但在隊列實作則是新的節點一直在後頭，這還沒什麼問題，我們只要以一個flag一直指向最新新增的節點位置即可，但是pop就有點麻煩了，原本只要將頂端的節點拿掉，變成隊列後就要一個個遍歷，並將出隊列的節點再塞回隊列之中，直到找到要取出的節點為止再做嫁接。

程式碼解說:

初始化一LinkedList需要自行訂義節點，包含值與下一個目標位置，而MyStack主要用來存放頭節點的位置以判斷是否stack為空(只有該頭節點存在)，而flag則是指向最新的節點位置，方便做節點插入與得知對stack來說其為頂端的節點，最後在建構的function就是初始化頭節點並指派其為Header與Flag的值

type Node struct {
	Val  int
	Next *Node
}
type MyStack struct {
	Header *Node
	Flag   *Node
}
func Constructor() MyStack {
	newNode := &Node{}
	newNode.Next = newNode
	return MyStack{newNode, newNode}
}

與原本stack節點都是從頭插入不同，在隊列中都是從最後頭塞入節點，而Flag就將舊節點的下一個指向新節點並將Flag也跟著移到新節點的位置，而在隊列中最新的節點在初始化時，我們將其下一個目標位置指回了頭節點，以方便遍歷時判斷是否還有其它節點存在(沒有的話就只有頭節點)

func (this *MyStack) Push(x int) {
	newNode := &Node{x, this.Header}
	this.Flag.Next = newNode
	this.Flag = newNode
}

一開始先將最新節點也就是要Pop出去的節點位置給儲存下來，接著開始從隊列開頭一個個遍歷(頭節點除外)，如果為我們要Pop的節點，就將頭節點嫁接到目標節點的下一個節點並回傳其值，也可以在這邊多加一行去釋放目標節點的記憶體空間，至於那些從隊列拿出但不是目標的節點，就將其塞回隊列尾端，同時將Flag做更新，最後與push時相同，將當前最新節點的下一個目標位置指回了頭節點，以方便遍歷時判斷是否還有其它節點存在，至於如果有任何的例外狀況，像是stack沒有任何值卻要pop，這時就回傳一任意值(這邊以0做為範例)

func (this *MyStack) Pop() int {
	popNode := this.Flag
	head := this.Header.Next
	for head != this.Header {
		if head == popNode {
			this.Header.Next = head.Next
			return head.Val
		}
		this.Flag.Next = head
		this.Flag = head
		head = head.Next
		this.Flag.Next = this.Header
	}
	return 0
}

因為Flag始終指向最新節點的位置，所以這時就只要回傳Flag位置節點的值即可

1
2
3

func (this *MyStack) Top() int {
	return this.Flag.Val
}

如果stack之中沒有其它的節點存在，表示quene之中只存在頭節點，而這時只要判斷是否頭節點的下一個目標節點仍為頭節點，如果是就回傳true，否則就回傳false

func (this *MyStack) Empty() bool {
	if this.Header.Next == this.Header {
		return true
	}
	return false
}

完整程式碼:

type Node struct {
	Val  int
	Next *Node
}
type MyStack struct {
	Header *Node
	Flag   *Node
}
func Constructor() MyStack {
	newNode := &Node{}
	newNode.Next = newNode
	return MyStack{newNode, newNode}
}
func (this *MyStack) Push(x int) {
	newNode := &Node{x, this.Header}
	this.Flag.Next = newNode
	this.Flag = newNode
}
func (this *MyStack) Pop() int {
	popNode := this.Flag
	head := this.Header.Next
	for head != this.Header {
		if head == popNode {
			this.Header.Next = head.Next
			return head.Val
		}
		this.Flag.Next = head
		this.Flag = head
		head = head.Next
		this.Flag.Next = this.Header
	}
	return 0
}
func (this *MyStack) Top() int {
	return this.Flag.Val
}
func (this *MyStack) Empty() bool {
	if this.Header.Next == this.Header {
		return true
	}
	return false
}

總結:

設計一個stack要用quene的方式去模擬，最主要關注在物件的兩個function:push與pop。

Push: 以原本的stack設計來說，push新的節點都是在最頂端，而舊的則是接在後頭，但在隊列實作則是新的節點一直在後頭
Pop: 原本stack設計只要將頂端的節點拿掉，變成隊列後就要一個個遍歷，並將出隊列的節點再塞回隊列之中，直到找到要取出的節點為止再做嫁接

A log about a developer.

未分類

Implement Stack using Queues

Implement Stack using Queues

Default:

解答思路:

程式碼解說:

完整程式碼:

總結: