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
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
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;
}
This comment has been removed by a blog administrator.
Easily understandable one. Thanks for the Code
This comment has been removed by a blog administrator.