栈与队列

—— by golang

栈与队列是两种基础的动态集合，它们都满足基本的存取要求，但在取序上表现不一样，栈先入后出（LIFO），队列先入先出（FIFO）；

栈（LIFO）

通过一个固定大小的数组（或slice）和一个游标（标示栈顶）来实现一个固定大小的栈；

package algo

import "errors"

func NewStack(n int) *Stack {
    return &Stack{
        elems: make([]interface{}, n),
    }
}

type Stack struct {
    elems []interface{}
    top   int
}

func (s *Stack) Push(e interface{}) error {
    if s.top >= len(s.elems) {
        return errors.New("stack overflow")
    }

    s.elems[s.top] = e
    s.top++
    return nil
}

func (s *Stack) Pop() (interface{}, error) {
    if s.top <= 0 {
        return nil, errors.New("stack underflow")
    }

    s.top--
    return s.elems[s.top], nil
}

func (s *Stack) Empty() bool {
    return s.top <= 0
}

队列（FIFO）

队列的实现有不同方式（有数组实现、也有链表实现），这里通过数组实现一个典型的循环队列；

package algo

import (
    "errors"
)

func NewQueue(n int) *Queue {
    return &Queue{
        elems: make([]interface{}, n),
        head:  -1,
        tail:  -1,
    }
}

type Queue struct {
    elems      []interface{}
    head, tail int
}

func (q *Queue) Push(e interface{}) {

    q.tail++
    if q.tail >= len(q.elems) {
        q.tail = 0
    }
    q.elems[q.tail] = e

    if q.head < 0 {
        q.head = q.tail
    } else if q.head == q.tail {
        q.head++
        if q.head >= len(q.elems) {
            q.head = 0
        }
    }
}

func (q *Queue) Pop() (interface{}, error) {
    if q.head < 0 {
        return nil, errors.New("queue underflow")
    }

    e := q.elems[q.head]
    if q.head == q.tail {
        q.head = -1
    } else {
        q.head++
        if q.head >= len(q.elems) {
            q.head = 0
        }
    }
    return e, nil
}

func (q *Queue) Empty() bool {
    return q.head == q.tail
}