Implement Stack Using Linked List

Implement Stack Using Linked List” is a popular programming problem asked in many technical and algorithmic interviews, based on both linked list and stack data structures. Here, we need to implement stack data structure using linked list data structure.

We strictly recommend to read the following post before proceeding:

  1. Insert element at the beginning of the linked list.

As we know, the basic operations that stack data structure performs are:

  1. Push Operation: Inserting an element at top of the stack.
  2. Pop Operation: Deleting an element from top of the stack.
  3. Peek Operation: Peeking(Checking) the top element of the stack.

As stack follows Last In First Out (LIFO) approach, the last element which is inserted into the stack will be the first element to be removed from the stack.

To implement stack using Linked List, following method can be used:

Performing PUSH Operation as inserting element in a linked list at the beginning of the linked list and POP Operation as deleting element from the beginning of the linked list.

Example to Implement stack using linked list:

Push Operation:

  • Empty Stack
  • Push ‘1’ in stack: 1 
  • Push ‘2’ in stack: 2 -> 1

Peek Operation:

  • ‘2’ is top element

Push Operation:

  • Push ‘3’ in stack: 3 -> 2 -> 1
  • Push ‘4’ in stack: 4 -> 3 -> 2 -> 1

Pop Operation:

  • Pop: 3 -> 2 -> 1

Peek Operation:

  • ‘2’ is top element

Pop Operation:

  • Pop: 2 -> 1
  • Pop: 1
  • Empty Stack

C++ Program to implement stack using Linked List is as follows:

/* C++ Program to Implement Stack Using Linked List */
#include<bits/stdc++.h>
using namespace std;

/* Structrue of the Node */
struct node
{
    int data;
    struct node *next;
};


/* Function to Push an element in a stack */
void push(struct node **head, int ele)
{
    /*Creating a new node.*/
    struct node *new_node;
    new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = ele;
    new_node->next = NULL;
    
    cout<<ele<<" is pushed into stack!!\n";
    
    /* check whether the Stack is empty or not*/
    /* If empty, new node will become head of the stack(Linked List) */
    if(*head == NULL)     
    {
        *head = new_node;
        return;
    }
    
    /* If stack is not empty, insert element at beginning of stack */
    new_node -> next = *head;
    (*head) = new_node;
    
}

/* Function to Pop out element from stack*/
void pop(struct node **head)
{
    /* If Stack is NULL, simply return */
    if(*head == NULL)
    {
        cout<<"Stack is already empty!!";
        return;
    }

    /* Delete the top element and assign head to next of current head */
    struct node *temp = *head;
    cout<<temp->data<<" is popped out from stack!!\n";
    (*head) = (*head) -> next;
    delete temp;
}

/* Function to Peek in a Stack */
void peek(struct node *head)
{
    /* If Stack is empty, return */
    if(head == NULL)
    {
        cout<<"\nStack is Empty!!\n\n";
        return;
    }
    /* If stack is not empty, print the top element */
    cout<<"\nThe top Element of Stack is "<<head->data<<"\n\n";
}
int main()
{
    struct node *head;
    head = NULL;
    cout<<"Inserting 3 Elements in a Stack!!\n\n";
    push(&head,1);
    push(&head,2);
    peek(head);
    push(&head,3);
    cout<<"\n\n Popping Elements from the stack!!\n\n";
    pop(&head);
    pop(&head);
    peek(head);
    pop(&head);
    pop(&head);

}
OUTPUT:
Inserting 3 Elements in a Stack!!
 
1 is pushed into stack!!
2 is pushed into stack!!
 
The top Element of Stack is 2
 
3 is pushed into stack!!
 
 
 Popping Elements from the stack!!
 
3 is popped out from stack!!
2 is popped out from stack!!
 
The top Element of Stack is 1
 
1 is popped out from stack!!
Stack is already empty!!

Related Posts:

  1. Merge Overlapping Intervals using Stacks
  2. Largest Rectangular Area in Histogram
  3. Length of Longest Valid Substring
  4. Reverse a String using Stack
  5. Implement two stacks in a single array
  6. Print Bracket Number
  7. Next Greater Frequency Element
  8. Sort a Stack using Temporary Stack
  9. Check whether given Parentheses String are Balanced Parentheses or Not.
  10. Next Greater Element
  11. Find Minimum number of bracket reversals required to make an expression balanced.
  12. Implement Queue Using Two Stacks.
  13. Check Anagram Strings.
  14. Check Whether Given String is Palindromic Anagram or Not.
  15. Check Whether Given String is Panagram or Not.
  16. Find First Non-Repeating Character of the String.
  17. Find Most Frequent Element of the Array.
  18. Find Pair in an Array with Given Sum.
  19. Find First Repeating Element of an Array.
  20. Find Majority Element of an Array.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *