Stack and Queue Implementation of Linked List in C++

(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;
}