Home/Blog/Interview Prep/Understanding stacks and their applications

Understanding stacks and their applications

Hassan Shahzad

Sep 12, 2024

11 min read

content

What is a stack?Data manipulation behavior Stack operations Push Pop Peek isEmpty Size Code example Application and uses The undo/redo mechanism Expression evaluation Backtracking algorithms Examples of backtracking algorithms Complexity analysis What’s next?

Recommended resource

Grokking the Coding Interview Patterns

With thousands of potential questions to account for, preparing for the coding interview can feel like an impossible challenge. Yet with a strategic approach, coding interview prep doesn’t have to take more than a few weeks. Stop drilling endless sets of practice problems, and prepare more efficiently by learning coding interview patterns. This course teaches you the underlying patterns behind common coding interview questions. By learning these essential patterns, you will be able to unpack and answer any problem the right way — just by assessing the problem statement. This approach was created by FAANG hiring managers to help you prepare for the typical rounds of interviews at major tech companies like Apple, Google, Meta, Microsoft, and Amazon. Before long, you will have the skills you need to unlock even the most challenging questions, grok the coding interview, and level up your career with confidence. This course is also available in JavaScript, Python, Go, and C++ — with more coming soon!

85hrs

Intermediate

281 Challenges

282 Quizzes

Data manipulation behavior#

Last In, First Out (LIFO) is the principle that controls data manipulation in stacks. This principle essentially influences how data is accessed, stored, and removed. The first element added to a stack will be the last to be removed. Such an arrangement of operations comes to life within various computational contexts under this stack behavior. In a LIFO system, the last element added is the first one to be processed, so elements are processed in the reverse order from how they were added. For instance, when adding something new on top, you need the previous bits to support it. As an illustration, within programming languages for function call management, a call stack guarantees that the last function called returns first, maintaining a proper sequence of actions and efficient backtracking through recursive algorithms.

Let’s look at the illustration to better understand the working of the LIFO order:

Furthermore, undo mechanisms used in computer programs allow users to undo their most recent actions first to retrace their steps as they were executed previously. Another aspect that makes this data structure useful is its simplicity and efficiency regarding its operations—push (addition of an item), pop (deletion of an item), and peek (accessing the head), all of which take constant time to execute.

Stack operations#

The LIFO mechanism of the stack data structure depends on three basic operations: push, pop, and peek. These procedures ensure effective and organized data management throughout the stack, allowing for various applications in different computational tasks.

Push#

This operation is responsible for adding an element to the top of the stack. This is a simple yet effective operation that makes data insertion efficient. Pushing a new element onto the stack causes it to be positioned above every other element, thus making it the top element. This operation is completed in $O(1)$ constant time, guaranteeing that the performance of the insertion procedure remains unchanged as the stack expands. The push operation is essential for maintaining a specified order of activities or items in these settings.

Let’s look at the illustration to better understand the workings of the push operation:

Pop#

This operation is the counterpart to the push operation, responsible for removing the topmost element from the stack. The most recent element inserted is the first to be withdrawn in this operation, which strictly follows the LIFO concept. Similar to the push operation, popping an element from the stack is very efficient because it takes $O(1)$ , or constant time, to complete. The pop action is crucial in applications where items are processed and removed in the opposite order of their addition, such as syntax parsing and expression evaluation. Eliminating unnecessary components guarantees proper operation execution and efficient resource management, including memory in function calls.

Let’s look at the illustration to better understand the workings of the pop operation:

Peek#

With this operation, the top member of the stack can be accessed without being removed. To ensure that judgments may be made based on the present state of the stack without changing its structure, this operation offers a mechanism to inspect the element at the top of the stack. The efficiency characteristic of stack operations is maintained by the peek operation, which is likewise performed in constant time, $O(1)$ . Peek is very helpful for algorithms that often need to examine the top element, like when parsing syntax and ensuring that the parentheses are balanced. The approach facilitates the validation process without changing the contents of the stack by looking at the top element to see if the current closing parenthesis matches the most recent opening parenthesis.

Let’s look at the illustration to better understand the workings of the peek operation:

isEmpty#

This utility operation determines if there are any elements in the stack. If the stack is empty, it returns true; if not, it returns false. When performing stack operations like pop and peek, which depend on at least one element in the stack functioning properly, this operation is essential for avoiding problems. Developers can prevent exceptions before these actions and gracefully manage edge cases by ensuring the stack is empty. Because the isEmpty action usually consists of a straightforward comparison of the stack’s size or a check against a null reference, it is also performed in constant time, $O(1)$ .

Size#

