“This is the 23rd day of my participation in the First Challenge 2022. For details: First Challenge 2022”

What is a stack

Like a linked list, a stack is a simple data structure. In the stack, the order in which data is evaluated is very important.

Like a linked list, a stack is a simple data structure. In the stack, the order in which data is evaluated is very important. A stack is a bit like washing dishes and piling them up. The top plate must be washed first, and then the bottom of the plate after washing. The first dish placed is always the last to be taken.

A stack is an ordered list of inserts and deletions at one end, and the Last element to be inserted is always the First element to be removed. This feature is also known as Last in First out(LIFO) or First in Last out(FILO).

  • The operation of pushing is called push;

  • The operation to remove the stack is called pop.

  • Adding elements to a full stack is called stack overflow;

Stack life example

Stacks also have many real life examples. Consider a simple example of boards stacked on top of each other in a canteen. A stack is a bit like washing dishes and piling them up. The top plate must be washed first, and then the bottom of the plate after washing. The first dish placed is always the last to be taken. You can simply see that it follows the LIFO/FILO principle.

The operation of the stack

A stack is an ordered list of inserts and deletions at one end, and the Last element to be inserted is always the First element to be removed. This feature is also known as Last in First out(LIFO) or First in Last out(FILO).

The operation of pushing is called push; The animation is shown below:

The operation is called pop, and the animation is shown as follows:

Adding elements to a full stack is called stack overflow;

The method of stack

push(e): Add e at the top of the (implicit) stack
pop(): Remove and return the top element of the stack

empty(): Return the Boolean value true just in case the stack is empty.
top(): Return the top element of that stack without removing it.
Copy the code

The structure of the stack

type Stack interface {
    containers.Container
    Push(e interface{})
    Pop() (interface{}, error)
    Top() (interface{}, error)        
}
Copy the code

Stack array implementation

package main

import (
    "errors"
    "fmt"
)

// ArrayStack is an implementation of a stack.
type ArrayStack struct {
    elements []interface{}}// New creates a new array stack.
func New(a) *ArrayStack {
    return &ArrayStack{}
}

// Size returns the number of elements in the stack.
func (s *ArrayStack) Size(a) int {
    return len(s.elements)
}

// Empty returns true or false whether the stack has zero elements or not.
func (s *ArrayStack) Empty(a) bool {
    return len(s.elements) == 0
}

// Clear clears the stack.
func (s *ArrayStack) Clear(a) {
    s.elements = make([]interface{}, 0.10)}// Push adds an element to the stack.
func (s *ArrayStack) Push(e interface{}) {
    s.elements = append(s.elements, e)
}

// Pop fetches the top element of the stack and removes it.
func (s *ArrayStack) Pop(a) (interface{}, error) {
    if s.Empty() {
        return nil, errors.New("Pop: the stack cannot be empty")
    }
    result := s.elements[len(s.elements)- 1]
    s.elements = s.elements[:len(s.elements)- 1]
    return result, nil
}

// Top returns the top of element from the stack, but does not remove it.
func (s *ArrayStack) Top(a) (interface{}, error) {
    if s.Empty() {
        return nil, errors.New("Top: stack cannot be empty")}return s.elements[len(s.elements)- 1].nil
}

func main(a) {

    s := New()
    s.Push(1)
    s.Push(2)
    s.Push(3)

    fmt.Println(s)
    fmt.Println(s.Pop())
    fmt.Println(s)
    fmt.Println(s.Top())
    fmt.Println("Stack length:", s.Size())
    fmt.Println("Is the stack empty?", s.Empty())

    s.Clear()
    if s.Empty() {
        fmt.Println("Stack empty")}}Copy the code

Running results:

&{[1 2 3]} 3 <nil> &{[1 2]} 2 <nil> Length of stack: 2 Whether stack is empty: false Stack is emptyCopy the code

Stack of linked list implementation

package linkedliststack

import "errors"

type LinkedStack struct{
    topPtr *node
    count int
}

func (s *LinkedStack) Size(a) int {
    return s.count
}

func (s *LinkedStack) Empty(a) bool {
    return s.count == 0
}

func (s *LinkedStack) Clear(a) {
    s.count = 0
    s.topPtr = nil
}

func (s *LinkedStack) Push(e interface{}) {
    s.topPtr = &node{e, s.topPtr}
    s.count++
}

func (s *LinkedStack) Pop(a) (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(a) (interface{}, error)  {
    if s.count == 0 {
        return nil, errors.New("Pop: the stack cannot be empty")
    }
    result s.topPtr.item, nil
}
Copy the code

The reader can try to write the main function to verify the stack of linked list implementation.

conclusion

Using the data structure of stack, we can conveniently realize some more practical functions: for example, the browser before and after the jump, expression evaluation, parenthesis matching, but also to achieve the binary tree order traversal, etc..

  • Array visualization
  • Linked list implementation visualization