RSS

Category Archives: Stacks, Queues and Linked Lists

PROGRAM TO DETECT THE PRESENCE OF A LOOP IN A LINKED LIST (FLOYD’S CYCLE FINDING ALGORITHM)

// THIS PROGRAM CHECKS FOR THE PRESENCE OF A LOOP IN A LINKED LIST (FLOYD'S CYCLE FINDING ALGORITHM)

#include <iostream>

using namespace std;

struct node
{
    int info;
    node *next;
};

bool looppresent(node *start);

int main()
{
    node *start;
    int i = 2;
    char wish = 'Y';
    start = new node;
    node *ptr;

    cout<<"Node 1: ";
    cin>>start->info;
    start->next = NULL;

    ptr = start;

    do
    {
        cout<<"\nNode "<<i<<": ";
        node *temp = new node;
        ptr->next = temp;
        ptr = temp;
        cin>>ptr->info;
        cout<<"\nContinue ??\n";
        cin>>wish;
        i++;
    }
    while(wish == 'Y' || wish == 'y');
    ptr->next = NULL;

    //uncomment the below line if you want to add a loop
    //ptr->next = start->next;

    if(looppresent(start) == true)
    {
        cout<<"\n Loop is present in the linked list\n\n";
    }
    else
    {
        cout<<"\n The linked list is loop free\n";
    }

    return 0;
}

bool looppresent(node *start)
{
    node *first, *second;
    first = second = start;
    second = first->next->next;

    while(first != NULL && second != NULL && first != second)
    {
        first = first->next;
        if(second->next == NULL || second ->next ->next == NULL)
            return false;
        second = second->next->next;
    }

    if(first == second)
        return true;
    else
        return false;
}

 

PROGRAM TO DELETE ALL THE ELEMENTS EQUAL TO AN ENTERED ELEMENT FROM THE STACK

// PROGRAM TO IMPLEMENT THE DELETE FUNCTIONALITY IN A STACK

#include <iostream>
#include <cstdlib>
#include <process.h>
#define size 10

using namespace std;

class stack{
	int data[size];
	int top;
	
	public:
		stack()
		{
			top = -1;
		}
		void push();
		void pop();
		void display();
		void del(int);
};

int main()
{
	stack s;
	char wish = 'Y';
	int choice;
	
	do{
		system("cls");
		cout<<"\nImplementation of Delete functionality in Stack....\n\n";
		cout<<"\nPlease enter a choice\n\n";
		cout<<"\n1. PUSH AN ELEMENT\n\n";
		cout<<"\n2. POP AN ELEMENT\n\n";
		cout<<"\n3. DISPLAY THE ELEMENTS OF STACK\n\n";
		cout<<"\n4. DELETE ALL THE ELEMENTS EQUAL TO A CERTAIN ELEMENT FROM THE STACK\n\n";
		cout<<"\n5. EXIT THE PROGRAM\n\n";
		cout<<"\n\nEnter your choice\t";
		cin>>choice;
		
		while(choice<1 || choice >5)
		{
			cout<<"\nInvalid choice.... Enter a valid one below\n\n";
			cout<<"Choice : \t";
			cin>>choice;
		}
		system("cls");
		int var;
		switch(choice)
		{
			case 1: s.push();
					cout<<"\n\nThe stack staus is \n\n";
					s.display();
					break;
			
			case 2: s.pop();
					cout<<"\n\nThe stack staus is \n\n";
					s.display();
					break;
			
			case 3: cout<<"\n\nThe stack staus is \n\n";
					s.display();		
					break;
					
			case 4: cout<<"\n\nEnter the element all elements equal to which should be deleted from stack\n\n";
					cin>>var;
					s.del(var);
					cout<<"\n\nThe stack staus is \n\n";
					s.display();
					break;
					
			case 5: cout<<"\nEXITING FROM THE PROGRAM \n\n";
					exit(0);
					break;	
		}
		
		cout<<"\n\nDo any more operation? (Y/N)";
		cin>>wish;
		
		while(wish != 'y' && wish !='Y' && wish !='n' && wish != 'N')
		{
			cout<<"\n\nInvalid choice \n\n Please enter correct one below...\n";
			cout<<"\nChoice (Y/N): \t";
			cin>>wish;
		}
		
	}while(wish == 'y' || wish == 'Y');
	
	cout<<"\n\nThanks for coming.... Do come again. \n\n";
	cout<<"\nHave a nice day ahead :)";
	
	return 0;
}

