Stack in Data Structure

A stack is a simple yet powerful data structure used in various computer science applications, such as managing function calls, evaluating expressions, and implementing depth-first search (DFS) and more. Stacks are a key tool every developer should understand because it is a fundamental way to manage sequential data using the LIFO principle. In this article, you will explore everything about stacks, from basic concepts to real-world applications and implementations.

Table of Contents:

• Overview of the Stack in Data Structures
• How Stack is Implemented in Memory
  • Array-Based Stack Implementation
  • Linked List-Based Stack Implementation
• Basic Stack Operations
  1. push()
  2. pop()
  3. peek() or top()
  4. isEmpty()
  5. isFull()
• Common Stack Applications in Computer Science
• Error Handling in Stacks: Overflow and Underflow
• Best Practices for Working with Stack
• Real-World Examples of Stack Usage
• Conclusion

Overview of the Stack in Data Structures

Think of a stack of plates or a stack of books. The stack data structure is like that. It can store data of any type. All the stack operations, such as push, pop, and peek, occur from the same end. This end is the top of the stack. This principle is referred to as LIFO. 

Important Features of a Stack: The Stack data structure works with the LIFO rule. The LIFO stands for Last-in, First-out. 

How Stack Operates?

Stack operates using the LIFO method. LIFO stands for last-in, first-out. This principle is the basis of many computer science algorithms and methods of data management. This data structure principle says that the item that was added to the stack last will get removed first. This means, when you push an item, it becomes the current top of the stack, and when you pop an item, you remove whatever is currently on the top.

To better understand stacks, let’s use a simple example to illustrate. Consider that you have an empty stack and you push the integers 1, 2, and 3, respectively, to it. Your stack will look like:

Now you will pop an element from the stack. This will remove the number 3, which is the top element of the stack. The stack will then look like this

Drawbacks of the  Stack Data Structure 

• You can only access the top item of a stack directly.
• To get an item in the middle, you must remove all items above it one by one.
• This makes stacks slow when you need to reach items in different positions quickly.
• So, stacks are not good if you want to access elements randomly.

How Stack is implemented in Memory

There are two ways to represent a stack in memory. One way is using an array, and the other is using a linked list. In this section, we will discuss both arrays and linked lists in memory. 

1. Array-Based Stack Implementation

This way involves using a static or dynamic array to hold the stack elements. We add a pointer to indicate where the top of the stack is. This method relies on static memory allocation, which means the size of the stack is fixed and the memory allocated to the stack cannot be changed thereafter. A stack implemented with an array holds its values in one continuous block of memory. Therefore, we can use the simple structure of arrays to accomplish all of the stack operations. 

Advantages: 

• Time complexity for all stack operations is O(1).
• This makes this implementation faster and more efficient.

Disadvantages:

• When using a static array, the stack size is fixed and cannot grow beyond the initial allocation, potentially causing a stack overflow if exceeded
• Dynamic arrays can resize, but resizing operations can be costly because they involve allocating new memory and copying existing elements, which impacts performance during those times.

2. Linked List-Based Stack Implementation

In this approach, the stack is implemented using a linked list. Each node in the linked list stores the element of the stack and a pointer to the next node in the stack. The linked list also holds a reference to the top node. The stack keeps track of the top node, which represents the most recently added element. Each node is stored in non-contiguous memory locations. The nodes are linked together using pointers, with the top node pointing to the next node down the stack, forming a chain.

Advantages:

• The stack size is variable, so you are able to insert or delete elements or nodes until system memory is full. And that is why there can be no risk of a stack overflow
• The time complexity for the insert and remove operations is always O(1) without changing the position of other elements.

Disadvantages:

• Every node has to maintain extra memory for the pointer/reference of the next node. It makes the memory overhead significantly high.
• Because you have a pointer to manage for each node, it means slightly more work when compared to an array.

Basic Stack Operations

You can customize the operations you want to work on your stack. But there are a few basic operations that are a must for your stack to work properly. This section will cover all these basic operations, along with algorithms to implement them. Once you understand the algorithm, you can implement it using the programming language of your choice. 

 1. push()

This operation is used to insert an element on top of the stack.

Algorithm:

Step 1: Start
Step 2: Check if the stack has reached its maximum capacity:
            If yes, signal an overflow error (cannot insert)
            If no, proceed to step 2
