Stack using linked list

 

What is a Stack?

• A stack is a linear data structure that follows the Last In First Out (LIFO) principle.

• That means:
  ➔ The last element inserted is the first one to be removed.

• Example:
  Think of a pile of plates —
  You add a plate on top, and you remove a plate from the top.

Stack Operations

Operation	Meaning
Push	Add an element on the top of the stack
Pop	Remove the top element
Peek	View the top element without removing
isEmpty	Check whether the stack is empty

How to Implement a Stack using Linked List

Instead of using an array (fixed size), we can use a linked list where each node contains:

• The data part.

• The pointer to the next node.

And we use a pointer top to always point to the topmost node.

Structure of a Node

In C:

struct Node {
    int data;
    struct Node* next;
};

---

Algorithms

1. Initialize the Stack

Set top = NULL

---

2. Push Operation

1. Create a new node.
2. Assign data to the new node.
3. Set newNode->next = top.
4. Set top = newNode.

---

3. Pop Operation

1. If top == NULL
     Output "Stack Underflow"
     Exit
2. Else
     Set temp = top
     Store temp->data into poppedValue
     Move top to top->next
     Free temp
     Return poppedValue

---

4. Peek Operation

1. If top == NULL
     Output "Stack is empty"
     Exit
2. Else
     Output top->data

---

Advantages of Stack Using Linked List

• Dynamic size (no fixed limit).

• Efficient use of memory (no unused space).

• Flexible to grow and shrink at runtime.

C Program Stack using linked list

#include<stdio.h>

#include<conio.h>

#include <stdlib.h>

struct Node

{

 int data;

 struct Node *next;

};

struct Node *top=NULL;

void push(int value) {

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    newNode->data = value;

    newNode->next = top;

    top = newNode;

}

int pop() {

    if (top == NULL) {

        printf("Stack is empty.\n");

        return -1;  // or any value to indicate an error

    }

    int poppedValue = top->data;

    struct Node* temp = top;

    top = top->next;

    free(temp);

    return poppedValue;

}

void displayStack() {

    if (top == NULL) {

        printf("Stack is empty.\n");

    } else {

        struct Node* temp = top;

        printf("Stack content:\n");

        while (temp != NULL) {

            printf("%d-->", temp->data);

            temp = temp->next;

        }

        printf("NULL\n");

    }

}

void main()

{

 int ch;

 

 do

 {

  printf("\nMenu\n----\n1. Push\n2. Pop\n3.display\n4. Exit");

  printf("\nEnter the choice:");

  scanf("%d",&ch);

  switch(ch)

  {

   case 1:

        printf("Enter the data to push:");

        int data;

        scanf("%d",&data);

        push(data);

        displayStack();

        break;

   case 2:

        int rv;

        rv=pop();

        if(rv!=-1) printf("Popped Value is:%d\n",rv);

        displayStack();

        break;

   case 3:

        displayStack();

        break;

   case 4:

        exit(0);

   default:

        printf("There is no such operation:");

  }

 }

 while(1);

}