void stack::push() 
{
	int element;
	if(top == size-1)
	{
		cout<<"\n\nERROR !!!!!   STACK OVERFLOW !!!!!!\n\n";
		exit(1);
	}
	else
	{
		top++;
		cout<<"\n\nEnter the element to be pushed:\t";
		cin>>element;
		data[top] = element;
	}
	
	cout<<"\n\nINSERTION SUCCESSFUL .....\n\n";
}

void stack::pop()
{
	if(top == -1)
	{
		cout<<"\n\nERROR !!!!!! STACK UNDERFLOW !!!!!!\n\n";
		exit(1);
	}
	else
	{
		int item = data[top];
		top--;
		cout<<"\n\nDeleted element is:\t "<<item;
	}
}

void stack::display()
{
	if(top == -1)
	cout<<"\n\nEMPTY !!!!!\n\n";
	else
	{
		for(int i = top; i >=0; i--)
		{
			if(i == top)
			{
				cout<<"Top -->  "<<data[i]<<'\n';
			}
			else
				cout<<"         "<<data[i]<<'\n';
		}                           
	}
}

void stack::del(int val)
{
	stack tempstack;
	
	for(;top>=0;)
	{
		if(data[top] == val)
		{
			top--;
		}
		else
		{
			//push into temp stack
			tempstack.top++;
			tempstack.data[tempstack.top] = data[top]; 
			top--;
		}
	}
	
	while(tempstack.top>=0)
	{
		top++;
		data[top] = tempstack.data[tempstack.top];
		tempstack.top--;
	}
	
	cout<<"\n\nDeletion Successful !!!!!\n\n";
}
 
5 Comments

Posted by on March 29, 2016 in Stacks, Queues and Linked Lists

 

IMPLEMENTATION OF CIRCULAR QUEUE USING ARRAYS (2ND LOGIC)

// THIS PROGRAM IMPLEMENTS CIRCULAR QUEUE

#include <iostream>
#include <cstdlib>
#define size 4

using namespace std;

class queue{
	int front,rear;
	int q[size];
	
	public:
		queue()
		{
			front = rear = -1;
		}
		void insert();
		int deleteq();
		void display();
};

int main()
{
	queue q;
	int choice;
	char wish;
	
	do{
		system("cls");
		cout<<"\nIMPLEMENTING CIRCULAR QUEUE USING ARRAYS \n";
		cout<<"\nPLEASE ENTER A CHOICE\n";
		cout<<"\n1. INSERT AN ELEMENT\n";
		cout<<"\n2. DELETE AN ELEMENT\n";
		cout<<"\n3. SHOW QUEUE STATUS\n";
		cout<<"\n4. EXIT FROM THE PROGRAM\n\n\n";
		cin>>choice;
		while(choice <1 || choice > 4)
		{
			cout<<"\n\nInvalid choice\n";
			cout<<"\nPlease enter your choice again\n\n";
			cin>>choice;
		}
		
		int del;
		
			switch(choice)
			{
				case 1: q.insert();
						cout<<"\n\nThe queue after insertion is\n\n";
						q.display();
						break;
				case 2: del = q.deleteq();
						cout<<"\n\n'"<<del<<"'"<<" deleted from the queue\n\n";
						cout<<"\nUpdated queue status is\n\n";
						q.display();
						break;
				case 3: cout<<"\n\nThe queue status is \n\n";
						q.display();
						break;
				case 4: cout<<"\n\nEXITING FROM THE PROGRAM...\n\n";
						exit(0);
			}
			
	cout<<"\n\nDo any other operation?\n\n Press 'y' or 'Y' to continue. \n\nAny other option to exit\n\n";
	cin>>wish;
	}while(wish == 'Y' || wish == 'y');	
	
	cout<<"\nThanks!!! Do come again\n";
	
	return 0;
}

