兩個隊列實(shí)現(xiàn)一個棧
思路:兩個隊列實(shí)現(xiàn)一個棧,使用了隊列交換的思想。
代碼如下:
type MyStack struct {
queue1, queue2 []int
}
//構(gòu)造函數(shù)
func Constructor() (s MyStack) {
return
}
func (s *MyStack) Push(x int) {
s.queue2 = append(s.queue2, x)
for len(s.queue1) > 0 {
s.queue2 = append(s.queue2, s.queue1[0])
s.queue1 = s.queue1[1:]
}
s.queue1, s.queue2 = s.queue2, s.queue1
}
func (s *MyStack) Pop() int {
v := s.queue1[0]
s.queue1 = s.queue1[1:]
return v
}
func (s *MyStack) Top() int {
return s.queue1[0]
}
func (s *MyStack) Empty() bool {
return len(s.queue1) == 0
}
先將元素入對到 queue2,此時 queue1 為0,交換 queue2 和 queue1。此時 queue2 為0,queue1 中有1個元素。
再執(zhí)行push操作時,len(queue1) > 0,此時再把 queue1 中的元素插入queue2 的尾部,然后將 queue2 和 queue1 進(jìn)行交換。
此時相當(dāng)于,插入 queue2 的兩個元素的位置發(fā)生了交換并保存在 queue1中。最后將 queue1 中的元素出隊,這樣就可以保證后插入的元素先出。
不斷執(zhí)行 push 操作就行。
一個隊列實(shí)現(xiàn)一個棧
思路:使用一個隊列時,將當(dāng)前插入元素前面的所有元素,先出隊再入隊即可。
代碼如下:
type MyStack struct {
queue []int
}
func Constructor() (s MyStack) {
return
}
func (s *MyStack) Push(x int) {
n := len(s.queue)
s.queue = append(s.queue, x)
for ; n > 0; n-- {
s.queue = append(s.queue, s.queue[0])
s.queue = s.queue[1:]
}
}
func (s *MyStack) Pop() int {
v := s.queue[0]
s.queue = s.queue[1:]
return v
}
func (s *MyStack) Top() int {
return s.queue[0]
}
func (s *MyStack) Empty() bool {
return len(s.queue) == 0
}
每次執(zhí)行 push 操作,如果queue存在元素,則將新插入元素前的所有元素出隊,然后依次進(jìn)隊。這樣新插入的元素就在隊首了。
-
計算機(jī)
+關(guān)注
關(guān)注
19文章
7360瀏覽量
87633 -
數(shù)據(jù)結(jié)構(gòu)
+關(guān)注
關(guān)注
3文章
569瀏覽量
40072 -
隊列
+關(guān)注
關(guān)注
1文章
46瀏覽量
10882
發(fā)布評論請先 登錄
相關(guān)推薦
評論