type Stack []interface {}

func (stack Stack) Len() int {
    return len(stack)
}

func (stack Stack) IsEmpty() bool  {
    return len(stack) == 0
}

func (stack Stack) Cap() int {
    return cap(stack)
}

func (stack *Stack) Push(value interface{})  {
    *stack = append(*stack, value)
}

func (stack Stack) Top() interface{}  {
    if len(stack) == 0 {
        return nil
    }
    return stack[len(stack) - 1]
}

func (stack *Stack) Pop() interface{}  {
    refStack := *stack
    if len(refStack) == 0 {
        return nil
    }
    value := refStack[len(refStack) - 1]
    *stack = refStack[:len(refStack) - 1]
    return value
}

type MyQueue struct {
    i,o []int
}


/** Initialize your data structure here. */
func Constructor() MyQueue {
    return MyQueue{}
}


/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int)  {
    this.i = append(this.i, x)
}


/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
    ret := this.Peek()
    this.o = this.o[:len(this.o) - 1]
    return ret
}


/** Get the front element. */
func (this *MyQueue) Peek() int {
    if len(this.o) == 0 {
        for len(this.i) > 0 {
            this.o = append(this.o, this.i[len(this.i) - 1])
            this.i = this.i[:len(this.i) - 1]
        }
    }
    return this.o[len(this.o) - 1]
}


/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
    return len(this.o) == 0 && len(this.i) == 0
}


/**
 * Your MyQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Peek();
 * param_4 := obj.Empty();
 */

type MyStack struct {
    i, o []int
}


/** Initialize your data structure here. */
func Constructor() MyStack {
    return MyStack{}
}


/** Push element x onto stack. */
func (this *MyStack) Push(x int)  {
    this.i = append(this.i, x)
    // fmt.Printf("PUSH %v, %v\n", this.i, this.o)
}


/** Removes the element on top of the stack and returns that element. */
func (this *MyStack) Pop() int {
    ret := 0
    for len(this.i) > 0 {
        if len(this.i) == 1 {
            ret = this.i[0]
            this.i = []int{}
            break
        }
        this.o = append(this.o, this.i[0])
        this.i = this.i[1:]
    }
    for len(this.o) > 0 {
        this.i = append(this.i, this.o[0])
        this.o = this.o[1:]
    }
    // fmt.Printf("POP %v, %v\n", this.i, this.o)
    return ret
}


/** Get the top element. */
func (this *MyStack) Top() int {
    ret := 0
    for len(this.i) > 0 {
        if len(this.i) == 1 {
            ret = this.i[0]
        }
        this.o = append(this.o, this.i[0])
        this.i = this.i[1:]
    }
    for len(this.o) > 0 {
        this.i = append(this.i, this.o[0])
        this.o = this.o[1:]
    }
    // fmt.Printf("TOP %v, %v\n", this.i, this.o)
    return ret
}


/** Returns whether the stack is empty. */
func (this *MyStack) Empty() bool {
    return len(this.i) == 0
}


/**
 * Your MyStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.Empty();
 */

func isValid(s string) bool {
    stack := []int{}
    for _, c := range s {
        if c == '(' || c == '{' || c == '[' {
            stack = append(stack, int(c))
            continue
        }
        if len(stack) == 0 {
            return false
        }
        t := stack[len(stack) - 1]
        if (c == ')' && t == '(' ||
            c == '}' && t == '{' ||
            c == ']' && t == '[') {
            stack = stack[:len(stack) - 1]
            continue
        }
        return false
    }
    if len(stack) > 0 {
        return false
    }
    return true
}

func removeDuplicates(S string) string {
    stack := []byte{}
    for i := range S {
        if len(stack) > 0 && stack[len(stack) - 1] == S[i] {
            stack = stack[:len(stack) - 1]
        } else {
            stack = append(stack, S[i])
        } 
    }
    return string(stack)
}

func evalRPN(tokens []string) int {
  var stack []int
  for _, val := range tokens {
    size := len(stack)
    switch val {
    case "+":
      stack = append(stack[:size-2], stack[size-2]+stack[size-1])
    case "-":
      stack = append(stack[:size-2], stack[size-2]-stack[size-1])
    case "*":
      stack = append(stack[:size-2], stack[size-2]*stack[size-1])
    case "/":
      stack = append(stack[:size-2], stack[size-2]/stack[size-1])
    default:
      val, _ := strconv.Atoi(val)
      stack = append(stack, val)
    }
  }
  return stack[0]
}