Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in Go

Key Operations of a Stack

Explore fundamental stack operations in this lesson to master how to add, remove, and inspect elements using Go. Understand the push, pop, peek, isEmpty, and isFull functions, their Go implementations, and analyze their time and space complexities. This lesson equips you to efficiently manage data structures following the LIFO principle with hands-on coding practice.

We'll cover the following...

With stack implementations using slices/arrays and linked lists established, the next step is to examine the fundamental operations for interacting with a stack. These operations define the stack’s behavior and how its data is manipulated.

A stack supports several core operations, but they all revolve around the LIFO (Last in, first out) principle. Before we can add or remove elements, we often need to check the current state of the stack. Let's begin with two essential utility operations.

The IsEmpty() operation

The IsEmpty() method checks whether the stack is empty. This is crucial before attempting to remove or view elements, as popping an empty stack would result in an error.

Example: Consider a stack that currently holds [88, 95, 72, 80, 91]. The top index points to position 4 (where 91 is stored). Calling IsEmpty() on this stack would return false because top is 4, not -1.

If we were to pop all five elements one by one, top would eventually become -1 again. At that point, calling IsEmpty() would return true.

Go implementation

In a fixed-capacity slice-backed stack, we check if top equals -1. Remember that we initialized top to -1 when creating an empty stack, so if it's still -1, no elements have been added.

Go (1.24.2)
package main
import "fmt"
type Stack struct {
	capacity int
	data []int
	top int
}
func NewStack(capacity int) *Stack {
	return &Stack{
		capacity: capacity,
		data: make([]int, capacity),
		top:-1,
	}
}
func (s *Stack) IsEmpty() bool {
	return s.top == -1
}
func main() {
	// Create a stack
	stack := NewStack(10)
	fmt.Println(" Is stack empty?", stack.IsEmpty()) // Output: true (stack is empty)
}

The IsFull() operation

The IsFull() operation checks whether the stack has reached its maximum capacity. This is only relevant for slice-backed stacks with a fixed size. Before pushing a new element, we should check if there’s space available.

Example: Consider a stack with capacity 5 that currently holds [88, 95, 72, 80, 91]. The top is 4, and the capacity is 5. As top equals capacity - 1, i.e., (5 - 1 = 4), the stack is full. Calling IsFull() would return true.

If we pop one element (91), top would become 3. Now top (3) is less than capacity - 1 (4), so calling IsFull() would return false.

Go implementation

In a fixed-capacity slice-backed stack, we check if top equals capacity - 1. Since slice and array indices start at 0, the last valid index is capacity - 1. If top has reached this position, the stack is full.

Go (1.24.2)
package main
import "fmt"
type Stack struct {
	capacity int
	data []int
	top int
}
func NewStack(capacity int) *Stack {
	return &Stack{
		capacity: capacity,
		data: make([]int, capacity),
		top: -1,
	}
}
func (s *Stack) IsEmpty() bool {
	return s.top == -1
}
func (s *Stack) IsFull() bool {
	return s.top == s.capacity-1
}
func main() {
	// Create a stack with capacity 5
	stack := NewStack(5)
	// Simulate a full stack with elements: [88, 95, 72, 80, 91]
	stack.top = 4 // top index is 4
	fmt.Println("Is stack full?", stack.IsFull()) // Output: true (stack is full)
	fmt.Println("Simulating popping one element from the stack")
	stack.top = 3 // top index is now 3
	fmt.Println("Is stack full?", stack.IsFull()) // Output: false (stack has space)
}

Note: For linked list-based stacks, IsFull() is typically not needed because they can grow dynamically until the system runs out of memory.

Push operation

The Push operation adds a new element to the top of the stack. This is how we insert data into the stack, and it always happens at one end, i.e., the top.

Before pushing an element into a fixed-capacity slice-backed stack, we must first check if the stack is full using IsFull(). If there's space available, we increment the top index and place the new element at that position.

Example: Let’s say we have a stack with capacity 10 that currently holds [88, 95, 72, 80], and we want to push the value 91 onto the stack. After the push, the stack contains [88, 95, 72, 80, 91] with top at index 4.

Go implementation

