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

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

• 单栈push和pop的运行时间都为O(1)，所以需要考虑的就是两个栈之间切换所用时间。
• 最坏情况：在push和pop交替操作时，需要将一个栈中的数据转移到另一个栈中，转移所用时间为O(n)，n为当前栈中元素个数。
• 最好情况：用flag记录上一次是push还是pop，如果和当前操作一致，则直接操作对应的栈，时间复杂度为O(1)。

  package main
  
  const maxSize = 10
  
  type StackDeque struct {
  	pushStack *Stack
  	popStack  *Stack
  	flag      bool // true in push，false in pop
  }
  
  func (s *StackDeque) exchange(from, to *Stack) {
  	to.Clean()
  	for true {
  		if v, ok := from.Pop(); ok {
  			to.Push(v)
  		} else {
  			break
  		}
  	}
  	s.flag = !s.flag
  }
  
  func (s *StackDeque) Push(val int) bool {
  	if !s.flag { // 当前在pop栈
  		s.exchange(s.popStack, s.pushStack)
  	}
  	return s.pushStack.Push(val)
  }
  
  func (s *StackDeque) Pop() (int, bool) {
  	if s.flag {
  		s.exchange(s.pushStack, s.popStack)
  	}
  	return s.popStack.Pop()
  }
  
  // ----------------实现栈开始----------------
  type Stack struct {
  	arr  [maxSize]int
  	size int
  }
  
  func (s *Stack) isFull() bool {
  	if s.size == maxSize {
  		return true
  	}
  	return false
  }
  
  func (s *Stack) isEmpty() bool {
  	if s.size == 0 {
  		return true
  	}
  	return false
  }
  
  func (s *Stack) Push(val int) bool {
  	if s.isFull() {
  		return false
  	}
  	s.arr[s.size] = val
  	s.size++
  	return true
  }
  
  func (s *Stack) Pop() (int, bool) {
  	if s.isEmpty() {
  		return 0, false
  	}
  	val := s.arr[s.size-1]
  	s.size--
  	return val, true
  }
  
  func (s *Stack) Clean() {
  	s.size = 0
  }
  
  // ----------------实现栈结束----------------