Stack implementation using Linked list

10 min read

Stack data structure implementation can be done using arrays and linked lists. Now, let us see the implementation of stacks using linked list.

Push and Pop operations in linked list

push() 

  • Create a newNode with the given data.
  • Check whether the stack is empty (TOP == NULL).
  • If it is empty, then set the pointer of the node to NULL.
  • If it is not empty, then make the node point to TOP.
  •  Finally, make the newNode as TOP.

Algorithm_push()

if (TOP == NULL)
newNode -> next = NULL
else
newNode -> next = TOP

pop()

  • Check whether stack is empty (top == NULL).
  • If it is empty, then display "EMPTY STACK"
  • If it is not empty, then create a temporary node and set it to TOP.
  • Print the data of TOP.
  • Make TOP to point to the next node.
  • Delete the temporary node.

Algorithm_pop()

if TOP == NULL
print "EMPTY STACK"
else
create a temporary node, temp = top
print TOP -> data
TOP = TOP -> next
free(temp)

Now, let us see a program to see linked list implementation of a stack.

C program to implement stacks using linked list

#include<stdio.h>
#include<stdlib.h>

/* Structure to create a node with data and pointer */

struct Node
{
int data;
struct Node *next;
}*top = NULL; // Initially the list is empty

void push(int);
void pop();
void display();

int main()
{
int choice, value;
printf("\nIMPLEMENTING STACKS USING LINKED LISTS\n");
while(1){
printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");
printf("\nEnter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("\nEnter the value to insert: ");
scanf("%d", &value);
push(value);
break;

case 2: pop();
break;

case 3: display();
break;

case 4: exit(0);
break;

default: printf("\nInvalid Choice\n");
}}}

void push(int value)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value; // get value for the node
if(top == NULL)
newNode->next = NULL;
else
newNode->next = top; // Make the node as TOP
top = newNode;
printf("Node is Inserted\n\n");
}

void pop()
{
if(top == NULL)
printf("\nEMPTY STACK\n");
else{
struct Node *temp = top;
printf("\nPopped Element : %d", temp->data);
printf("\n");
top = temp->next; // After popping, make the next node as TOP
free(temp);
}}

void display()
{
// Print the stack
if(top == NULL)
printf("\nEMPTY STACK\n");
else
{
printf("The stack is \n");
struct Node *temp = top;
while(temp->next != NULL){
printf("%d--->",temp->data);
temp = temp -> next;
}
printf("%d--->NULL\n\n",temp->data);
}}



OUTPUT

Pushing elements into the stack

stack using linked list push

 

Popping elements from the stack

stack using linked list pop

POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error