Here’s how we implement the Push operation step by step:

  1. We check if the stack is full by calling the IsFull() method. If it is full, we print an error message and return false because no further elements can be added to the stack.

  2. If the stack has capacity, increment top because we will place our new element at the top.

  3. Place the new element at the top.

Go (1.24.2)
package main
import "fmt"
type Stack struct {
	capacity int
	data []int
	top int
}
func NewStack(capacity int) *Stack {
	return &Stack{
		capacity: capacity,
		data: make([]int, capacity),
		top: -1,
	}
}
func (s *Stack) Push(value int) bool {
	// Check if stack is full
	if s.IsFull() {
		fmt.Println("Stack Overflow! Cannot push element.")
		return false
	}
	// Increment top and add the element
	s.top++
	s.data[s.top] = value
	return true
}
func (s *Stack) IsEmpty() bool {
	return s.top == -1
}
func (s *Stack) IsFull() bool {
	return s.top == s.capacity-1
}
func main() {
	// Create a stack with capacity 10
	stack := NewStack(10)
	// Push elements one by one
	stack.Push(88) // Stack: [88], top = 0
	stack.Push(95) // Stack: [88, 95], top = 1
	stack.Push(72) // Stack: [88, 95, 72], top = 2
	stack.Push(80) // Stack: [88, 95, 72, 80], top = 3
	stack.Push(91) // Stack: [88, 95, 72, 80, 91], top = 4
	fmt.Printf("Top index: %d\n", stack.top) // Output: Top index: 4
}

Pop operation

The Pop operation removes and returns the element at the top of the stack. This is how we retrieve data from the stack while also removing it from the structure.

Before popping, we must check if the stack is empty using IsEmpty(). If the stack has elements, we retrieve the element at the top index, then decrement top to reflect that the stack now has one fewer element.

Example: Consider a stack that currently contains [88, 95, 72, 80, 91], and we want to pop an element. After the pop, the stack contains [88, 95, 72, 80] with top at index 3. The value 91 is returned to the caller.

Go implementation

Here’s how we implement the Pop operation step by step:

  1. We check if the stack is empty by calling the IsEmpty() method. If it is empty, we print an error message and return 0, false because no elements can be removed from the stack. The false value tells the caller that the pop did not succeed.

  2. If the stack is not empty, we retrieve the value stored at its top index and store it in the variable value.

  3. After retrieving the top element, we decrement the top index to indicate that the top element has been removed.

  4. In the end, we return the removed value along with true.

Go (1.24.2)
package main
import "fmt"
type Stack struct {
	capacity int
	data []int
	top int
}
func NewStack(capacity int) *Stack {
	return &Stack{
		capacity: capacity,
		data: make([]int, capacity),
		top: -1,
	}
}
func (s *Stack) Pop() (int, bool) {
	// Check if stack is empty
	if s.IsEmpty() {
		fmt.Println("Stack Underflow! Cannot pop from empty stack.")
		return 0, false
	}
	// Get the top element
	value := s.data[s.top]
	// Decrement top
	s.top--
	return value, true
}
func (s *Stack) IsEmpty() bool {
	return s.top == -1
}
func (s *Stack) IsFull() bool {
	return s.top == s.capacity-1
}
func (s *Stack) Push(value int) bool {
	if s.IsFull() {
		fmt.Println("Stack Overflow! Cannot push element.")
		return false
	}
	s.top++
	s.data[s.top] = value
	return true
}
func main() {
	// Create a stack and push elements: [88, 95, 72, 80, 91]
	stack := NewStack(10)
	stack.Push(88)
	stack.Push(95)
	stack.Push(72)
	stack.Push(80)
	stack.Push(91)
	// Pop elements
	value, _ := stack.Pop()
	fmt.Println(value) // Output: 91, Stack now: [88, 95, 72, 80]
	value, _ = stack.Pop()
	fmt.Println(value) // Output: 80, Stack now: [88, 95, 72]
	value, _ = stack.Pop()
	fmt.Println(value) // Output: 72, Stack now: [88, 95]
	fmt.Printf("Top index after popping 3 elements: %d\n", stack.top) // Output: 1
}

Peek operation

The Peek operation returns the element at the top of the stack without removing ...