Stack and Queue Implementation of Linked List in C++

Please refer to this link for more detail explanation.

(A) Stack Implementation of Linked list
Algorithm

1. Declare and initialize necessary variables such as struct node *top, *p, top = NULL
2. For push operation,
– check for memory full
if((p=(nodetype*) malloc (sizeof(nodetype))) == NULL)
print “Memory Exhausted”
Else
-take data to be inserted say x
-Create an empty node p and assign data x to its info field
i.e. p->info = x;
p->next = NULL
if(top!=NULL)
p->next = top
3. For next push operation, goto step 2.
4. For pop operation,
if top = NULL
print “stack is empty”
else
-temp = top
-top = top->next
-display popped item as top->info
-delete temp
5. For next pop operation goto step 4

Source Code

#include<iostream>
#include<cstdlib>

#include<malloc.h>

#include<conio.h>


using namespace std;


struct node{

    int info;

    struct node *next;

};


class stack{

    struct node *top;

    public:

        stack();

        void push();

        void pop();

        void display();

};


stack::stack(){

    top = NULL;

}


void stack::push(){

    int data;

    struct node *p;

    if((p=(node*)malloc(sizeof(node)))==NULL){

        cout<<"Memory Exhausted";

        exit(0);

    }

    cout<<"Enter a Number to insert:";

    cin>>data;

    p = new node;

    p->info = data;

    p->next = NULL;

    if(top!=NULL){

        p->next = top;

    }

    top = p;

    cout<<"\nNew item inserted"<<endl;

}


void stack::pop(){

    struct node *temp;

    if(top==NULL){

        cout<<"\nThe stack is Empty"<<endl;

    }else{

        temp = top;

        top = top->next;

        cout<<"\nThe value popped is "<<temp->info<<endl;

        delete temp;

    }

}


void stack::display(){

    struct node *p = top;

    if(top==NULL){

        cout<<"\nNothing to Display\n";

    }else{

        cout<<"\nThe contents of Stack\n";

        while(p!=NULL){

            cout<<p->info<<endl;

            p = p->next;

        }

    }

}


int main(){

    stack s;

    int choice;

    do{

        cout<<"\nEnter your choice:";

        cout<<"\n1. PUSH\n2. POP\n3. DISPLAY\n4. EXIT\n";

        cin>>choice;

        switch(choice){

            case 1:

                s.push();

                break;

            case 2:

                s.pop();

                break;

            case 3:

                s.display();

                break;

            case 4:

                exit(0);

                break;

            default:

                cout<<"Invalid Choice";

                break;

        }

    }while(choice);

    getch();

    return 0;

}

(B) Queue Implementation of Linked List

Algorithm

1. Declare and initialize necessary variables such as struct node *front, *rear etc
2. For enqueue operation,
-take input data to be inserted
-create an empty node and assign data to its into field
i.e. p->info=data
p->next = NULL
if front = NULL
front = p
else
rear->next = p
-rear = p
3. For next enqueue operation, goto step 2
4. For dequeue operation,
if front = NULL
print “Queue is empty”
else
-create a node pointer temp
-temp = front
-front = front->next
-display dequeued item as temp->data
-delete temp
5. For dequeue of next data item, goto step 4

Source Code

#include<iostream>

#include<cstdlib>


using namespace std;

struct node{

    int info;

    struct node *next;

};


class Queue{

    private:

        node *rear;

        node *front;

    public:

        Queue();

        void enqueue();

        void dequeue();

        void display();

};

Queue::Queue(){

    rear = NULL;

    front = NULL;

}

void Queue::enqueue(){

    int data;

    node *temp = new node;

    cout<<"Enter the data to enqueue: ";

    cin>>data;

    temp->info = data;

    temp->next = NULL;

    if(front == NULL){

        front = temp;

    }else{

        rear->next = temp;

    }

    rear = temp;

}


void Queue::dequeue(){

    node *temp = new node;

    if(front == NULL){

        cout<<"\nQueue is Emtpty\n";

    }else{

        temp = front;

        front = front->next;

        cout<<"The data Dequeued is "<<temp->info;

        delete temp;

    }

}


void Queue::display(){

    node *p = new node;

    p = front;

    if(front == NULL){

        cout<<"\nNothing to Display\n";

    }else{

        while(p!=NULL){

            cout<<endl<<p->info;

            p = p->next;

        }

    }

}


int main(){

    Queue queue;

    int choice;

    while(true){

        cout<<"\n1.Enqueue\n2. Dequeue\n3. Display\n 4.Quit";

        cout<<"\nEnter your choice: ";

        cin>>choice;

        switch(choice){

            case 1:

                queue.enqueue();

                break;

            case 2:

                queue.dequeue();

                break;

            case 3:

                queue.display();

                break;

            case 4:

                exit(0);

                break;

            default:

                cout<<"\nInvalid Input. Try again! \n";

                break;

        }

    }

    return 0;

}
SHARE Stack and Queue Implementation of Linked List in C++

You may also like...

3 Responses

  1. Anonymous says:

    This comment has been removed by a blog administrator.

  2. joinwitraj says:

    Easily understandable one. Thanks for the Code

  3. Anonymous says:

    This comment has been removed by a blog administrator.

Leave a Reply

Your email address will not be published.

Share