Queue Class Implementation In C++

Filed Under: C++
Queue Class Implementation In C

In this article, we will learn about the template queue class in C++. We will start by discussing queues, and their basic properties and applications of queues in real-life. Later we will discuss the C++ code featuring a template queue class and its working principle. So without any further delay let’s start learning this new data structure.

What Is A Queue?

A queue is simply a data structure that works on the FIFO(First In First Out) principle. This principle says that the first element to enter the queue is the first one to be popped out.

A ticket counter is a much more intuitive example to understand the function of queues. The person who comes first buys the tickets earlier than others.

Real-Life Applications Of Queues

Queues are used very frequently in our lives. Let’s consider some of the most common use-cases of queues.

  • All the client-handling systems are based on queues. Whenever a clients request some services, we use a queue to store and process the data, and the requested services are provided on a first come first serve basis.
  • Popular social media platforms use queues to store various messages and posts sent and received by the users. These posts and messages appear in the ascending order of time of posting or sending.
  • The schedulers in an operating system rely heavily on queues to maintain simultaneous process management and ensure the best performance.
  • Very similar to cpu schedulers, there are disk schedulers, these also use the concept of queues to manage disk data.
Job Scheduler
Job Scheduler

Template Queue Class Implementation In C++

Enough of theory, let’s learn how to implement a template queue class on your own. We will start by looking at the basic structure of a template queue class. The advantage of coding a template class is that we can use any generic data type with a template class.

Properties Of Queues

  • Random access is not allowed
  • Only the access to the front most element is allowed
  • Insertion will take place at the end
  • Deletion takes place from the front

Data Members And Member Functions

Though we can develop a queue using various different data structures like an array, vector, a stack but in this article, we will do this using a linked list. For this purpose, we will also use the STL(Standard Template Library) list container.

Our queue class will consist of two data members.

  • list <T> l: It will strore the data inserted into the queue
  • int cs: This variable denotes the current size of the list

Let’s move to the member functions of the queue class.

  • Queue(): It is the default constructor of the class. This function will initialize the value of current size with zero.
  • bool is_empty(): Checks if the queue is empty or not.
  • void push(T data): Inserts an element at the end of the queue(LIFO property).
  • void pop(): Deletes the element at the front.
  • T get_front(): Returns the element at the front.

Queue()

Queue(): cs(0) {}

bool is_empty()

        bool is_empty()
        {
                return cs == 0;
        }

void push(T data)

        void push(T data)
        {
                l.push_back(data);
                cs += 1;
                return;
        }

void pop()

        void pop()
        {
                if(cs == 0)
                        return;
                l.pop_front();
                cs--;
                return;
        }

T get_front()

        T get_front()
        {
                return l.front();
        }

Program To Demonstrate The Working Of Queues

#include <iostream>
#include <list>

using namespace std;

// declaring a template class
// with the template data type as T
template <typename T>
class Queue
{
	// this list will store the data
	// note that declaring data members
	// as private makes the list
	// not accessible to scopes outside
	// the class object
	// hence random access is invoked
	list <T> l;
	// this variable denotes the
	// current size of the queue
	int cs;
public:
	// default constructor
	Queue(): cs(0) {}

	bool is_empty()
	{
		return cs == 0;
	}

	void push(T data)
	{
		l.push_back(data);
		cs += 1;
		return;
	}

	// first we will check if the
	// queue is already empty or not
	// and then proceed accordingly
	void pop()
	{
		if(cs == 0)
			return;
		l.pop_front();
		cs--;
		return;
	}

	// function to return the element
	// at the front of the queue
	T get_front()
	{
		return l.front();
	}
};

template <typename T>
void print_queue(Queue <T> q)
{
	cout << "The Queue Is:" << endl;
	cout << "First <-- ";
	while(!q.is_empty())
	{
		cout << q.get_front() << " <-- ";
		q.pop();
	}
	cout << " <-- Last" << endl << endl;
}

int main()
{
	Queue <string> waiting_list;

	cout << "Enter the elements and type |done| to stop" << endl;

	while(true)
	{
		string ele;
		cin >> ele;

		if(ele == "done")
			break;
		waiting_list.push(ele);
	}

	print_queue(waiting_list);

	cout << "Let's empty the queue by popping elements one by one" << endl;

	while(!waiting_list.is_empty())
	{
		cout << "Deleting: " << waiting_list.get_front() << endl;
		waiting_list.pop();
		print_queue(waiting_list);
	}

	return 0;
}
Queue Program Code
C++ Queue Program Code

Output

Queue Program Output
C++ Queue Program Output

Conclusion

Let’s conclude this article by recalling what we learned from today’s article. We started by discussing queues, then we moved towards some real-life applications of queues. Later we discussed the structure and member functions of a queue class. In the end, we developed a C++ program to demonstrate some common functions of our template queue class.

References

To read more about queues and lists you can refer to the following website.

https://www.journaldev.com/55647/linked-lists-cpp

https://en.cppreference.com/w/cpp/container/queue

close
Generic selectors
Exact matches only
Search in title
Search in content