Programming Data Structure Queue Implementation Based on Array | STL Queue |...

Queue Implementation Based on Array | STL Queue | Cpp Queue Interface

-

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 front. It is possible to insert an element at the end of sequence, which is the rear of the queue.

The Queue as abstract data type (ADT) supports following operation: enqueue(e) – insert an element e at the rear of the queue. dequeue() – 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: size() – returns the number of element in the queue. empty() – returns true if the queue is empty, otherwise false.

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 “using” statement. For example the code bellow declares a queue of integers:

[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. empty(): Return true if the queue is empty and false otherwise. push(e): Enqueue e at the rear of the queue. pop(): Dequeue the element at the front of the queue. front(): Return a reference to the element at the queue’s front. back(): Return a reference to the element at the queue’s rear.

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, q, and n. THose have the following meaning.

  • p is the index of the cell of Q storing the front of the queue. If the queue is non-empty, the dequeue operation can remove the index of the element.
  • q is an index of the cell of 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.
  • n is the current number of element in the queue.

Initially we set n=0, and p = q = 0, indicating an empty queue. When we dequeue an element from the front of the queue, we decrement n and increment p to the next cell in Q. Likewise, when we enqueue an element, we increment q and increment n. This allow us to implement enqueue and dequeue function in constant time.

Nonetheless, there is still a problem with this approach. Consider, for example, what happens if we repeatedly enqueue and dequeue a single element N different times. We would have p = q = N. 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 Q, we let the p and q indices “wrap around” the end of Q. That is, we now view Q as a “circular array” that goes from Q[0] to Q[N −1] and then immediately back to Q[0] again.

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 p or q, we simply need to compute this increment as “( p +1) mod N” or “(q +1) mod N,” respectively, where the operator “mod” is the modulo operator. This operator is computed for a positive number by taking the remainder after an integral division. 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 ≤ q < y such that x = my + 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():
return n
Algorithm empty():
return (n = 0)
Algorithm front():
if empty() then
throw QueueEmpty exception
return Q[ p ]
Algorithm dequeue():
if empty() then
throw QueueEmpty exception
p ←( p +1) mod N
n = n−1
Algorithm enqueue(e):
if size() = N then
throw QueueFull exception
Q[q]←e
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.

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Latest Articles

Dictionaries | HashMap in Python | Working with Key-Values

Dictionaries in Python is similar to Hashmap comparing to other languages. It stores data as a key-value...

Hash Table | Indexing | Hashing Algorithm | Python Implementation

This article will talk about a high-level view of the Hash Table. As a programmer, this technique...

Eigenvector Eigenvalue | Linear Algebra Fundamentals

Eigenvector ($bar{v}$) in linear algebra is a non-zero vector (matrix) that doesn't change its direction during linear...

Pivot Table | Microsoft Excel | Create Data Insight Easily

Pivot table in microsoft Excel is an useful function that gives us a way to create insight...

Macro Function in Microsoft Excel | Automate Repetitive Task

This article we will talk about the Macro. It is a function in microsoft excel which basically...

SVD | Singular Value Decomposition | Machine Learning Fundamentals

Singular Value Decomposition or SVD is the general purpose useful tool in Numerical Linear Algebra for data...

Must read

Dictionaries | HashMap in Python | Working with Key-Values

Dictionaries in Python is similar to Hashmap...

Eigenvector Eigenvalue | Linear Algebra Fundamentals

Eigenvector ($bar{v}$) in linear algebra is a...

You might also likeRELATED
Recommended to you