How to Implement Stacks in Data Structure? Stack Operations Explained

Are you interested in learning about Stack operations in data structure in an easy-to-grasp manner? Here’s what you are looking for!

A Stack is a linear data structure where the data can be accessed on LIFO, meaning that an element inserted at last will be removed first. A Stack can be imagined as a pile of books or, say, a pile of plates on top of one another. To add one, you may put it on the top so the rest of the Stack is not disturbed. To remove one, you may take the book added last to avoid disturbing the rest of the pile. This is a simple illustration of how a Stack work. A Stack has two basic operations, a push and a pop. 

Stacks are commonly used in many areas of computer science and programming. If you’re interested in a career in this field, a Professional Certificate Program in Data Science and Business Analytics will be an ideal choice to go through with. Some areas where Stack is used include managing function calls in programming languages (using a call Stack), undo/redo functionality in text editors, evaluating the arithmetic expressions, and implementing the backtracking algorithms. This blog gives you an overview of the implementation of Stacks in data structure.

Stack Representation in Data Structures

Now that you have a fair idea of what is Stack, here’s a look into its representation. There are two ways to represent a Stack in data structure-

• Using an Array

Data can be presented through an array; under an array, the data structure is fixed, while the Stack requires data to increase or decrease. To implement a Stack under a fixed array, a variable is inserted at the top to make the changes as required.

By increasing the variable and assigning the element to the relevant index of the array, we can put an element at the top of the Stack. By returning the element at the current index of the array and decrementing the variable, we can remove an element from the top of the Stack. 
 

• Using a Linked List

Another way to overcome the issue of constant size is to represent a Stack with a linked list. A linked list is a data structure composed of nodes, each of which contains data and a pointer to the next node. To implement a Stack using a linked list, we must keep a pointer to the Stack’s top node. 

The linked list-based representation allows for dynamic resizing as nodes can be added or removed dynamically. However, accessing elements in a linked list-based Stack has a time complexity of O(n), as traversal from the top node to the desired element may require traversing the linked list.
Learn data science courses online from the World’s top Universities. Earn Executive PG Programs, Advanced Certificate Programs, or Masters Programs to fast-track your career.

Working of Stack in Data Structures

Here’s a simple explanation of how Stack works in data structures. 

Assuming you are working on a Stack of 50 books, to insert the 60th book, you need to update the top to insert the 60th book.

If you want to access the 30th book, you need to remove the topmost book so that the top will pop for the 30th book.

Check out our free courses to get an edge over the competition.

Basic Operations on Stack in Data Structures

The working of a Stack can be further explained by using the following operations –

1. push()

When an element is pushed onto the Stack, a new node is created, and the element value is assigned to it. The new node’s next reference points to the previous top node, and the top pointer is updated to the new node.

  2. pop()

This operation removes and returns an element from the top of the Stack. If the Stack is empty, then it causes an underflow condition.

  3. top()

This operation returns the element at the top of the Stack without removing it.

  4. isEmpty()

This operation returns true if the Stack is empty, else false.

  5. size() 

This operation returns the number of elements in the Stack.

  6. Peek Operation

A peek operation is an operation on a Stack that returns the value of the top element of the Stack without removing it. The peek operation can be helpful in checking the value of the top element without modifying the Stack.

  7. isFull()

An isFull() operation returns true if the Stack is full, else it returns false. It helps check whether the Stack has reached its maximum capacity and cannot store more elements.

A Python Programming Bootcamp from upGrad will give you a thorough understanding of all Stack operations. 

Application of Stack in Data Structures

A Stack can be used for various applications in data structures, such as –  

• Expression Evaluation and Conversion

A Stack can be used to evaluate arithmetic expressions in different notations, such as infix, prefix, and postfix. A Stack can also be used to convert an expression from one notation to another by using some rules and algorithms. 

• Backtracking

A Stack can be used to implement backtracking algorithms, which involve exploring all possible solutions until a desired goal is reached or all options are exhausted. For example, a Stack and queue can be used to solve mazes, puzzles, sudoku, etc.

• Function Call

A Stack can be used to store information about the active functions or subroutines in a program. When a function is called, its parameters, local variables, and return address are pushed onto the Stack. When the function returns, these values are popped from the Stack, and the control is transferred to the caller function.

• Parentheses Checking

A Stack can be used to check if an expression has balanced parentheses or not. For example, ((a b)*c) is balanced, but (a b)*c) is not. The algorithm is to push every opening parenthesis onto the Stack and pop every closing parenthesis from the Stack. If the Stack is empty at the end, then the expression is balanced.

• String Reversal

A Stack can be used to reverse a string by pushing all the characters of the string onto the Stack and then popping them out one by one. The order of the characters will be reversed due to the LIFO characteristic of the Stack.

• Syntax Parsing

A Stack can be used to parse the syntax of a programming language or a mathematical expression. A Stack can help match the tokens and detect any errors or ambiguities.

• Memory Management

A Stack can be used to manage memory allocation and deallocation in some programming languages, such as C and C++. A Stack can store the addresses of dynamically allocated memory blocks and free them when they are no longer needed.

Advantages of Array Implementation

Some of the advantages of array Stack implementation are –

1. Efficient Access to Elements

Arrays provide direct and efficient access to any element in the collection using the index number. This allows for fast data retrieval and manipulation.

  2. Memory Efficiency

Arrays have low overhead as they only require one memory block to store all the elements. There is no need to allocate or deallocate memory for each element separately.

   3. Sorting

Arrays can be used to sort data in ascending or descending order by using various algorithms, such as bubble sort, merge sort, and quicksort. Sorting can help in improving the performance and readability of the data.

   4. Searching

Arrays can be searched for specific elements using algorithms such as linear search and binary search. Searching can help in finding the desired data or checking its existence.

   5. Matrices

Arrays can be used to represent matrices in mathematical computations such as matrix multiplication, linear algebra, and image processing. Matrices are useful for modeling various phenomena and systems.

Disadvantages of Array Implementation

Some of the disadvantages of array implementation are –

1. Fixed Size

Arrays have a fixed size when they are created and may not be sufficient to store all the elements, causing an overflow condition. Similarly, if the array size is larger than the number of elements, it causes a waste of memory.

  2. Memory Allocation Issues

Allocating a large array can be problematic if the system has a small storage size. If not enough contiguous memory is available to store the array, then it causes a memory allocation error.

  3. Insertion and Deletion

Arrays do not support efficient insertion and deletion of elements. To insert an element at a specific position in the array, all the elements after that position have to be shifted one place to the right. Similarly, to delete an element from a specific position in the array, all the elements after that position have to be shifted one place to the left. This can be time-consuming and costly.

Conclusion

Stacks are linear data structures that follow the LIFO principle: the last element inserted is the first one removed. They can be implemented using arrays or linked lists, each with its own advantages and disadvantages. Stacks are useful for applications that require reversing, backtracking, or undoing operations. 

If you are eager to make a career in data analytics, join upGrad’s Data Analytics 360 Cornell Certificate Program for unmatched guidance and expertise through in-depth learning.