Understanding Queue with Array (UQA)


UQA:    SOLD



A queue is a collection of data where adding elements can only be done at one end (referred to as the tail/rear) and removing or retrieving elements is done at the other end (referred to as the head/front).

The queue operates on the First In First Out (FIFO) principle. This means that the order in which elements enter the queue is the same order in which they leave. Queues are common in everyday life. For instance, cars queuing at a toll gate or people waiting in line at a ticket counter form queues.

The first element that enters the queue will be the first one to leave. The operation to remove an element from a queue is called DEQUEUE. A queue has one entry point (the tail) and one exit point (the head), requiring the use of two variables: Head and Tail.

1. Queue Declaration with an Array

The process of declaring a queue involves creating its structure in memory. The queue structure includes data stored in an array, a head to mark the front of the queue, and a tail to mark the rear of the queue.

#define MAX 6

struct Queue {
    int data[MAX];
    int head;
    int tail;
};

2. Initialization

Queue initialization creates an empty queue. For queues using arrays, initialize the head and tail fields to 0 if the first element starts with index 1, or to -1 if the first element starts with index 0.

void Create() {
    antrian.head = antrian.tail = -1;
}

3. Empty Check Operation

This operation checks whether the queue is empty, which is essential before performing a dequeue. If the queue is empty, a dequeue cannot proceed. This is determined by checking if tail equals -1.

int IsEmpty() {
    if (antrian.tail == -1)
        return 1;  // Queue is empty
    else
        return 0;  // Queue is not empty
}

4. Full Check Operation

This operation checks if the queue is full. It returns true (1) if tail equals MAX - 1.

int IsFull() {
    if (antrian.tail == MAX - 1)
        return 1;  // Queue is full
    else
        return 0;  // Queue is not full
}

5. Enqueue Operation

This operation adds a new element to the queue. It updates the tail position and stores the data. Steps include:

  • Check if the queue is empty. If so, set both head and tail to 0 and add the data.
  • If the queue is not empty, increment tail by 1 and add the data.
void Enqueue(int data) {
    if (IsEmpty() == 1) {
        antrian.head = antrian.tail = 0;
        antrian.data[antrian.tail] = data;
        cout << antrian.data[antrian.tail];
    } else {
        antrian.tail++;
        antrian.data[antrian.tail] = data;
        cout << antrian.data[antrian.tail];
    }
}

6. Dequeue Operation

This operation removes the first element (head) from the queue. It shifts all subsequent elements forward and decrements the tail.

int Dequeue() {
    int i;
    int e = antrian.data[antrian.head];

    for (i = antrian.head; i <= antrian.tail - 1; i++) {
        antrian.data[i] = antrian.data[i + 1];
    }
    antrian.tail--;
    return e;
}

7. Clear Operation

Clears all elements from the queue by resetting head and tail to -1. This does not delete the array but resets the access indices.

void Clear() {
    antrian.head = antrian.tail = -1;
    cout << "Data Clear";
}

8. Display Operation

Displays all elements in the queue using a loop from head to tail.

void Tampil() {
    if (IsEmpty() == 0) {
        for (int i = antrian.head; i <= antrian.tail; i++) {
            cout << antrian.data[i] << " ";
        }
    } else {
        cout << "Data Kosong\n";
    }
}

Complete Program

Below is the full implementation of the queue program in C++:

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define MAX 6

struct Queue {
    int data[MAX];
    int head;
    int tail;
};
Queue antrian;

void Create() { antrian.head = antrian.tail = -1; }
int IsEmpty() { return antrian.tail == -1 ? 1 : 0; }
int IsFull() { return antrian.tail == MAX - 1 ? 1 : 0; }
void Enqueue(int data) {
    if (IsEmpty() == 1) {
        antrian.head = antrian.tail = 0;
        antrian.data[antrian.tail] = data;
        cout << antrian.data[antrian.tail];
    } else {
        antrian.tail++;
        antrian.data[antrian.tail] = data;
        cout << antrian.data[antrian.tail];
    }
}
int Dequeue() {
    int i, e = antrian.data[antrian.head];
    for (i = antrian.head; i <= antrian.tail - 1; i++) {
        antrian.data[i] = antrian.data[i + 1];
    }
    antrian.tail--;
    return e;
}
void Clear() { antrian.head = antrian.tail = -1; cout << "Data Clear"; }
void Tampil() {
    if (IsEmpty() == 0) {
        for (int i = antrian.head; i <= antrian.tail; i++) cout << antrian.data[i] << " ";
    } else {
        cout << "Data Kosong\n";
    }
}
void main() {
    int pil, data;
    Create();
    do {
        clrscr();
        cout << "\n============MENU============\n";
        cout << "1. Enqueue\n";
        cout << "2. Dequeue\n";
        cout << "3. Display\n";
        cout << "4. Clear\n";
        cout << "5. Exit\n";
        cout << "----------------------------\n";
        cout << "Enter your choice -> ";
        cin >> pil;
        switch (pil) {
            case 1:
                cout << "Data: ";
                cin >> data;
                Enqueue(data);
                break;
            case 2:
                if (IsEmpty() == 0)
                    cout << "Dequeued element: " << Dequeue();
                else
                    cout << "Queue is empty" << endl;
                break;
            case 3:
                Tampil();
                break;
            case 4:
                Clear();
                break;
            case 5:
                break;
        }
        getch();
    } while (pil != 5);
}

Source

Course Material: Data Structure, authored by Eko Riswanto, STMIK EL Rahma Yogyakarta.


Post a Comment

Previous Next

نموذج الاتصال