fork download
copy 
  1. #include <iostream>
  2.  
  3. // Define the maximum capacity for the queue.
  4. #define MAX_SIZE 5
  5.  
  6. /**
  7.  * @class LinearQueue
  8.  * @brief Implements a basic Queue data structure using a fixed-size array.
  9.  * * Follows the First-In, First-Out (FIFO) principle.
  10.  * * This implementation is simpler but suffers from space inefficiency 
  11.  * as the 'front' index keeps moving forward.
  12.  */
  13. class LinearQueue {
  14. private:
  15.     // Array to store queue elements
  16.     int arr[MAX_SIZE]; 
  17.  
  18.     // Index of the front element (where dequeue happens)
  19.     int front; 
  20.  
  21.     // Index of the rear element (where enqueue happens)
  22.     int rear; 
  23.  
  24. public:
  25.     /**
  26.      * @brief Constructor for the LinearQueue.
  27.      */
  28.     LinearQueue() {
  29.         // Initialize front and rear to -1 to signify an empty queue.
  30.         front = -1; 
  31.         rear = -1; 
  32.     }
  33.  
  34.     /**
  35.      * @brief Checks if the queue is empty.
  36.      * @return true if the queue is empty, false otherwise.
  37.      */
  38.     bool isEmpty() const {
  39.         // The queue is empty when both front and rear are -1
  40.         return front == -1;
  41.     }
  42.  
  43.     /**
  44.      * @brief Checks if the queue is completely full.
  45.      * @return true if the queue is full, false otherwise.
  46.      */
  47.     bool isFull() const {
  48.         // The queue is full when the rear pointer reaches the last index (MAX_SIZE - 1)
  49.         return rear == MAX_SIZE - 1;
  50.     }
  51.  
  52.     /**
  53.      * @brief Adds an element to the rear of the queue (Enqueue).
  54.      * @param data The integer value to be inserted.
  55.      */
  56.     void enqueue(int data) {
  57.         if (isFull()) {
  58.             std::cout << "ERROR: Queue Overflow! Cannot enqueue element " << data << ". Queue is full.\n";
  59.             return;
  60.         }
  61.  
  62.         if (isEmpty()) {
  63.             // If the queue was empty, set front to 0
  64.             front = 0;
  65.         }
  66.  
  67.         // Always increment rear and insert the new element
  68.         rear++;
  69.         arr[rear] = data;
  70.         std::cout << "Enqueued: " << data << " to the queue.\n";
  71.     }
  72.  
  73.     /**
  74.      * @brief Removes and returns the element from the front of the queue (Dequeue).
  75.      * @return The integer value removed from the queue.
  76.      */
  77.     int dequeue() {
  78.         if (isEmpty()) {
  79.             std::cout << "ERROR: Queue Underflow! Cannot dequeue element. Queue is empty.\n";
  80.             return -1; // Indicate error
  81.         }
  82.  
  83.         int dequeuedValue = arr[front];
  84.         std::cout << "Dequeued: " << dequeuedValue << " from the queue.\n";
  85.  
  86.         if (front == rear) {
  87.             // If the last element is removed, reset the queue to empty state
  88.             front = -1;
  89.             rear = -1;
  90.         } else {
  91.             // Move front forward (this is where space is 'wasted' in linear queue)
  92.             front++;
  93.         }
  94.  
  95.         return dequeuedValue;
  96.     }
  97.  
  98.     /**
  99.      * @brief Utility function to display the current elements in the queue.
  100.      */
  101.     void display() const {
  102.         if (isEmpty()) {
  103.             std::cout << "Queue is currently empty.\n";
  104.             return;
  105.         }
  106.  
  107.         std::cout << "Current Queue (Front -> Rear): ";
  108.         for (int i = front; i <= rear; i++) {
  109.             std::cout << arr[i] << (i == rear ? "" : " -> ");
  110.         }
  111.         std::cout << "\n";
  112.     }
  113. };
  114.  
  115. /**
  116.  * @brief Main function to demonstrate the LinearQueue class functionality.
  117.  */
  118. int main() {
  119.     LinearQueue q;
  120.  
  121.     std::cout << "--- Initial State ---\n";
  122.     std::cout << "Is Empty: " << (q.isEmpty() ? "True" : "False") << "\n";
  123.  
  124.     // 1. Enqueue Operations
  125.     std::cout << "\n--- Enqueuing elements ---\n";
  126.     q.enqueue(100); // front=0, rear=0
  127.     q.enqueue(200); // front=0, rear=1
  128.     q.enqueue(300); // front=0, rear=2
  129.     q.display();
  130.  
  131.     // 2. Dequeue Operations
  132.     std::cout << "\n--- Dequeuing elements (FIFO) ---\n";
  133.     q.dequeue(); // 100 is removed, front=1, rear=2
  134.     q.dequeue(); // 200 is removed, front=2, rear=2
  135.     q.display();
  136.  
  137.     // 3. Overflow and Inefficiency Demonstration (MAX_SIZE is 5)
  138.     std::cout << "\n--- Demonstrating Fullness and Inefficiency ---\n";
  139.     q.enqueue(400); // front=2, rear=3
  140.     q.enqueue(500); // front=2, rear=4 (Queue is now full)
  141.  
  142.     q.display();
  143.     std::cout << "Is Full: " << (q.isFull() ? "True" : "False") << "\n";
  144.  
  145.     // 4. Overflow Test
  146.     q.enqueue(600); // Should fail due to overflow
  147.  
  148.     // Note: The first two array slots (index 0 and 1) are empty 
  149.     // but cannot be reused because 'rear' cannot decrement. This is the 
  150.     // fundamental inefficiency of the simple linear array queue.
  151.  
  152.     // 5. Empty the queue
  153.     std::cout << "\n--- Emptying the queue ---\n";
  154.     q.dequeue(); 
  155.     q.dequeue(); 
  156.     q.dequeue(); // 500 is removed. front=-1, rear=-1
  157.  
  158.     // 6. Underflow Test
  159.     q.dequeue(); // Should fail due to underflow
  160.  
  161.     std::cout << "Is Empty: " << (q.isEmpty() ? "True" : "False") << "\n";
  162.  
  163.     return 0;
  164. }
  165.  
  166.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
--- Initial State ---
Is Empty: True

--- Enqueuing elements ---
Enqueued: 100 to the queue.
Enqueued: 200 to the queue.
Enqueued: 300 to the queue.
Current Queue (Front -> Rear): 100 -> 200 -> 300

--- Dequeuing elements (FIFO) ---
Dequeued: 100 from the queue.
Dequeued: 200 from the queue.
Current Queue (Front -> Rear): 300

--- Demonstrating Fullness and Inefficiency ---
Enqueued: 400 to the queue.
Enqueued: 500 to the queue.
Current Queue (Front -> Rear): 300 -> 400 -> 500
Is Full: True
ERROR: Queue Overflow! Cannot enqueue element 600. Queue is full.

--- Emptying the queue ---
Dequeued: 300 from the queue.
Dequeued: 400 from the queue.
Dequeued: 500 from the queue.
ERROR: Queue Underflow! Cannot dequeue element. Queue is empty.
Is Empty: True
https://ideone.com/32sFIb
language:
C++ (gcc 8.3)
created:
14 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!