Introduction to Stack in Data Structures

Stack in Data Structures

A stack in data structures is a linear collection that follows the Last In, First Out (LIFO) principle, where the last element added is the first to be removed. This structure is essential in various algorithms and applications such as expression evaluation, backtracking, and memory management. Stack implementation can be done using different programming languages such as stack in data structures using C, and stack in data structures using Java, Each offers its unique advantages.

In this DSA tutorial, we will see the stack in data structures in detail i.e. its features, working, implementation, etc. 

What is a Stack in Data Structures?

• A stack is an ordered list or we can say a container in which insertion and deletion can be done from the one end known as the top of the stack.
• The last inserted element is available first and is the first one to be deleted.
• Hence, it is known as Last In, First Out LIFO or First In, Last Out FILO.
• In a stack, the element at the top is known as the top element.
• When a new element is added to the stack, it is placed on top of the existing elements.
• Stacks are dynamic; this means that they do not have a fixed size and their size can be increased or decreased depending upon the number of elements.

Read More -

1.)Best Data Structure Interview Questions and Answers

2.) Differences Between Stack and Queue Data Structures

Standard Operations on Stack

The time complexity of all the given operations is constant, i.e. O(1).

1. Insertion: push()

The push() operation is one of the fundamental operations in a stack data structure. Pushing means inserting an element at the top of the stack. If the stack is full, then it is said to be an Overflow condition.

Algorithm for push() operation in the stack

begin
 if stack is full
 return
 endif
else 
 increment top
 stack[top] assign value
end else
end procedure

According to the algorithm,

1. First Check if the stack is full
2. If it is full, produce an error and exit
3. If the stack is not full, increment top to point to the next space.
4. Add the data element to the stack location, where the top is pointing.
5. End the process and exit.

2. Deletion: pop()

The pop() operation is used to remove the topmost element of the stack and return its value. The pop() operation modifies the state of the stack by removing the topmost element. The items are popped in the reversed order in which they are pushed. If the Stack is empty, it is a Underflow condition.

Algorithm for pop() operation on the stack

begin
 if stack is empty
 return
 endif
else
 store value of stack[top]
 decrement top
 return value
end else
end procedure

According to the algorithm,

1. First, check if the stack is empty.
2. If empty, print Stack underflow and exit.
3. If not empty, access the data element at which the top is pointing.
4. Decrease the value of the top by 1.
5. End the process and exit.

3. peek()

The peek() operation returns the value of the topmost element of the stack without modifying the stack. This can be useful when you need to check the value of the top element before deciding whether to remove it or not.

Algorithm for peek() operation on the stack

begin 
 return stack[top]
end procedure

4. isFull()

The isFull() operation is used to determine if the stack is full or not. A stack is said to be full if it has reached its maximum capacity and there is no more space to add new elements to the stack.

Algorithm for isFull() operation on the stack

begin
 if stack length is equal to the maximum stack size
 return true
 endif
 else
 return false
 end else
end procedure

5. isEmpty()

The isEmpty() operation is used to check if the stack is empty or not. It returns a boolean value, true when the stack is empty, otherwise false.

Algorithm for isEmpty() operation on the stack

begin
 if top < 1
 return true
 else
 return false
end procedure

Working of Stack in Data Structures

The size of the stack depends on the number of memory blocks available to store the elements.

• Initially, as shown in the figure, the stack is empty, and we can add elements one by one using the push operation until it becomes full.
• A pointer called TOP is used to keep track of the top element in the stack.
• When initializing the stack, we set its value to -1 so that we can check if the stack is empty by comparing TOP == -1.
• On pushing an element, 150, we increase the value of TOP and place the new element in the position pointed to by TOP i.e. TOP=0 and so stack[0]=150.
• Again we push n element, 250, and increase the value of TOP i.e. TOP=1 and so stack[1]=250.
• On popping an element, we return the element pointed to by TOPi.e. return stack[1] and reduce its value i.e. TOP=0.
• Before pushing, we check if the stack is already full.
• Before popping, we check if the stack is already empty

  

Implementation of Stack in Different Programming Languages

There are two ways to implementStack in Data Structures, using a 1D Array and using a Single Linked List. Let us look at each of them.

The time complexity of all the operations in both implementations is the same i.e. O(1).

1. Implementation of Stack Using a 1D Array

Follow the below-given procedure to implement stack using a 1D Array in Data Structures

• Declare a variable top to keep track of the top element in the stack.
• When initializing the stack, set the value of the top to -1 to check if the stack is full or empty.
• Declare a function push() that takes an array, stack[]; the size of the array, n; and the element a to be inserted as its parameters.
• Under the function:  you have to check if the stack is already full. If so, return from the function. and If the stack is not full, increment  top and place the new element in the position pointed to by the top.

• Declare a function pop() that removes the top element from the stack.
• Under the function just check if the stack is empty. If so, return from the function then If the stack is not empty, return the element at the top index in the array stack[] and decrement top. Here, we are not deleting the value at the top index during pop() because once the pointer is moved to point to the previous element, it does not matter what is contained in that memory location.

• Declare a function topElement() that returns the element at the top index from the array stack[].
• Declare a function size() that returns the occupied size of the array stack[]. It returns top + 1.
• Declare a function isEmpty() to check if the top is equal to -1. If it is, it returns true, otherwise false.
• Declare a function isFull() to check if the top is equal to the maximum size of the array stack[]. If it is, it returns true, otherwise false.

Example of Stack Implementation in Different Languages using a 1D array

class Stack:
    def __init__(self, size):
        self.size = size
        self.stack = [-1] * size
        self.top = -1

    def push(self, a):
        if self.top == self.size - 1:
            print("Stack Overflow")
        else:
            self.top += 1
            self.stack[self.top] = a

    def is_empty(self):
        return self.top == -1

    def pop(self):
        if self.is_empty():
            print("Stack Underflow")
        else:
            self.top -= 1

    def stack_size(self):
        return self.top + 1

    def top_element(self):
        return self.stack[self.top]


if __name__ == "__main__":
    stack = Stack(6)

    stack.push(5)
    print("Current size of stack is", stack.stack_size())

    stack.push(10)
    stack.push(15)
    stack.push(20)
    stack.push(25)
    stack.push(30)
    print("Current size of stack is", stack.stack_size())

    # Attempting to push into a full stack
    stack.push(35)

    # Accessing the top element
    print("At present, the top element in stack is", stack.top_element())

    # Removing all the elements from the stack
    for _ in range(6):
        stack.pop()
    print("Current size of stack is", stack.stack_size())

    # Attempting to pop from an empty stack
    stack.pop()
 

public class Stack {
 private int size;
 private int[] stack;
 private int top;

 public Stack(int size) {
 this.size = size;
 this.stack = new int[size];
 this.top = -1;
 }

 public void push(int a) {
 if (top == size - 1) {
 System.out.println("Stack Overflow");
 } else {
 top += 1;
 stack[top] = a;
 }
 }

 public boolean isEmpty() {
 return top == -1;
 }

 public void pop() {
 if (isEmpty()) {
 System.out.println("Stack Underflow");
 } else {
 top -= 1;
 }
 }

 public int stackSize() {
 return top + 1;
 }

 public int topElement() {
 return stack[top];
 }

 public static void main(String[] args) {
 Stack stack = new Stack(6);

 stack.push(5);
 System.out.println("Current size of stack is: " + stack.stackSize());

 stack.push(10);
 stack.push(15);
 stack.push(20);
 stack.push(25);
 stack.push(30);
 System.out.println("Current size of stack is: " + stack.stackSize());

 // Attempting to push into a full stack
 stack.push(35);

 // Accessing the top element
 System.out.println("At present, the top element in stack is: " + stack.topElement());

 // Removing all the elements from the stack
 for (int i = 0; i < 6; i++) {
 stack.pop();
 }
 System.out.println("Current size of stack is: " + stack.stackSize());

 // Attempting to pop from an empty stack
 stack.pop();
 }
}
 

#include<iostream>
using namespace std;
int top = -1; 
 
 void push (int stack[ ] , int a , int n){
 if ( top == n-1)
 cout << "Stack Overflow" << endl ; 
 else
 top = top +1 ; 
 stack[ top ] = a ; 
 }
 bool isEmpty ( ){
 if ( top == -1 ) 
 return true ;
 else
 return false;
 }
 
 void pop ( ){
 if( isEmpty ( ) )
 cout << "Stack Underflow " << endl ;
 else 
 top = top - 1 ; 
 }
 
 
 int size ( ){
 return top + 1;
 }
 
 int topElement (int stack[]){
 return stack[ top ];
 }
 
 int main( ){
 int stack[ 6 ];
 
 push(stack , 5 , 6 ) ;
 cout << "Current size of stack is " << size ( ) << endl ;
 
 push(stack , 10 , 6);
 push (stack , 15 , 6) ;
 push (stack , 20 , 6) ;
 push (stack , 25 , 6) ;
 push (stack , 30 , 6) ;
 cout << "Current size of stack is " << size( ) << endl ;
 
 //As the stack is full, further pushing will show an overflow condition.
 push(stack , 35 , 6) ;
 
 cout << "At present, the top element in stack is " << topElement(stack) << endl;
 
 for(int i = 0 ; i < 6;i++ )
 pop( );
 cout << "Current size of stack is " << size( ) << endl ;
 
 //As the stack is empty , further popping will show an underflow condition.
 pop ( ); 
 return 0;
 }

Output

Current size of stack is 1
Current size of stack is 6
Stack Overflow
At present, the top element in stack is 30
Current size of stack is 0
Stack Underflow 

Advantages of Array Implementation

• Easy to implement.
• Memory is saved as pointers are not involved.

Limitations of Array Implementation

• The maximum size of the array must be defined beforehand.
• The size of the array cannot be changed during the run time because it is not dynamic.

2. Implementation of Stack Using a Single Linked List

Follow the below-given procedure to implement Stack using a Single Linked List in Data Structures.

1. First of all, create a class or structure Node with instance variables, data, and next.
2. The data will contain the element to be inserted and next will contain the address of the previous element in the linked list.
3. To keep track of the topmost element, create an instance, top of the class Node.
4. Declare a function push() that takes data as a parameter and adds it to the existing linked list.
5. Under the function –
   • A temporary instance of the class Node is created, and memory is allocated for the same.
   • Check if the heap is full. If it is, print Stack Overflow.
   • If the heap is not full, add the data to the temporary instance.
6. Store the address of the previous top in the address part of the temporary instance.
7. Update the top so that it points to the temporary instance that contains the newly inserted value.
8. Declare a function pop() that deletes the current top, and point it to the element just before it.
9. Under the function –
   • Check if the stack is empty or not. If it is, print Stack Underflow.
   • If the stack is not empty, make the top point to the previous element.
   • Free the memory that was used by the element that was popped.

Example of Stack Implementation in Different Languages Using a Single Linked List

class Node:
    def __init__(self, data):
        self.data = data
        self.link = None

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        temp = Node(data)
        temp.link = self.top
        self.top = temp

    def is_empty(self):
        return self.top is None

    def peek(self):
        if not self.is_empty():
            return self.top.data
        else:
            exit(1)

    def pop(self):
        if self.is_empty():
            print("Stack Underflow")
            exit(1)
        else:
            temp = self.top
            self.top = self.top.link
            temp.link = None
            del temp

if __name__ == "__main__":
    stack = Stack()

    stack.push(5)
    stack.push(10)
    stack.push(15)
    stack.push(20)
    stack.push(25)
    stack.push(30)

    # Print top element of stack
    print("\nThe Top element is", stack.peek())

    # Delete top elements of stack
    stack.pop()
    stack.pop()
    stack.pop()
    stack.pop()
    stack.pop()

    # Print top element of stack
    print("\nThe Top element is", stack.peek())
 

class Node {
 int data;
 Node link;

 public Node(int data) {
 this.data = data;
 this.link = null;
 }
}

class Stack {
 Node top;

 public Stack() {
 this.top = null;
 }

 public void push(int data) {
 Node temp = new Node(data);
 temp.link = top;
 top = temp;
 }

 public boolean isEmpty() {
 return top == null;
 }

 public int peek() {
 if (!isEmpty()) {
 return top.data;
 } else {
 System.exit(1);
 return -1; // Unreachable, but added to satisfy compiler
 }
 }

 public void pop() {
 if (isEmpty()) {
 System.out.println("Stack Underflow");
 System.exit(1);
 } else {
 Node temp = top;
 top = top.link;
 temp.link = null;
 // Note: In Java, the memory will be automatically garbage collected, so no need to explicitly delete.
 }
 }
}

class Main {
 public static void main(String[] args) {
 Stack stack = new Stack();

 stack.push(5);
 stack.push(10);
 stack.push(15);
 stack.push(20);
 stack.push(25);
 stack.push(30);

 // Print top element of stack
 System.out.println("\nThe Top element is: " + stack.peek());

 // Delete top elements of stack
 stack.pop();
 stack.pop();
 stack.pop();
 stack.pop();
 stack.pop();

 // Print top element of stack
 System.out.println("\nThe Top element is: " + stack.peek());
 }
}
 

#include <iostream>
using namespace std;

// Declare linked list node
struct Node{
 int data;
 struct Node* link;
};

struct Node* top;

