A stack is an ordered data structure that follows the Last-In-First-Out (LIFO) principle. Stacks are most easily implemented using the Go programming language.

Table of Contents

Concept of Stack

A stack is a memory in which values are stored and retrieved in “last in first out” manner. Data is added to stack using push operation and data is taken out of stack using pop operation.

stack

  • Initially the stack was empty. Then value 1 is added to stack using push(1) operator.
  • Similarly, push(2) and push(3)
  • Pop operation take the top of the stack. In Stack, data is added and deleted in “last in, first out” manner.
  • First pop() operation will take 3 out of the stack.
  • Similarly, other pop operation will take 2 then 1 out of the stack.
  • In the end, the stack is empty when all the elements are taken out of the stack.

System stack and Method Calls

When a method is called, the current execution is stopped and the control goes to the called method. After the called method exits / returns, the execution resumes from the point at which the execution was stopped.

To get the exact point at which execution should be resumed, the address of the next instruction is stored in the stack. When the method call completes, the address at the top of the stack is taken out.

Example:

func function2() {
	fmt.Println("fun2 line 1")
}

func function1() {
	fmt.Println("fun1 line 1")
	function2()
	fmt.Println("fun1 line 2")
}

func main() {
	fmt.Println("main line 1")
	function1()
	fmt.Println("main line 2")
}

Analysis:

  • Every program starts with main() function.
  • The first statement of main() will be executed. This will print “main line 1” as output.
  • function1() is called. Before control goes to function1() then next instruction that is address of next line is stored in the system stack.
  • Control goes to function1() method.
  • The first statement inside function1() is executed, this will print “fun1 line 1” to output.
  • function2() is called from function1(). Before control goes to function2() address of the next instruction that is address of next line is added to the system stack.
  • Control goes to function2() method.
  • “fun2 line 1” is printed to screen.
  • When function2() exits, control come back to function1(). Then the program reads the next instruction from the stack, and the next line is executed and print “fun1 line 2” to screen.
  • When function1() exits, control comes back to the main method. Then program reads the next instruction from the stack and execute it and finally “main line 2” is printed to screen.

Points to remember:

  • Methods are implemented using a stack.
  • When a method is called the address of the next instruction is pushed into the stack.
  • When a method is finished the address of the execution is taken out of the stack.

Implementation Stack

A stack will have below operations:

  • New(): create a new stack
  • Push(): add an element to the stack
  • Pop(): remove an element from the stack
  • IsEmpty() check if the stack is empty
  • Length() get the number of items in the stack
  • Peek() queries the top element of the stack
// Type is the placeholder type that indicates a generic value
// When is executed, variables of this type will be replaced with
// references to the specific type
//      var Item Type
type Type interface{}

// Item the type of the stack
type Item Type

// ItemStack the stack of Items
type ItemStack struct {
	items []Item
	lock  sync.RWMutex
}

// New creates a new stack
func (s *ItemStack) New() *ItemStack {
	s.items = []Item{}
	return s
}

// Push adds an item to the top of the stack
func (s *ItemStack) Push(t Item) {
	s.lock.Lock()
	s.items = append(s.items, t)
	s.lock.Unlock()
}

// Pop removes an item from the top of stack
func (s *ItemStack) Pop() *Item {
	s.lock.Lock()

	if len(s.items) == 0 {
		return nil
	}

	item := s.items[len(s.items)-1]
	s.items = s.items[0 : len(s.items)-1]
	s.lock.Unlock()

	return &item
}

// IsEmpty check the stack is empty
func (s *ItemStack) IsEmpty() bool {
	return len(s.items) == 0
}

// Length gets the length of the stack
func (s *ItemStack) Length() int {
	return len(s.items)
}

// Peek queries the top element of the stack
func (s *ItemStack) Peek() Item {
	s.lock.Lock()
	if len(s.items) == 0 {
		return nil
	}

	item := s.items[len(s.items)-1]
	s.lock.Unlock()

	return item
}

Conclusion

The stack is a linear and ordered type of data structure that follows the LIFO (Last In, First Out) rule for its data items.

As the stack plays a very important role in solving many of the computational problems that a programmer comes across, I highly recommend that people gain an understanding of the concept as well as how to employ it in their projects. I hope this article was a good introduction to the stack.

Reference