Implement Stack Using Linked List

Implement Stack Using Linked List” is a popular problem based on both linked list and stack data structures. Here, we need to implement stack using linked list.

The basic operations that stack data structure performs are:

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

As stack follows LIFO(Last In First Out) 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 a 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 a linked list from the beginning of the linked list.

Example:

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. Largest Rectangular Area in Histogram
  2. Length of Longest Valid Substring
  3. Reverse a String using Stack
  4. Implement two stacks in a single array
  5. Print Bracket Number
  6. Next Greater Frequency Element
  7. Sort a Stack using Temporary Stack
  8. Infix to Postfix Conversion
  9. Infix to Prefix Conversion
  10. Prefix to Infix Conversion
  11. Prefix to Postfix Conversion
  12. Postfix to Infix Conversion
  13. Postfix to Prefix Conversion
  14. Check whether given Parentheses String are Balanced Parentheses or Not.
  15. Next Greater Element
  16. Find Minimum number of bracket reversals required to make an expression balanced.
  17. Implement Queue Using Two Stacks.
  18. Merge Overlapping Intervals using Stacks
  19. Program to find equilibrium index of an Array.
  20. Program to find majority element of an Array.

You may also like...

Leave a Reply

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