void queue::insert()
{
	int item;
	if((rear+1)%size == front)
	{
		cout<<"\nOverflow !!!!! Terminating.....";
		exit(1);
	}
	else if(front == -1 && rear == -1)
	{
		front = 0;
		rear = 1;
		cout<<"\nEnter the element to be inserted\n";
		cin>>item;
		q[front] = item;
		cout<<"\nInsertion Successful\n\n";
	}
	else
	{
		cout<<"\nEnter the element to be inserted \n";
		cin>>item;
		q[rear] = item;
		rear = (rear+1)%size;
		cout<<"\nInsertion Successful\n\n";
	}
}

int queue::deleteq()
{
	int item;
	if(front == rear)
	{
		cout<<"\nUnderflow!!!. Terminating....\n";
		exit(-1);
	}
	else
	{
		item = q[front];
		front = (front+1)%size;
		cout<<"\nDeletion Successful !!!\n\n";
	}
	
	return item;
}

void queue::display()
{
	int ctr = front;
	
	while(ctr != rear)
	{
		cout<<q[ctr]<<' ';
		ctr = (ctr+1)%size;
	}
}
 
 

PROGRAM TO MERGE TWO SORTED LINKED LISTS INTO A THIRD SORTED LINKED LIST

/* THIS PROGRAM MERGES TWO SORTED LINKED LISTS SUCH THAT THE SORTED LINKED LIST IS IN ASCENDING ORDER
  */

#include <iostream>
#include <process.h>

using namespace std;

struct node{
	int info;
	node *next;
};

class linkedlist{
	node *front;
	node *end;
	public:
		linkedlist()
		{
			front = end = NULL;
		}
		void add(int);
		node* retfront()
		{ return front;	}
};

node* mergelists(node *first, node *second);

int main()
{
	char wish = 'y';
	linkedlist first, second;
	
	cout<<"\nInput the first linked list's first element (ascending order)";
	
	int info;
	
	  while(wish == 'Y' || wish == 'y')
	  {
	  	cout<<"\nElement: \t";
	  	cin>>info;
	  	first.add(info);
	  	cout<<"\nAdd more? (Y/y)\n";
	  	cin>>wish;
	  }

	cout<<"\nInput the second linked list's first element (ascending order)\n";
	
	wish = 'Y';
	
		while(wish == 'y' || wish == 'Y')
		{
			cout<<"\nElement:\t";
			cin>>info;
			second.add(info);
			cout<<"\nAdd more? (Y/y)\n";
			cin>>wish;
		}
		
	cout<<"\nMerging the linked lists\n";
	
	node *newlist = mergelists(first.retfront(), second.retfront());
	
	cout<<"\nThe merged linked list is \n\n";
	
	while(newlist != NULL)
	{
		cout<<newlist->info;
		newlist = newlist->next;
		cout<<'\n';
	}
	
	return 0;
}

node * mergelists(node *first, node *second)
{
	linkedlist newlist;
	
	while(first != NULL && second != NULL)
	{
		if(first->info < second->info)
		{
			newlist.add(first->info);
			first = first->next;
		}
		else
		{
			newlist.add(second->info);
			second = second->next;
		}                                      
	}                                          
											
	if(first != NULL)
	{
		while(first != NULL)
		{
			newlist.add(first->info);
			first = first->next;
		}
	}
	else if(second != NULL)
	{
		while(second != NULL)
		{
			newlist.add(second->info);
			second = second->next;
		}
	}
	
	return newlist.retfront();
}

void linkedlist::add(int val)
{
	node *ptr = new node;
	
	if(ptr == NULL)
	{
		cout<<"\nError !!! No memory available !!!!\n";
		cout<<"\nAborting.....\n";
		exit(1);
	}
	
	ptr->info = val;
	ptr->next = NULL;
	
	if(front == NULL)
	{
		front = end = ptr;
	}
	else                    
	{                       
		end->next = ptr;
		end = ptr;
	}
}
 
 

PROGRAM TO IMPLEMENT CIRCULAR QUEUE USING LINKED LIST

// THIS PROGRAM IMPLEMENTS A CIRCULAR QUEUE USING A LINKED LIST

#include <iostream.h>
#include <conio.h>
#include <dos.h>
#include <process.h>

struct node
{
   int info;
   node *next;
};

class queue
{
   node *front;
   node *rear;

   public:
   void enqueue();
   void dequeue();
   void show();
   queue()
   {
      front = rear = NULL;
   }
   ~queue()
   {
      cout<<"\nQUEUE DESTROYED \n";
   }
};

void main()
{
   clrscr();

   char wish;
   int choice =  -1;

   queue q;

   do{
      clrscr();
      cout<<"\n        IMPLEMENTATION OF QUEUE USING LINKED LISTS \n\n\n";
      cout<<"\nCHOOSE AN OPERATION \n";
      cout<<"\n1. INSERT IN THE QUEUE (ENQUEUE) \n";
      cout<<"2. DELETE FROM THE QUEUE (DEQUEUE)\n";
      cout<<"3. SHOW THE QUEUE STATUS\n";
      cout<<"4. EXIT THE PROGRAM\n";
      cout<<"\n\nPLEASE ENTER YOUR CHOICE\n";
      cin>>choice;

	if(choice == 1)
	{
	   q.enqueue();
	   q.show();
	}
	else if(choice == 2)
	{
	   q.dequeue();
	   q.show();
	}
	else if(choice == 3)
	{
	   q.show();
	}
	else
	{
	   cout<<"\nTERMINATING...\n";
	   sleep(1);
	   exit(0);
	}
	cout<<"\n\n\nDO ANY MORE OPERATION? (Y/N) \n";
	cin>>wish;
   }
   while(wish == 'Y' || wish == 'y');

   cout<<"\nTHANKS!!!!. DO VISIT AGAIN\n";
   cout<<"\n\nPress any key to exit\n";
   getch();
}

void queue::enqueue()
{
   node *ptr = new node;
   clrscr();

   cout<<"\nPERFORMING ENQUEUE OPERATION \n\n";
   cout<<"\nENTER THE INFO PART OF NEW NODE\n";
   cin>>ptr->info;

   if(front == NULL)
   {
     front = rear = ptr;
     ptr->next = front;
   }
   else
   {
     rear->next = ptr;
     rear = ptr;
     rear->next = front;
   }

   cout<<"\n SUCCESSFUL\n";
}

void queue::dequeue()
{
   node *save;
   save = front;

   if(front == NULL)
   {
     cout<<"\nUNDERFLOW!!!\nNOTHING TO DELETE\n";
   }
   else if(front == rear)
   {
      front = rear = NULL;
      delete save;
      cout<<"\nDEQUE SUCCESSFUL\n\n\nMODIFIED QUEUE IS \n";
   }
   else
   {
    front = front->next;
    rear->next = front;
    delete save;
    cout<<"\nDEQUE SUCCESSFUL\n";
    cout<<"\n\nMODIFIED QUEUE IS \n";
   }
}

void queue::show()
{
   if(front == NULL)
    cout<<"\nQUEUE IS EMPTY \n";
   else
   {
    node *temp = front;
    cout<<"\nQUEUE STATUS IS \n\n";
    do
    {
	cout<<temp->info<<' ';
	temp = temp->next;
    }
    while(temp != front);
   }
}
 
Leave a comment

Posted by on December 17, 2015 in Stacks, Queues and Linked Lists

 

PROGRAM TO IMPLEMENT CIRCULAR QUEUE USING ARRAYS

// PROGRAM TO IMPLEMENT CIRCULAR QUEUE USING ARRAYS 

#include <iostream>
#define size 4
#include <process.h>

using namespace std;

class queue
{
	int arr[size];
	int front, rear;
	public:
		queue()
		{
		  front = rear = -1;
		}
		void insert();
		void del();
		void show();
};

int main()
{
	int choice = -1;
	char wish;
	queue myqueue;
	
	do
	{
	    cout<<"\n\n           IMPLEMENTING QUEUE USING ARRAYS              \n\n";
		cout<<"\n1. INSERT AN ELEMENT \n";
		cout<<"\n2. DELETE AN ELEMENT \n";
		cout<<"\n3. SHOW QUEUE STATUS \n";
		cout<<"\n4. EXIT\n";
	lb:	cout<<"\n\nPLEASE ENTER YOUR CHOICE\n";
		cin>>choice;
		
		switch(choice)
		{
			case 1:	myqueue.insert();
		   			break;
			case 2: myqueue.del();
					break;
			case 3: cout<<"\nQueue status is \n";
					myqueue.show();
					break;
			case 4: cout<<"\nTerminating...\n";
					exit(0);
		   default: cout<<"\nInvalid choice.... Enter correct one(1-4)\n";
		   			goto lb; 
		}
		
		cout<<"\n\nDo any more operation ? \n\n";
		cin>>wish;	
	}
	while(wish == 'Y' || wish == 'y');
	
	cout<<"\n\nThanks!!!!! Do come again..\n";
	return 0;
}