Step 3: Place the new element at the position immediately above the current top
Step 4: Update the "top" pointer/index to refer to this newly inserted element
Step 5: End

2. pop()

This operation is used to remove the element on top of the stack.

Algorithm:

Step 1: Start.
Step 2: Check if the stack is empty:
            If yes, signal an underflow error (nothing to remove).
            If no, proceed to step 3.
Step 3: Retrieve the element at the current "top" position.
Step 4: Remove that element from the stack.
Step 5: Adjust the "top" pointer/index to the next element down.
Step 6: Return the retrieved element.
Step 7: End

3. peek() or top()

This operation is used to see or fetch the top element. 

Algorithm: 

Step 1: Start
Step 2: Check if the stack is empty:
            If yes, signal an underflow error (no top element exists).
            If no, proceed to step 3.
Step 3: Return the element at the current "top" position without removing it.
Step 4: End

 4. isEmpty()

This operation is used to check if the stack is empty.

Algorithm:

Step 1: Start
Step 2: Compare the "top" pointer/index to the initial (empty) position:
            If they match, the stack has no elements; return true.
            Otherwise, return false.
Step 3: End

 5. isFull() 

This function is used to check if the stack is full or not.

Algorithm:

Step 1: Start
Step 2: Compare the current number of elements to the stack's capacity:
            If the count equals capacity, return true.
            Otherwise, return false.
Step 3: End

Common Stack Applications in Computer Science

1. A Function Call Stack: A function call stack keeps track of all the functions that are currently running in a program. It works on the Last-In-First-Out (LIFO) principle, which means the most recently called function is the first one to finish and be removed from the stack.

2. Expression Evaluation: Stacks are used to evaluate mathematical expressions in calculators and many other applications. Operators and operands are processed sequentially. It pushes the operands onto the stack until it encounters an operator. Then it pops out the two topmost operands and calculates the result based on the operator.
   Example: Let us evaluate the expression 3 + 4 * 2. First, the expression is converted to a postfix expression 3 4 2 * + and pushed into the stack.

The expression is evaluated in the following steps

• Step 1: Initialize the stack. The stack is initially empty.
• Step 2: Push 3 → Stack: [3]
• Step 3: Push 4 → Stack: [3, 4]
• Step 4: Push 2 → Stack: [3, 4, 2]
• Step 5: Encounter ‘*’: Pop 2 and 4, calculate, and again push 8 → Stack: [3, 8]
• Step 6: Encounter ‘+’: Pop 8 and 3, evaluate the expression with * and then push 11 → Stack: [11]
• Step 7: Final result: The final result of the expression is the only element left on the stack, which is 11.
  
  

3. Backtracking Algorithms: Backtracking algorithms utilize stacks to maintain a systematic search with all of the possible solutions. Consider that you are navigating through a maze. You always start at the entrance, and you try different paths to find your way through the maze. After taking each step forward, you will push that particular step that you are taking. In other words, once you reach a dead end within the maze, you’ll backtrack the last step off the stack and then follow the next direction you haven’t gone in. This keeps on going until you either find the way out or exhaust all possible options.
   
   In computer programming, the stack holds the current sequence of execution and allows you to go backwards to the prior state with ease. The stack is particularly handy for problems like maze solving, the n-queens problem, or any NP complete or NP hard combinatorial problem that requires testing multiple different paths and backtracking on admitted failing paths. The LIFO (Last-In-First-Out) nature ensures that you are always returned to the most recently changed decision point when backtracking during your program execution, and this is why it is one of the better data structures to use for backtracking algorithms
4. Undo/Redo Operations in Various Applications: Most applications use the stack for undo/redo functionality. We push the action on a stack, and for the Undo operation, we pop it off, and for the Redo operation, we re-push.

5. Browser History Navigation: Web browsers use a stack to keep tabs on the sites that you have visited. When you visit a new page, you will be pushing it onto the array. If the “back” button is clicked, you simply pop the current page off the stack. Clicking a “forward” button will again push the page back to the stack.

6. Parentheses Matching and Syntax Validation: When programmers write code, all the parentheses, brackets, and braces must match up correctly. Compilers use a stack to help check this. Whenever they see an opening symbol like “(” or “{“, they put it on the stack. When they see a closing symbol like “)” or “}”, they check if it matches the last opening symbol on the top of the stack. This way, they can tell if everything is properly paired.

