Queue Implementation in C - JohnHau/mis GitHub Wiki

A queue is a linear data structure that serves as a container of objects that are inserted and removed according to the FIFO (First–In, First–Out) principle.

Queue has three main operations: enqueue, dequeue, and peek. We have already covered these operations and C implementation of queue data structure using an array and linked list. In this post, we will cover queue implementation in C++ using class and STL.

The following queue implementation in C++ covers the following operations:

Enqueue: Inserts a new element at the rear of the queue. Dequeue: Removes the front element of the queue and returns it. Peek: Returns the front element present in the queue without dequeuing it. IsEmpty: Checks if the queue is empty. IsFull: Checks if the queue is full. Size: Returns the total number of elements present in the queue. Practice this problem

Queue Implementation using an array:

#include #include using namespace std;

// Define the default capacity of a queue #define SIZE 1000

// A class to store a queue class Queue { int *arr; // array to store queue elements int capacity; // maximum capacity of the queue int front; // front points to the front element in the queue (if any) int rear; // rear points to the last element in the queue int count; // current size of the queue

public: Queue(int size = SIZE); // constructor ~Queue(); // destructor

int dequeue();
void enqueue(int x);
int peek();
int size();
bool isEmpty();
bool isFull();

};

// Constructor to initialize a queue Queue::Queue(int size) { arr = new int[size]; capacity = size; front = 0; rear = -1; count = 0; }

// Destructor to free memory allocated to the queue Queue::~Queue() { delete[] arr; }

// Utility function to dequeue the front element int Queue::dequeue() { // check for queue underflow if (isEmpty()) { cout << "Underflow\nProgram Terminated\n"; exit(EXIT_FAILURE); }

int x = arr[front];
cout << "Removing " << x << endl;

front = (front + 1) % capacity;
count--;

return x;

}

// Utility function to add an item to the queue void Queue::enqueue(int item) { // check for queue overflow if (isFull()) { cout << "Overflow\nProgram Terminated\n"; exit(EXIT_FAILURE); }

cout << "Inserting " << item << endl;

rear = (rear + 1) % capacity;
arr[rear] = item;
count++;

}

// Utility function to return the front element of the queue int Queue::peek() { if (isEmpty()) { cout << "Underflow\nProgram Terminated\n"; exit(EXIT_FAILURE); } return arr[front]; }

// Utility function to return the size of the queue int Queue::size() { return count; }

// Utility function to check if the queue is empty or not bool Queue::isEmpty() { return (size() == 0); }

// Utility function to check if the queue is full or not bool Queue::isFull() { return (size() == capacity); }

int main() { // create a queue of capacity 5 Queue q(5);

q.enqueue(1);
q.enqueue(2);
q.enqueue(3);

cout << "The front element is " << q.peek() << endl;
q.dequeue();

q.enqueue(4);

cout << "The queue size is " << q.size() << endl;

q.dequeue();
q.dequeue();
q.dequeue();

if (q.isEmpty()) {
    cout << "The queue is empty\n";
}
else {
    cout << "The queue is not empty\n";
}

return 0;

} Download Run Code

Output:

Inserting 1 Inserting 2 Inserting 3 The front element is 1 Removing 1 Inserting 4 The queue size is 3 Removing 2 Removing 3 Removing 4 The queue is empty

The time complexity of all the above queue operations is O(1).

Using std::queue:

C++’s STL provides a std::queue template class which is restricted to only enqueue/dequeue operations. It also provides std::list which has push_back and pop_front operations with LIFO semantics. Java’s library contains Queue interface that specifies queue operations.

#include #include using namespace std;

// Queue implementation in C++ using std::queue int main() { queue q;

q.push("A");        // Insert `A` into the queue
q.push("B");        // Insert `B` into the queue
q.push("C");        // Insert `C` into the queue
q.push("D");        // Insert `D` into the queue

// Returns the total number of elements present in the queue
cout << "The queue size is " << q.size() << endl;

// Prints the front of the queue (`A`)
cout << "The front element is " << q.front() << endl;

// Prints the rear of the queue (`D`)
cout << "The rear element is " << q.back() << endl;

q.pop();            // removing the front element (`A`)
q.pop();            // removing the next front element (`B`)

cout << "The queue size is " << q.size() << endl;

// check if the queue is empty
if (q.empty()) {
    cout << "The queue is empty\n";
}
else {
    cout << "The queue is not empty\n";
}

return 0;

} Download Run Code

Output:

The queue size is 4 The front element is A The rear element is D The queue size is 2 The queue is not empty