The number of items that are presently kept in the stack is returned by this operation. This information makes understanding the stack’s capacity and controlling apps’ use easier. For example, knowing the stack size can aid resource allocation decisions and guarantee that the stack stays under a specific limit when resource limitations are crucial. By keeping track of a counter that increases or decreases with each push or pop operation, the size operation is often constructed to run in constant time, $O(1)$ . Doing this guarantees that the size may be effectively queried without requiring a full stack iteration.

Code example#

Let’s look at the code example of the above mentioned operations:

class Stack:
  def __init__(self):
    self.stack = []
  # Add an element to the top of the stack.
  def push(self, item):
    self.stack.append(item)
    print(f"Pushed {item}")
    print("Stack:", self.stack,"\n")
  # Remove and return the top element from the stack. Raise an error if the stack is empty.
  def pop(self):
    if self.is_empty():
        raise IndexError("pop from empty stack")
    
    item = self.stack.pop()
    print(f"Popped {item}")
    print("Stack:", self.stack,"\n")
    
    return item
  
  # Return the top element of the stack without removing it. Raise an error if the stack is empty.
  def peek(self):
    if self.is_empty():
        raise IndexError("peek from empty stack")
    
    print("Peek value: ",self.stack[-1],"\n")
    return self.stack[-1]
  # Check if the stack is empty
  def is_empty(self): 
    return len(self.stack) == 0
  # Return the number of elements in the stack
  def size(self):
    return len(self.stack)
# Driver code
if __name__ == "__main__":
  stack = Stack()
  stack.push(1)
  stack.push(2)
  stack.push(3)
  stack.peek()
  stack.pop()
  stack.peek()
  stack.pop()
  stack.pop()

Stack operations

Application and uses#

The versatility and ease of implementation make them a fundamental data structure frequently utilized in software development. Here are some of the applications of stacks:

The call stack in programming languages is one of the main uses for stacks; it makes sure that the local variables and execution state of each function are appropriately kept.
Stacks are essential for parsing syntax and expressions during compilation. This allows one to evaluate arithmetic expressions quickly and ensure that parentheses are balanced.
Stacks are also essential for backtracking algorithms in puzzle and maze solving by keeping track of other paths to explore.
Web browsers allow users to effortlessly travel back and forth thanks to their history feature, which uses stacks to manage sites visited.
Stacks are also utilized in text editors and other apps’ undo/redo features, which offer a straightforward yet efficient approach to undo or redo actions.

Let’s examine some of the uses of stacks in these applications.

The undo/redo mechanism#

A popular and effective method for handling application modifications where users might execute several actions and need to undo or redo those actions is the undo/redo technique using a stack. Two stacks—one for undo operations and another for redo operations—are used by this method. To ensure that subsequent actions are consistent with the updated state, completed actions are moved to the undo stack, and the redo stack is cleared. When an action is undone, the most recent action is removed from the undo stack and placed onto the redo stack, returning the state to its initial state.

On the other hand, reapplying an action involves popping and pushing the most recent action from the redo stack back onto the undo stack. This stack-based methodology offers a reliable means of handling user actions and state changes within an application by guaranteeing that the order of operations can be precisely and effectively maintained.

Let’s look at the illustration to better understand the working of the undo and redo operations:

class UndoRedoStack:
  def __init__(self):
    self.undo_stack = []
    self.redo_stack = []
  def perform_action(self, action):
    # Clear the redo stack when a new action is performed.
    self.redo_stack.clear()
    
    # Push the new action onto the undo stack.
    self.undo_stack.append(action)
    print(f"Performed action: {action}")
    self.print_state()
  def undo(self):
    if not self.undo_stack:
        print("No actions to undo")
        return
    
    # Pop the last action from the undo stack and push it onto the redo stack.
    action = self.undo_stack.pop()
    self.redo_stack.append(action)
    print(f"Undo action: {action}")
    self.print_state()
  def redo(self):
    if not self.redo_stack:
        print("No actions to redo")
        return
    
    # Pop the last action from the redo stack and push it onto the undo stack.
    action = self.redo_stack.pop()
    self.undo_stack.append(action)
    print(f"Redo action: {action}")
    self.print_state()
  def print_state(self):
    print(f"Undo stack: {self.undo_stack}")
    print(f"Redo stack: {self.redo_stack}")
    print()
def main():
    # Create an instance of the UndoRedoStack
    editor = UndoRedoStack()
    # Perform some actions
    editor.perform_action("Type 'Hello'")
    editor.perform_action("Type 'World'")
    editor.perform_action("Delete 'World'")
    # Undo actions
    editor.undo()
    editor.undo()
    # Redo actions
    editor.redo()
    editor.redo()
    # Perform another action
    editor.perform_action("Type 'Stack'")
    # Undo and redo again
    editor.undo()
    editor.redo()
