# Implementing Stack in Data Structures

12 Apr 2024
Beginner
15.5K Views
Learn via Video Course & by Doing Hands-on Labs

## Stack in Data Structures: An Overview

Stackin Data Structures is a type of non-primitive, linear, and dynamic data structure. It works according to the `LIFO` Principle. In this DSA tutorial, we will see stack in detail i.e. its features, working, implementation, etc. To further enhance your understanding and application of stack concepts, consider enrolling in theData Structures and Algorithms Course, to gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

## 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.

## Standard Operations on Stack

The time complexity of all the given operations is constant, i.e. `O(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.

### 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 an `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.

### 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
``````

### 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
``````

### 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 `TOP`i.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 mainly two ways to implement Stacks 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)`.

### Implementation of Stack Using a 1D Array

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

1. Declare a variable `top` to keep track of the top element in the stack.
2. When initializing the stack, set the value of the `top` to `-1` to check if the stack is full or empty.
3. 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.
4. Under the function
• Check if the stack is already full. If so, return from the function.
• If the stack is not full, increment the `top` and place the new element in the position pointed to by the `top`.
5. Declare a function `pop()` that removes the `top` element from the stack.
6. Under the function:
• Check if the stack is empty. If so, return from the function.
• 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.

7. Declare a function `topElement()` that returns the element at the `top` index from the array `stack[]`.
8. Declare a function `size()` that returns the occupied size of the array `stack[]`. It returns `top + 1`.
9. Declare a function `isEmpty()` to check if the `top` is equal to `-1`. If it is, it returns `true`, otherwise `false`.
10. 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() {
}

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

public int stackSize() {
}

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 ( ){
}

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
``````

• 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.

### 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

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

def push(self, data):
temp = Node(data)
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
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;

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

class Stack {
Node top;

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

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

public boolean isEmpty() {
}

public int peek() {
if (!isEmpty()) {
} 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;
// 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;

struct Node{
int data;
};

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
// Make temp as top of Stack
top = temp;
}
// function to check if stack is empty or not
int isEmpty(){
}
int peek(){
// Check for empty stack
if (!isEmpty())
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{
temp = top;
// Assign second node to top
// Destroy connection between
// first and second
// 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.

• 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. The list of the expression conversion is given below:
• infix to prefix
• Infix to postfix
• Prefix to infix
• Prefix to postfix
• Postfix to infix
4. Parsing: A stack is often used in parsing algorithms to keep track of the nesting of symbols such as parentheses, brackets, and braces.
5. 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.
6. 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.

• 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.

• 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 saw 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 test your knowledge of stack, enroll in our Dsa Training.

## FAQs

### Q1. How to implement Stacks in Data Structures?

There are mainly two ways to implement Stacks in Data Structures, using a 1D Array and using a Single Linked List.

### Q2. What are the limitations of Linked List implementation of stacks?

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

### Q3. What are the advantages of Stacks?

Easy to implement, Efficient memory management, Accessibility, Recursive algorithms, Compiler Design, etc.
Share Article
Batches Schedule
Similar Articles