Data structure: Stack

Stack, last in first out (advanced last out), one of the commonly used data structures. There are two implementations: sequential storage and chained storage. Depth-first traversal can be simulated based on this data structure.

Brush questions are often used.

Implementation one, based on the GO standard librarycontainer/list

import "container/list"

type Stack struct {
	l *list.List
}

func NewStack(a) *Stack {
	return &Stack{
		l: list.New(),
	}
}

func (o *Stack) Push(v interface{}) {
	o.l.PushBack(v)
}

func (o *Stack) Peek(a) interface{} {
	if o.IsEmpty() {
		panic("Stack is empty")}return o.l.Back().Value
}

func (o *Stack) Pop(a) {
	if o.IsEmpty() {
		panic("Stack is empty")
	}
	o.l.Remove(o.l.Back())
}

func (o *Stack) IsEmpty(a) bool {
	return o.l.Len() == 0
}

func (o *Stack) Len(a) int {
	return o.l.Len()
}
Copy the code

Implementation two, based on slice

type Stack struct {
	data []interface{}}func NewStack(a) *Stack {
	return &Stack{}
}

func (o *Stack) Push(v interface{}) {
	o.data = append(o.data, v)
}

func (o *Stack) Peek(a) interface{} {
	if o.IsEmpty() {
		panic("Stack is empty")}return o.data[len(o.data)- 1]}func (o *Stack) Pop(a) {
	if o.IsEmpty() {
		panic("Stack is empty")
	}
	o.data = o.data[:len(o.data)- 1]}func (o *Stack) Len(a) int {
	return len(o.data)
}

func (o *Stack) IsEmpty(a) bool {
	return len(o.data) == 0
}
Copy the code

Implementation three, based onSingly linked lists

// Single linked list package
import "algo/internal/singlylinkedlist"

type Stack struct {
	list *singlylinkedlist.SinglyLinkedList
	size int
}

func NewStack(a) *Stack {
	return &Stack{
		list: &singlylinkedlist.SinglyLinkedList{},
	}
}

func (o *Stack) Len(a) int {
	return o.size
}

func (o *Stack) IsEmpty(a) bool {
	return o.size == 0
}

func (o *Stack) Push(v interface{}) {
	o.list.AddToHead(v)
	o.size++
}

func (o *Stack) Peek(a) interface{} {
	if o.IsEmpty() {
		panic("Stack is empty")}return o.list.Head().V
}

func (o *Stack) Pop(a) {
	if o.IsEmpty() {
		panic("Stack is empty")
	}
	o.list.RemoveHead()
	o.size--
}
Copy the code

Test code:

package main

import "fmt"

func main(a) {
	sk := NewStack()
	for i := 0; i < 9; i++ {
		sk.Push(i * 2)}for! sk.IsEmpty() { fmt.Println(sk.Peek().(int), sk.Len())
		sk.Pop()
	}
}
Copy the code