if __name__ == "__main__":
    main()

Undo/Redo mechanism

Expression evaluation#

In computer science, expression evaluation with stacks is a fundamental technique for parsing and calculating mathematical expressions, particularly those with operators and operands in prefix, postfix (Reverse Polish notation), or infix notation. The LIFO feature of the stack data structure makes it especially suitable for this assignment since it precisely fits the need to efficiently handle nested and sequential operations. In evaluating an expression, operands are loaded onto the stack. Upon encountering an operator, the required operands are removed from the stack, the operation is carried out, and the outcome is pushed back onto the stack. Until the expression is assessed in its entirety, this process is repeated. For instance, operands are pushed while evaluating a postfix expression like $3~2~4~*~+$ , and the top two elements are popped, multiplied, and the result is pushed back when the operator $*$ is encountered. This approach ensures correct operation sequence and good parenthetical management while streamlining the handling of complex expressions. It is efficient. As such, stacks are essential to expression evaluation across a wide range of programming languages and computational applications.

Let’s look at the illustration to better understand how stack is utilized to evaluate the expression:

Note: The solution for this application is posed as a challenge to the user. To understand how to evaluate an expression using a stack, please check out Evaluate Postfix Expression Using a Stack.

Backtracking algorithms#

Backtracking algorithms are an effective problem-solving method that examines every potential solution and eliminates those that do not meet the limitations of the problem. Stacks are essential to these algorithms because they keep track of the problem’s state as it moves through many possible solutions. The current state is pushed onto the stack, and the algorithm moves on to the next stage, when a certain path or solution has to be investigated. When the algorithm encounters a dead end, it attempts an alternative route and goes back by popping the stack to return to the prior state.

Examples of backtracking algorithms#

Depth-First Search (DFS) in graphs: In DFS, a stack records the vertices that need to be visited. The method pushes the first node into the stack first, then proceeds to push its neighboring nodes onto the stack to examine them. If a node has no unvisited neighbors, the method pops the stack to go back and investigate alternative branches.

Note: The Introduction to Tree Depth-First Search lists some of the main problems with using a stack to track the nodes in trees and graphs.

N-Queens problem: The problem involves placing $N$ queens on an $N×N$ chessboard such that no two queens threaten each other. A stack is used to keep track of the positions of the queens on the board. When placing a queen, the algorithm pushes the current state onto the stack. If a valid position is not found, the algorithm pops the stack to remove the last placed queen and tries a new position.

Note: Refer to the N-Queens lesson here to understand and gain insights into how the N-Queens problem utilizes the stack to track the positions of the queen on the board.

Maze solving: A stack can record the path to solve a maze. Starting from the entrance, each move is pushed onto the stack. When a dead end is encountered, the stack is popped to backtrack to the previous position and explore alternative paths until the exit is found.
Sudoku solver: The board’s current state can be saved in a stack at each step when solving a Sudoku puzzle. The program fills the board by pushing the value of each cell onto the stack. If a dispute occurs, the stack is popped to go back and try an alternative value.

Complexity analysis#

Let’s discuss and analyze the time complexities of stack operations through a comparison table, highlighting their efficiency and rationale in various applications:

Complexity Table

Operation	Time Complexity	Why?
Push	O(1)	The push operation adds an element to the top of the stack. This involves appending an element to the stack, which requires constant time.
Pop	O(1)	The pop operation removes the top element from the stack. This involves removing the topmost element from the stack.
Peek	O(1)	The peek operation retrieves the top element without removing it. This involves accessing the top element of a stack.
isEmpty	O(1)	The isEmpty operation checks if the stack contains any elements. This involves checking the size of the stack or comparing the stack to an empty stack. This operation is performed in constant time as it involves a simple comparison or size check.
Size	O(1)	The size operation returns the number of elements in the stack. This involves accessing the length of the stack. This operation is performed in constant time since it involves reading the length property of the stack, which is maintained during insertions and deletions.

What’s next?#

Learning about stacks and their uses is essential to become an expert in basic data structures in programming. Explore stacks in greater detail using Educative’s vast library of courses and learning paths. Whether you are a novice or seeking to expand your skills, our platform offers extensive materials to assist students at any skill level. Discover how our useful content can enable you to completely comprehend the nuances of stacks and their many applications in effectively resolving real-world issues. Visit Educative.io to find the best courses designed to improve your comprehension of stacks and advance your development into a professional role. Here are some of the top resources containing content about stacks and their applications:

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments