What is Queue, which we have discussed previously. besides, we also discussed about stack and its implementation, see-here». In this lesson we will talk about Queue Implementation based on array. Before going through the main topic, we will review about queue and C plus plus Queue interface.

Queue is a fundamental Data Structure, which is closely related to stack, except for an element removes or inserts in Queue according to the principle * first-in-first-out* (FIFO). We usually say that element enter in the Queue at rear, and out or removed from the front. Queue as ADT defines a container that keeps element in a sequence. We can access or delete an element in a queue to the first element, which refers to as

**. It is possible to insert an element at the end of sequence, which is the**

*front**of the queue.*

**rear**The Queue as abstract data type (ADT) supports following operation: ** enqueue(e)** – insert an element e at the rear of the queue.

*– Removes element at the front of the queue. an error occurs if the queue is empty. front() – returns a reference to the front element. An error occurs if the queue is empty. Additionally, Queue also supports the following member function:*

**dequeue()****– returns the number of element in the queue.**

*size()**– returns true if the queue is empty, otherwise false.*

**empty()**## The STL Queue

The Standard Template Library (STL) provides a method for queue implementation. In order to declare an object of type queue, it is necessary to first include definition file, which is “**queue**“. As with STL vector, the class queue is part of std namespace. Therefore, it is necessary either to use “* std::queue*“, or provide appropriate “

*” statement. For example the code bellow declares a queue of integers:*

**using**[cpp]

#include <queue>

using std::queue; // make queue accessible

queue<int> myQueue; // a queue of integers

[/cpp]

As with instances of STL vectors and stacks, an STL queue dynamically resizes itself as new elements are added.

STL queue supports roughly the same operators as our interface, but syntax and semantics are slightly different. * size():* Return the number of elements in the queue.

*Return true if the queue is empty and false otherwise.*

**empty()****:***Enqueue e at the rear of the queue.*

**push(e):***Dequeue the element at the front of the queue.*

**pop():***Return a reference to the element at the queue’s front.*

**front():***Return a reference to the element at the queue’s rear.*

**back():**Unlike our queue interface, the STL queue provides access to both the front and back of the queue. Similar to the STL stack, the result of applying any of the operations front, back, or pop to an empty STL queue is undefined. Unlike

our interface, no exception is thrown, but it may very likely result in the program aborting. It is up to the programmer to be sure that no such illegal accesses are attempted.

## Cpp Queue Interface

An interface for Cpp queue ADT is as in the code fragment below. The queues base element type E, which a user provides.

[cpp]

template <typename E>

class Queue { // an interface for a queue

public:

int size() const; // number of items in queue

bool empty() const; // is the queue empty?

const E& front() const throw(QueueEmpty); // the front element

void enqueue (const E& e); // enqueue element at rear

void dequeue() throw(QueueEmpty); // dequeue element at front

};

[/cpp]

Note that the **size** and **empty** functions have the same meaning as their counterparts in the Stack ADT. These two member functions and **front** are known as accessor functions, for they return a value and do not change the contents of the data structure. Also note the use of the exception **QueueEmpty** to indicate the error state of an empty queue. The member functions **size**, **empty**, and **front** are all declared to be **const**, which informs the compiler that they do not alter the contents of the queue. Note that the member function **front** returns a constant reference to the **top** of the queue.

An error condition occurs when calling either of the functions **front** or **dequeue** on an empty queue. This is signaled by throwing an exception **QueueEmpty**, which is defined in the class **QueueEmpty**.

[cpp]

class QueueEmpty : public RuntimeException { public:

QueueEmpty(const string& err) : RuntimeException(err) { }

};

[/cpp]

## Simple Array based Queue Implementation

We present a simple realization of a queue by means of an array, **Q**, with capacity * N*, for storing its elements. The main issue with queue implementation is deciding how to keep track of the

**front**and

**rear**of the queue.

In particular, let Q[0] be the front of the queue, and have the queue grow from there. But this is not a efficient solution, because it requires we move all the element forward one array cell each time we perform a **dequeue** operation. Such queue implementation would therefore require Θ(n) time to perform the **dequeue** function. Here n this the current number of element in the queue. So, if we want to achieve constant time for each queue function, we need a different approach.

## Using array in circular way | Queue Implementation

To avoid moving object once they are placed in Array, Q, we define three variable, ** p**,

*, and*

**q***. THose have the following meaning.*

**n**is the index of the cell of**p****Q**storing the front of the queue. If the queue is non-empty, the dequeue operation can remove the index of the element.is an index of the cell of**q****Q**following the rear of the queue. If queue is not full, this is the index an enqueue operation insert an element in the queue.is the current number of element in the queue.**n**

Initially we set * n=0*, and

**, indicating an empty queue. When we**

*p = q = 0**an element from the*

**dequeue***of the queue, we decrement*

**front***and increment*

**n***to the next cell in*

**p***. Likewise, when we*

**Q***an element, we increment*

**enqueue***and increment*

**q***. This allow us to implement*

**n****and**

*enqueue**function in constant time.*

**dequeue**Nonetheless, there is still a problem with this approach. Consider, for example, what happens if we repeatedly * enqueue* and

*a single element*

**dequeue***N different*

*times*. We would have

*. If we were then to try to insert the element just one more time, we would get an array-out-of-bounds error, even though there is plenty of room in the queue in this case. To avoid this problem and be able to utilize all of the array*

**p = q = N***, we let the*

**Q****and**

*p**indices “wrap around” the end of*

**q***. That is, we now view*

**Q****as a “**

*Q**” that goes from*

**circular array***to*

**Q[0]***and then immediately back to*

**Q[N −1]***again.*

**Q[0]**## Using the Modulo Operator to Implement a Circular Array | Queue Implementation

Implementing this circular view of * Q* is actually pretty easy. Each time we increment

*or*

**p***, we simply need to compute this increment as “*

**q***mod*

**( p +1)***” or “*

**N***mod*

**(q +1)***,” respectively, where the operator “*

**N***” is the modulo operator. This operator is computed for a positive number by taking the remainder after an integral division.*

**mod***For example*, 48 divided by 5 is 9 with remainder 3, so 48 mod 5 = 3. Specifically, given integers x and y, such that x ≥ 0 and y > 0, x mod y is the unique integer 0 ≤

*< y such that x = my +*

**q****q**, for some integer m.

Recall that C++ uses “%” to denote the modulo operator.

We present an algorithm of our queue implementation in Code Fragment bellow. Note that we have introduced a new exception, QueueFull, to signal that no more elements can be inserted in the queue. Our implementation of a queue by means of an array is similar to that of a stack.

The array-based queue implementation is quite efficient. All of the operations of the queue ADT needs * O(1)* time to perform.

Algorithm * size()*:

*n*

**return**Algorithm

**empty():***(n = 0)*

**return**Algorithm

**front():**if

*then*

**empty()**throw

*exception*

**QueueEmpty**

**return****Q[ p ]**Algorithm

**dequeue():**if

*then*

**empty()**throw

*exception*

**QueueEmpty**p ←( p +1) mod N

n = n−1

Algorithm

**enqueue(e):**if

*=*

**size()***then*

**N**throw

**QueueFull**exception

*←e*

**Q[q]**q←(q+1) mod N

n = n+1

the only real disadvantage of the array-based queue implementation is that we artificially set the capacity of the

queue to be some number * N*. In a real application, we may actually need more or less queue capacity than this, but if we have a good estimate of the number of elements that will be in the queue at the same time, then the array-based queue implementation is quite efficient.

This article I chose from the book Data Structures and Algorithms in C++ by by Michael T. Goodrich, which is really a great book to study data structure. I recommend you to definitely check it out.