void queue::insert()
{
	if(rear == -1)
	{
		front = rear = 0;                       
	}											
	else if(front == 0 && rear <size-1  ||  front != 0  && rear <front-1 )
	{
	  rear++;
	}
	else if(front == 0 && rear == size-1  ||  rear == front-1)
	{
	   cout<<"\nQueue is full\n";
	   exit(0);
	}
	else
	{  
	 if(front >0  && rear == size-1)
	 {
	   rear = 0;
	 }
	}
	cout<<"\nInput the value you want to insert\n";
	int val;
	cin>>val;
	arr[rear] = val;
	cout<<"\nInsertion successful\n";
	cout<<"\nThe queue now is \n";
	show();
}

void queue::del()
{
	if(front == -1)
	{
	   cout<<"\nUnderflow!!!!Aborting....\n";
	   exit(0);
	}
	else if(front == rear)
	{
		front = rear = -1;
	}
	else if(front == size -1)
	{
	  front = 0;
	}
	else
	{
	  front++;
	}
	cout<<"\nDeletion successful\n";
	cout<<"\nQueue after deletion is \n";
	show();
}

void queue::show()
{
    if(front == -1)
    {
    	cout<<"\nempty\n";
	}
	else if(front == rear)
	{
		cout<<arr[front];
	}
	else if(front < rear)
	{
	      for(int i =front; i<=rear; i++)
	      cout<<arr[i]<<' ';
	}
	else 
	{
	     for(int i = front; i<size; i++)
	     cout<<arr[i]<<' ';
	     for(int i = 0; i<=rear; i++)
	     cout<<arr[i]<<' ';
	}
}
 
Leave a comment

Posted by on December 17, 2015 in Stacks, Queues and Linked Lists

 

PROGRAM TO IMPLEMENT STACK USING LINKED LISTS

// THIS PROGRAM IMPLEMENTS STACK USING LINKED LISTS

#include <iostream>
#include <process.h>

struct node
{
int info;
node *next;
}*top;

int main()
{
node *ptr, *save;
top = NULL;
char wish = 'y';
int choice,size;

do
{
std::cout<<"\nChoose an operation\n";
std::cout<<"\n\n1. Insertion\n";
std::cout<<"\n2. Deletion\n";
std::cout<<"\n3. Display\n";
std::cout<<"\nEnter your choice(1-3) \n";
std::cin>>choice;

switch(choice)
{
case 1: std::cout<<"\nInsert how many elements?\n";
std::cin>>size;
std::cout<<"\nEnter the element(s)\n";
for(int i = 0; i<size; i++)
{
ptr = new node;
save = top;
top = ptr;
top->next = save;
std::cin>>top->info;
}
std::cout<<"\nSuccessful\n";
break;
case 2: if(top == NULL)
{
std::cout<<"\nUnderflow!!!!\n";
std::cout<<"\nAborting...\n";
exit(0);
}
ptr = top;
top = ptr->next;
delete ptr;
break;
case 3: ptr = top;
std::cout<<"\nStack status is \n";
if(ptr ==NULL)
std::cout<<"\nStack is empty\n";
while(ptr != NULL)
{
std::cout<<ptr->info;
if(ptr == top)
std::cout<<" <-- (top)";
std::cout<<'\n';
ptr = ptr->next;
}
break;
default: std::cout<<"\nInvalid choice!!\nAborting...\n";
exit(0);
}
std::cout<<"\n\nPerform More operations(Y/N)??\n";
std::cin>>wish;
}while(wish == 'y' || wish == 'Y');

return 0;
}
 
Leave a comment

Posted by on November 21, 2015 in Stacks, Queues and Linked Lists