什么是栈
类似于链表，栈是一种简单的数据结构。在栈中，数据的取值顺序非常重要。栈有点像洗碟子然后堆碟子，最先洗的一定是最上面的碟子，然后洗干净后，放到碟子的最下面。第一个放好的碟子永远是最后一个被取用的。
栈是一种插入和删除总在一端的有序列表，最后插入的元素时总是第一个被删除的元素，这种特征也被称为 Last in First out(LIFO)或者 First in Last out(FILO)。
入栈的操作叫做 push ;
出栈的操作叫做 pop 。
往一个满栈里插入元素叫做 栈溢出；
栈的方法
push(e): Add e at the top of the (implicit) stackpop(): Remove and return the top element of the stackempty(): Return the Boolean value true just in case the stack is empty.top(): Return the top element of that stack without removing it.
栈的结构
type Stack interface { containers.Container Push(e interface{}) Pop() (interface{}, error) Top() (interface{}, error) }
栈的数组实现
import "errors"type ArrayStack struct { store []interface{}}func (s *ArrayStack) Size() int { return len(s.store)}func (s *ArrayStack) Empty() bool { return len(s.store) == 0}func (s *ArrayStack) Clear() { s.store = make([]interface{}, 0, 10)}func (s *ArrayStack) Push(e interface{}) { s.store = append(s.store, e)}func (s *ArrayStack) Pop() (interface{}, err) { if len(s.store) == 0 { return nil, errors.New("Pop: the stack cannot be empty") } result := s.store[len(s.store)-1] s.store = s.store[:len(s.store)-1] return result, nil}func (s *ArrayStack) Top() (interface{}, error) { if len(s.store) == 0 { return nil, errors.New("Top: stack cannot be empty") } return s.store[len(s.store)-1], nil}
栈的链表实现
import "errors"type ArrayStack struct { store []interface{}}func (s *ArrayStack) Size() int { return len(s.store)}func (s *ArrayStack) Empty() bool { return len(s.store) == 0}func (s *ArrayStack) Clear() { s.store = make([]interface{}, 0, 10)}func (s *ArrayStack) Push(e interface{}) { s.store = append(s.store, e)}func (s *ArrayStack) Pop() (interface{}, err) { if len(s.store) == 0 { return nil, errors.New("Pop: the stack cannot be empty") } result := s.store[len(s.store)-1] s.store = s.store[:len(s.store)-1] return result, nil}func (s *ArrayStack) Top() (interface{}, error) { if len(s.store) == 0 { return nil, errors.New("Top: stack cannot be empty") } return s.store[len(s.store)-1], nil}type LinkedStack struct{ topPtr *node count int}func (s *LinkedStack) Size() int { return s.count}func (s *LinkedStack) Empty() bool { return s.count == 0}func (s *LinkedStack) Clear() { s.count = 0 s.topPtr = nil}func (s *LinkedStack) Push(e interface{}) { s.topPtr = &node{e, s.topPtr} s.count++}func (s *LinkedStack) Pop() (interface{}, error) { if s.count == 0 { return nil, errors.New("Pop: the stack cannot be empty") } result := s.topPtr.item s.topPtr = s.topPtr.next s.count-- return result, nil}func (s *LinkedStack) Top() (interface{}, error) { if s.count == 0 { return nil, errors.New("Pop: the stack cannot be empty") } result s.topPtr.item, nil}
评论（0）