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

如何在一个数组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
  }