算法导论—一个数组中实现两个栈

如何在一个数组A[1..n]中实现两个栈，使得当两个栈的元素个数之和不为n时，两者都不会发生上溢。

• 要求push和pop操作的运行时间为O(1)。

实现：

• 两个栈分别从数组的两端开始，向中间push元素，直到两个指针相遇。

  package main
  import "fmt"
  const maxSize = 10
  const (
    sLeft stackType = iota
    sRight
  )
  type stackType int
  type Stack struct {
    arr   [maxSize]int
    left  int
    right int
  }
  var stack = Stack{
    arr:   [maxSize]int{},
    left:  -1,
    right: maxSize,
  }
  func (s *Stack) Push(val int, stackType stackType) bool {
    if s.IsFull() {
        return false
    }
    if stackType == sLeft {
        s.arr[s.left+1] = val
        s.left++
    } else {
        s.arr[s.right-1] = val
        s.right--
    }
    return true
  }
  func (s *Stack) Pop(stackType stackType) (val int, exist bool) {
    if stackType == sLeft {
        if s.left > -1 {
            val = s.arr[s.left]
            exist = true
            s.left--
        }
    } else {
        if s.right < maxSize {
            val = s.arr[s.right]
            exist = true
            s.right++
        }
    }
    return
  }
  // 两栈都为空
  func (s *Stack) IsEmpty() bool {
    if s.right == maxSize && s.left == -1 {
        return true
    }
    return false
  }
  func (s *Stack) IsFull() bool {
    if s.right-s.left == 1 {
        return true
    }
    return false
  }