// function to push the elements into stack
void push(int data){
 // Create a new node temp
 struct Node* temp;
 
 //allocate memory
 temp = new Node();
 
 // Check if the stack is full.
 if (!temp){
 cout << "\nStack Overflow";
 exit(1);
 }
 // Set data of temp equal to data
 temp->data = data;
 // Make temp point to the top
 temp->link = top;
 // Make temp as top of Stack
 top = temp;
}
// function to check if stack is empty or not
int isEmpty(){
 return top == NULL;
}
// function to return top element in a stack
int peek(){
 // Check for empty stack
 if (!isEmpty())
 return top->data;
 else
 exit(1);
}
// function to delete top element
void pop(){
 struct Node* temp;
 // Check for stack underflow
 if (top == NULL){
 cout << "\nStack Underflow" << endl;
 exit(1);
 }
 else{
 // Top assign into temp
 temp = top;
 // Assign second node to top
 top = top->link;
 // Destroy connection between
 // first and second
 temp->link = NULL;
 // Release memory of top node
 free(temp);
 }
}
// main function
int main(){
 // Push the elements of stack
 push(5);
 push(10);
 push(15);
 push(20);
 push(25);
 push(30);

 // Print top element of stack
 cout << "\nThe Top element is " << peek() << endl;
 
 // Delete top elements of stack
 pop();
 pop();
 pop();
 pop();
 pop();
 // Print top element of stack
 cout << "\nThe Top element is " << peek() << endl;
 
 return 0;
}
 

Output

Top element is: 30

Top element is: 5 

If you are facing any difficulty in understanding the linked list implementation of stack in data structures refer to the previous tutorial, Linked Lists in Data Structures.

Advantages of Linked List Implementation

• A linked list is dynamic, i.e. the size of the linked list can be changed during the run time.
• It is used in many virtual machines like JVM.

Limitations of Linked List Implementation

• There's an extra requirement of memory due to the involvement of pointers.
• Random accessing of elements is not possible in a stack.

Applications of Stack

There are some applications of stacks in the data structure:

1. Function Calls and Recursion: When a function is called, the compiler stores information about the return address and the values of any parameters, in the stack. When the function is finished, the information is retrieved from the stack and the program continues executing from the point where it left off.
2. Recursion: To maintain the previous states, the compiler creates a system stack in which all the previous records of the function are maintained
3. Expression Evaluation: A stack can be used to evaluate arithmetic expressions in which parentheses are used to group sub-expressions. The operands and operators are pushed into the stack, and when a closing parenthesis is encountered, the sub-expression is evaluated using the operators and operands in the stack.
4.  The A list of the expression conversion is given below:
   • infix to prefix
   • Infix to postfix
   • Prefix to infix
   • Prefix to postfix
   • Postfix to infix
5. Parsing: A stack is often used in parsing algorithms to keep track of the nesting of symbols such as parentheses, brackets, and braces.
6. Undo/Redo Operations: Many applications, such as text editors and graphic design software, allow users to undo and redo previous operations. A stack can be used to store the state of the application before each operation, allowing the user to undo or redo the operation by popping or pushing elements from the stack.
7. Backtracking: When searching for a solution to a problem, it may be necessary to backtrack and try a different path if the current path does not lead to a solution. A stack can be used to store information about the current path, allowing the algorithm to backtrack by popping elements from the stack.

Advantages of Stack

• Easy to implement: The implementation of a stack is simple, making it easy to use and understand.
• Efficient memory management: A stack uses a contiguous block of memory, which is allocated when the stack is created. This makes it efficient in terms of memory utilization.
• Accessibility: A stack allows quick access to its elements as the elements are added and removed from the top of the stack, which is useful in many applications, such as parsing expressions and reversing a string.
• Recursive algorithms: A stack is used to store function calls and their states, which helps in the efficient implementation of recursive function calls.
• Compiler Design: Stack is used in compiler design for parsing and syntax analysis of programming languages.

Disadvantages of Stack

• Limited storage: Stacks can store only a fixed number of elements. In the case of stack overflow, there can be a loss of data.
• No random access: Unlike other data structures like arrays, stacks do not provide direct access to elements in the middle of the stack. You can only add and remove elements from the top of the stack. The user has to remove all the elements above the middle element to access it.
• Stack overflow and underflow: Adding or removing too many elements into and from the stack can cause stack overflow or underflow respectively causing the program to crash.
• Memory management: Stack uses a contiguous block of memory, which can result in memory fragmentation or memory leaks if there's a frequent addition or removal of elements.

Summary

So, here we have studied every aspect of a stack in data structures. You might have got at least some idea regarding stack and its applications. I know it's quite difficult to understand the whole topic in a single go. Therefore, refer to it again and again till you get thorough with the stack in data structures. To grow your knowledge about the stack in data structures, enroll in our Data Structures and Algorithms.