DS Menu

Stacks using linkedlist

Stack Implementation Using an Linked List

Initialize the Stack

The Stack structure has a top pointer, which is initialized to null

Pseudocode


struct node
    int data
    struct node next

struct node top := NULL

Push Operation

Adds a new element to the top of the stack. A new node is created with the given data, and it's placed at the beginning of the linked list, updating the top pointer.

Pseudocode

// Add an item to the stack
function push(data):
    newNode = new Node(data)
    newNode.next := top
    top = newNode

Pop Operation

Removes and returns the top element of the stack. It checks if the stack is empty to avoid underflow. The top pointer is then updated to the next node in the list.

Pseudocode

// Remove an item from the stack
function pop():
    if top = null
        display "Stack Underflow"
        return null
    else:
        poppedNode := top
        top := top.next
        return poppedNode.data

Peek Operation

Returns the top element of the stack without removing it. This operation checks if the stack is empty before returning the data of the top node.

Pseudocode

// Get the top item of the stack without removing it
function peek():
    if top = null
        display "Stack is empty"
        return null
    else:
        return top.data

C Program to implement Stack using Linked List

Program

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

struct node{
    int data;
    struct node *next;
}*head=NULL;

struct node *create(int value)
{
    struct node *temp;
    temp=(struct node*)malloc(sizeof(struct node));
    temp->data=value;
    temp->next=NULL;
    return temp;
}

void push(int value)
{
    struct node *newnode;
    newnode=create(value);
    if(head==NULL)
    {
        head=newnode;
    }
    else
    {
        newnode->next=head;
        head=newnode;
    }
}

void pop()
{
    struct node *temp;
    if(head==NULL)
    {
        printf("deletion is not possible");
    }
    else
    {
        temp=head;
        head=head->next;
        free(temp);
    }
}

void show()
{
    struct node *temp;
    if(head==NULL)
    {
        printf("list is empty");
    }
    else
    {
        temp=head;
        while(temp!=NULL)
        {
            printf("%d\n",temp->data);
            temp=temp->next;
        }
    }
}

void main()
{
    int ch,pos,value;
    do
    {
        printf("\n1.push\n2.pop end\n3.show\n4.exit\n");
        printf("enter your choice:");
        scanf("%d",&ch);
        switch(ch)
        {
        case 1: printf("enter the value:");
                scanf("%d",&value);
                push(value);
                break;
        case 2: pop();
                break;
        case 3: show();
                break;
        case 4:break;
        default: printf("\nyour choice is wrong!.. ");
        }
    }while(ch!=4);
}

Next Topic :Queues using array