用两个队列实现栈，并分析相关栈操作的运行时间。
思路同：两个栈实现队列
type DequeStack struct {
pushDeque *Deque
popDeque *Deque
flag bool // true in push, false in pop
}
func (d *DequeStack) exchange(from, to *Deque) {
to.Clean()
for true {
if v, ok := from.Pop(); ok {
to.Push(v)
} else {
break
}
}
d.flag=!d.flag
}
func (d *DequeStack) Push(val int) bool {
if !d.flag{
d.exchange(d.popDeque, d.pushDeque)
}
return d.pushDeque.Push(val)
}
func (d *DequeStack) Pop() (int, bool){
if d.flag{
d.exchange(d.pushDeque, d.popDeque)
}
return d.popDeque.Pop()
}
// 队列实现
type Deque struct {
arr [maxSize]int
head int
tail int
size int
}
func (d *Deque) next(position int) int {
if position == len(d.arr)-1 {
return 0
}
return position + 1
}
func (d *Deque) isFull() bool {
return d.size == len(d.arr)
}
func (d *Deque) isEmpty() bool {
return d.size == 0
}
func (d *Deque) Push(val int) bool {
if d.isFull() {
return false
}
d.arr[d.tail] = val
d.tail = d.next(d.tail)
d.size++
return true
}
func (d *Deque) Pop() (int, bool) {
if d.isEmpty() {
return 0, false
}
val := d.arr[d.head]
d.head = d.next(d.head)
d.size--
return val, true
}
func (d *Deque) Clean() {
d.head = 0
d.tail = 0
d.size = 0
}