7. Depth-First Search (DFS): Depth-First Search (DFS) traverses a graph by going down one path as far as possible before backtracking to explore other paths, keeping its journey using a stack of the next nodes to explore.

Error Handling in Stacks: Overflow and Underflow

Two primary errors are possible when using stacks: stack overflow and stack underflow. These are related to stack size and must be explicitly addressed in the manner in which you construct your code.

Stack Overflow

Pushing an element into an already full stack is called a stack overflow. This error occurs when the stack has a fixed size (as in the case of a stack implemented with an array).

Consequences: If left unhandled, overflow may lead to corrupted data, crashing programs, or undefined behavior.

How to handle a stack overflow:

In order to handle this error, you can create a check function or an isFull() operation before a push() operation to check that there is room on the stack.

Algorithm:

Step 1: Start
Step 2: Check if the stack is full
        IF the stack is full THEN
            Display an error message: "Stack Overflow – cannot insert element."
            STOP the operation
        ELSE
            Insert the element at the top position
            Increase the top pointer
Step 3: End

Stack Underflow

If you try to remove an item from an empty stack, you hit a stack underflow.

Consequences: Underflow may lead to retrieving wrong data, crashes in the program, or reaching memory spots that are not valid.

How to handle a stack underflow error: Always make sure the stack is not empty before removing an item. Use the isEmpty() method or peek() method to see if the top has a NULL value.

Algorithm:

Step 1: Start
Step 2:
       IF the stack is empty THEN
          Display an error message: "Stack Underflow – no element to remove."
          STOP the operation
       ELSE
          Access and remove the top element
          Decrease the top pointer
Step 3: End

Best Practices for Working with Stack

You should always follow best practices to implement and use the stack efficiently and effectively. As a developer, it is your responsibility to write code that takes the least time.

1. Choose Built-in Stack Implementation

Every object-oriented programming Language has a built-in implementation of a stack. Unless it is absolutely necessary, you should always use these built-in implementations as they are already tested for errors and will save you time. 

• In Python, you can use the list class or collections.deque.
• In Java, try to use Deque over the Stack class, as the Stack class is legacy now.
• In C++, use the std::stack class.

2. Ensure Stack Overflow and Underflow Protection

If you are implementing the stack data structure on your own, you should always remember to add a proper mechanism to deal with stack overflow and underflow. This will help you prevent runtime errors and undefined behavior due to underflow or overflow.

3. Limit Stack Size When Needed

A stack data structure gives you the power to limit its size. This allows you to control the memory usage. By enforcing a maximum stack size, you can prevent unbounded growth that could lead to excessive memory consumption, system slowdowns, or crashes. This is especially important in embedded systems, real-time applications, or mobile devices. 

Real-World Examples of Stack Usage

The concept of stacks comes in handy for solving a lot of real-world problems since this deals with sequential data. It is also used to represent various real-world structures like a stack of books, floors in a building, and many more.

One of the examples is evaluating the postfix notation. Let us consider an example. The stack data structure is used to solve this.

Code:

Output:

Explanation: The postfix expression “231+9-*” is evaluated systematically using a stack. First, you compute 3 multiplied by 1, which equals 3, and place that onto the stack. Then you compute 2 plus 3 equals 5 and keep that on the stack. After that, you push 9 and subtract that from 5 (5 – 9 = -4). The last value on the stack is -4, so that is the value that is returned and displayed.

Conclusion

This article explained stacks clearly by showing their main actions, how they use memory, and where they are useful in computer science. Stacks work based on the LIFO (Last In, First Out) rule, which helps manage data in a specific order. Stacks are useful for tasks like handling function calls, solving math expressions, or exploring paths in algorithms. It also showed two ways to create stacks: using arrays or linked lists, so developers can choose what fits best. Lastly, avoiding stack overflow and underflow errors is important to keep programs running smoothly. Overall, stacks are a basic but powerful tool to solve many computer problems.

To strengthen your expertise and boost your career prospects, enroll in our Software Development Course for practical learning. Also, get ready for job interviews with our Software Engineering Interview Questions, designed by industry professionals.

Stack in Data Structures