算法导论-两个队列实现栈

用两个队列实现栈，并分析相关栈操作的运行时间。

思路同：两个栈实现队列

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
}