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