Algorithm for Queue ADT
1. Create a new queue data structure (e.g., an array or linked list) and set the front and rear pointers to -1 to indicate an empty queue.
2. Define the enqueue operation to add a new element to the rear of the queue:
a. Check if the queue is full (i.e., if the rear pointer is equal to the size of the queue minus 1).
b. If the queue is full, raise an error or resize the queue to allow for more elements.
c. If the queue is not full, increment the rear pointer, insert the new element at the position pointed to by the rear pointer, and update the value of the rear pointer.
3. Define the dequeue operation to remove the element from the front of the queue:
a. Check if the queue is empty (i.e., if the front pointer is equal to the rear pointer).
b. If the queue is empty, raise an error or return a special value to indicate an empty queue.
c. If the queue is not empty, retrieve the value at the position pointed to by the front pointer, increment the front pointer, and return the value.
4. Define the peek operation to retrieve the value of the front element without removing it:
a. Check if the queue is empty (i.e., if the front pointer is equal to the rear pointer).
b. If the queue is empty, raise an error or return a special value to indicate an empty queue.
c. If the queue is not empty, retrieve the value at the position pointed to by the front pointer and return the value.
a. Check if the front pointer is equal to the rear pointer.
b. If the front pointer is equal to the rear pointer, return true to indicate an empty queue.
These operations can be implemented using various data structures, such as arrays or linked lists, and different programming languages have different syntax for implementing these operations.
Create a class Queue
Initialize a queueArray of size MAX_SIZE and a front and rear variable to -1
Create a method isEmpty which returns true if the queue is empty i.e., front = -1 and rear = -1
Create a method isFull which returns true if the queue is full i.e., rear = MAX_SIZE - 1
Create a method enqueue which takes an element as argument
Check if the queue is full using isFull method
If full, print "Queue is full"
Else, increment rear and add element to queueArray at the rear index
If front = -1, set front = 0
Create a method dequeue
Check if the queue is empty using isEmpty method
If empty, print "Queue is empty"
Else, store the element at the front of the queue in a temp variable
Increment front
If front > rear, set front = rear = -1
Return the temp variable
Create a method display
Check if the queue is empty using isEmpty method
If empty, print "Queue is empty"
Else, loop through the queueArray from front to rear and print the elements
Create a queue object and call the enqueue, dequeue and display methods as needed.
This pseudocode defines a Queue class that has an array queueArray to store the elements of the queue, a front variable to keep track of the index of the front element of the queue, and a rear variable to keep track of the index of the rear element of the queue. The isEmpty, isFull, enqueue, dequeue, and display methods are defined to perform the corresponding operations on the queue. In the enqueue method, we check if the queue is full, and if not, we add the element to the rear of the queue and update the rear index. In the dequeue method, we check if the queue is empty, and if not, we remove the front element from the queue and update the front index. In the display method, we loop through the queueArray from front to rear and print the elements.
C Program
#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 5
int queueArray[MAX_SIZE];
int front = -1;
int rear = -1;
bool isEmpty() {
return (front == -1 && rear == -1);
}
bool isFull() {
return (rear == MAX_SIZE - 1);
}
void enqueue(int element) {
if (isFull()) {
printf("Queue is full\n");
} else if (isEmpty()) {
front = rear = 0;
queueArray[rear] = element;
} else {
rear++;
queueArray[rear] = element;
}
}
int dequeue() {
if (isEmpty()) {
printf("Queue is empty\n");
return -1;
} else if (front == rear) {
int temp = queueArray[front];
front = rear = -1;
return temp;
} else {
int temp = queueArray[front];
front++;
return temp;
}
}
void display() {
if (isEmpty()) {
printf("Queue is empty\n");
} else {
printf("Queue: ");
for (int i = front; i <= rear; i++) {
printf("%d ", queueArray[i]);
}
printf("\n");
}
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
enqueue(40);
enqueue(50);
enqueue(60); // this will print "Queue is full"
display(); // this will print "Queue: 10 20 30 40 50 "
dequeue();
dequeue();
display(); // this will print "Queue: 30 40 50 "
return 0;
}
CPP Program
#include <iostream>
using namespace std;
#define MAX_SIZE 5
class Queue {
int queueArray[MAX_SIZE];
int front;
int rear;
public:
Queue() {
front = -1;
rear = -1;
}
bool isEmpty() {
return (front == -1 && rear == -1);
}
bool isFull() {
return (rear == MAX_SIZE - 1);
}
void enqueue(int element) {
if (isFull()) {
cout << "Queue is full\n";
} else if (isEmpty()) {
front = rear = 0;
queueArray[rear] = element;
} else {
rear++;
queueArray[rear] = element;
}
}
int dequeue() {
if (isEmpty()) {
cout << "Queue is empty\n";
return -1;
} else if (front == rear) {
int temp = queueArray[front];
front = rear = -1;
return temp;
} else {
int temp = queueArray[front];
front++;
return temp;
}
}
void display() {
if (isEmpty()) {
cout << "Queue is empty\n";
} else {
cout << "Queue: ";
for (int i = front; i <= rear; i++) {
cout << queueArray[i] << " ";
}
cout << endl;
}
}
};
int main() {
Queue queue;
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
queue.enqueue(50);
queue.enqueue(60); // this will print "Queue is full"
queue.display(); // this will print "Queue: 10 20 30 40 50 "
queue.dequeue();
queue.dequeue();
queue.display(); // this will print "Queue: 30 40 50 "
return 0;
}
JAVA Program
public class Queue {
private int[] queueArray;
private int front;
private int rear;
private int capacity;
public Queue(int capacity) {
this.capacity = capacity;
this.queueArray = new int[capacity];
this.front = -1;
this.rear = -1;
}
public boolean isEmpty() {
return (front == -1 && rear == -1);
}
public boolean isFull() {
return (rear == capacity - 1);
}
public void enqueue(int element) {
if (isFull()) {
System.out.println("Queue is full");
} else if (isEmpty()) {
front = rear = 0;
queueArray[rear] = element;
} else {
rear++;
queueArray[rear] = element;
}
}
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty");
return -1;
} else if (front == rear) {
int temp = queueArray[front];
front = rear = -1;
return temp;
} else {
int temp = queueArray[front];
front++;
return temp;
}
}
public void display() {
if (isEmpty()) {
System.out.println("Queue is empty");
} else {
System.out.print("Queue: ");
for (int i = front; i <= rear; i++) {
System.out.print(queueArray[i] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
Queue queue = new Queue(5);
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
queue.enqueue(50);
queue.enqueue(60); // this will print "Queue is full"
queue.display(); // this will print "Queue: 10 20 30 40 50 "
queue.dequeue();
queue.dequeue();
queue.display(); // this will print "Queue: 30 40 50 "
}
}