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
 
#include
 
#include
 
#include
 
 
 
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){
 
        coutMemory Exhausted";
 
        exit(0);
 
    }
 
    coutEnter 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"
 
}
 
 
 
void stack::pop(){
 
    struct node *temp;
 
    if(top==NULL){
 
        cout\nThe stack is Empty"
 
    }else{
 
        temp = top;
 
        top = top->next;
 
        cout\nThe value popped is "info
 
        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){
 
            coutinfo
 
            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:
 
                coutInvalid 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
 
#include
 
 
 
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;
 
    coutEnter 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;
 
        coutThe data Dequeued is "info;
 
        delete temp;
 
    }
 
}
 
 
 
void Queue::display(){
 
    node *p = new node;
 
    p = front;
 
    if(front == NULL){
 
        cout\nNothing to Display\n";
 
    }else{
 
        while(p!=NULL){
 
            coutinfo;
 
            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;
 
}