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

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

• 单栈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
  }
  // ----------------实现栈结束----------------