Algorithms for Basic Queue Operations
We assume:
• queue[MAX] is an array to hold queue elements.
• front and rear are integers.(-1 initially)
• MAX is the maximum size.
Algorithm for Enqueue (Insert element)
Algorithm ENQUEUE(item)
1. If rear == MAX - 1 then
Output "Queue Overflow"
Exit
2. Else
rear = rear + 1
queue[rear] = item
4. End If
5. Return
Algorithm for Dequeue (Remove element)
Algorithm DEQUEUE()
1. If front == rear then
Output "Queue Underflow"
Exit
2. Else
front = front + 1
item = queue[front]
3. End If
4. Return item
Note: if front==rear we can also reset queue to utilize space
Algorithm for Peek (View Front Element)
Algorithm PEEK()
1. If front == rear then
Output "Queue is Empty"
Exit
2. Else
item = queue[front+1]
3. End If
4. Return item
Algorithm for isEmpty (Check if queue is empty)
Algorithm isEmpty()
1. If front == rear then
Return TRUE
2. Else
Return FALSE
C Program - queue using arrays
#include <stdio.h>
#include<stdlib.h>
#include <stdbool.h>
#define MAX 10
// initilazing queue
int queue[MAX];
int rear = - 1;
int front = -1;
// Function to check if the queue is empty
bool isEmpty() {
return rear==front ;
}
// Function to check if the queue is full
bool isFull() {
return rear == MAX - 1;
}
void enqueue() // enqueue
{
int item;
if (isFull())
printf("Queue Overflow \n");
else
{
printf("\nInset the element in queue : ");
scanf("%d", &item);
rear = rear + 1;
queue[rear] = item;
}
} /*End of insert()*/
void dequeue() //dequeue
{
if (isEmpty() )
{
printf("\nQueue Underflow \n");
return ;
}
else
{
front = front + 1;
printf("\nElement deleted from queue is : %d\n", queue[front]);
}
} /*End of delete() ; if front==rear we also reset queue to utilize space*/
void display()// print queue
{
int i;
if (isEmpty() )
printf("\nQueue is empty \n");
else
{
printf("\nQueue is : ");
for (i = front+1; i <= rear; i++)
printf("%d ", queue[i]);
printf("\n");
}
}
// Function to peek at the front item
int peek() {
if (isEmpty()) {
printf("Queue is empty. Nothing to peek.\n");
return -1; // Error value
} else {
return queue[front+1];
}
}
// Function to get the size of the queue
int size() {
if (isEmpty()) {
return 0;
} else {
return rear - (front + 1)+1;
}
}
int main()
{
int choice;
while (1)
{
printf("\[Link] element to queue \n");
printf("[Link] element from queue \n");
printf("[Link] all elements of queue \n");
printf("[Link] \n");
printf("[Link] of the queue\n");
printf("[Link] \n");
printf("\nEnter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
int x=peek();
if(x!=-1) printf("\nfront element is=%d\n",x);
break;
case 5:
printf("\nsize of the queue is =%d\n",size());
break;
case 6:
exit(1);
default:
printf("\nWrong choice \n");
} /*End of switch*/
} /*End of while*/
return 0;
} /*End of main()*/
Circular Queue Algorithms
Assume:
• Queue array: queue[MAX]
• Initially: front = 0, rear = 0
• A slot is wasted to distinguish full and empty.
Algorithm for isEmpty()
Algorithm isEmpty(front, rear)
1. If front == rear
Return TRUE
2. Else
Return FALSE
Meaning:
If front == rear, queue is empty.
Algorithm for isFull()
1. If (rear + 1) mod MAX == front
Return TRUE
2. Else
Return FALSE
Meaning:
If the next position of rear is front, the queue is full.
Algorithm for Enqueue (Insert an element)
1. If isFull() then
Output "Queue Overflow"
Exit
2. Else
rear = (rear + 1) mod MAX
queue[rear] = item
3. End If
Algorithm for Dequeue (Remove an element)
1. If isEmpty() then
Output "Queue Underflow"
Exit
2. Else
front = (front + 1) mod MAX
item = queue[front]
3. End If
4. Return item
Algorithm for Peek (View Front Element)
1. If isEmpty() then
Output "Queue is Empty"
Exit
2. Else
temp = (front + 1) mod MAX
Return queue[temp]
C Program - Circular Queue using array
#include <stdio.h>
#include<stdlib.h>
#include <stdbool.h>
#define MAX 10
// initilazing queue
int cqueue[MAX];
int rear = 0;
int front = 0;
// Function to check if the cqueue is empty
bool isEmpty() {
return front==rear ;
}
// Function to check if the cqueue is full
bool isFull() {
return (rear+1)%MAX == front;
}
void enqueue() // enqueue
{
int item;
if (isFull())
printf("Queue Overflow \n");
else
{
printf("\nInset the element in queue : ");
scanf("%d", &item);
rear = (rear + 1)%MAX;
cqueue[rear] = item;
}
} /*End of insert()*/
void dequeue() //dequeue
{
if(isEmpty())
{
printf("\nQueue Underflow \n");
return ;
}
else
{
front = (front + 1) %MAX;
printf("\nElement deleted from queue is : %d\n", cqueue[front]);
}
} /*End of delete() */
void display()// print queue
{
int i;
if (isEmpty() )
printf("\nQueue is empty \n");
else
{ printf("\nQueue is : ");
for (i = (front+1)%MAX; i != (rear+1)%MAX; i=(i+1)%MAX)
printf("%d ", cqueue[i]);
printf("\n");
}
}
// Function to peek at the front item
int peek() {
if (isEmpty()) {
printf("Queue is empty. Nothing to peek.\n");
return -1; // Error value
} else {
return cqueue[front+1];
}
}
int main()
{
int choice;
while (1)
{
printf("\[Link] element to queue \n");
printf("[Link] element from queue \n");
printf("[Link] all elements of queue \n");
printf("[Link] \n");
printf("[Link] \n");
printf("\nEnter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
int x=peek();
if(x!=-1) printf("\nfront element is=%d\n",x);
break;
case 5:
exit(1);
default:
printf("\nWrong choice \n");
} /*End of switch*/
} /*End of while*/
return 0;
} /*End of main()*/
Algorithms for Doubly Linked List
1. Insert at Beginning
Algorithm InsertAtBeginning(value)
1. Create a new node
2. Set [Link] = value
3. Set [Link] = NULL
4. Set [Link] = head
5. If head is not NULL
[Link] = newNode
6. Set head = newNode
2. Insert at End
Algorithm InsertAtEnd(value)
1. Create a new node
2. Set [Link] = value
3. Set [Link] = NULL
4. If head is NULL
head = newNode
[Link] = NULL
Else
temp = head
While [Link] != NULL
temp = [Link]
[Link] = newNode
[Link] = temp
3. Insert at a Given Position
Algorithm InsertAtPosition(value, position)
1. Create a new node
2. If position == 1
Call InsertAtBeginning(value)
Return
3. temp = head
4. Move temp to (position-1)th node
5. [Link] = [Link]
6. If [Link] != NULL
[Link] = newNode
7. [Link] = newNode
8. [Link] = temp
4. Delete from Beginning
Algorithm DeleteAtBeginning()
1. If head == NULL
Print "Empty list"
Return
2. temp = head
3. head = [Link]
4. If head != NULL
[Link] = NULL
5. Free temp
5. Delete from End
Algorithm DeleteAtEnd()
1. If head == NULL
Print "Empty list"
Return
2. If [Link] == NULL
Free head
head = NULL
Return
3. temp = head
4. Move temp to last node
5. [Link] = NULL
6. Free temp
6. Delete at Given Position
Algorithm DeleteAtPosition(position)
1. If head == NULL
Print "Empty list"
Return
2. If position == 1
Call DeleteAtBeginning()
Return
3. temp = head
4. Move temp to (position)th node
5. [Link] = [Link]
6. If [Link] != NULL
[Link] = [Link]
7. Free temp
7. Traversal Forward
Algorithm TraverseForward()
1. temp = head
2. While temp != NULL
Print [Link]
temp = [Link]
8. Traversal Backward
(First move to last node, then back using prev)
Algorithm TraverseBackward()
1. temp = head
2. While [Link] != NULL
temp = [Link]
3. While temp != NULL
Print [Link]
temp = [Link]
C program Doubly Linked List Operations
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
struct Node* head = NULL;
// Function to create a new node
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
exit(0);
}
newNode->data = value;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
// Insert at beginning
void insertAtBeginning(int value) {
struct Node* newNode = createNode(value);
if (head == NULL) {
head = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
printf("%d inserted at beginning\n", value);
}
// Insert at end
void insertAtEnd(int value) {
struct Node* newNode = createNode(value);
if (head == NULL) {
head = newNode;
} else {
struct Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
printf("%d inserted at end\n", value);
}
// Insert at given position
void insertAtPosition(int value, int position) {
if (position == 1) {
insertAtBeginning(value);
return;
}
struct Node* newNode = createNode(value);
struct Node* temp = head;
int i;
for (i = 1; i < position - 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) {
printf("Position out of bounds\n");
free(newNode);
return;
}
newNode->next = temp->next;
if (temp->next != NULL)
temp->next->prev = newNode;
temp->next = newNode;
newNode->prev = temp;
printf("%d inserted at position %d\n", value, position);
}
// Delete at beginning
void deleteAtBeginning() {
if (head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = head;
head = head->next;
if (head != NULL)
head->prev = NULL;
printf("Deleted %d from beginning\n", temp->data);
free(temp);
}
// Delete at end
void deleteAtEnd() {
if (head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = head;
if (temp->next == NULL) {
printf("Deleted %d from end\n", temp->data);
free(temp);
head = NULL;
return;
}
while (temp->next != NULL)
temp = temp->next;
temp->prev->next = NULL;
printf("Deleted %d from end\n", temp->data);
free(temp);
}
// Delete at given position
void deleteAtPosition(int position) {
if (head == NULL) {
printf("List is empty\n");
return;
}
if (position == 1) {
deleteAtBeginning();
return;
}
struct Node* temp = head;
int i;
for (i = 1; i < position && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) {
printf("Position out of bounds\n");
return;
}
if (temp->next != NULL)
temp->next->prev = temp->prev;
if (temp->prev != NULL)
temp->prev->next = temp->next;
printf("Deleted %d from position %d\n", temp->data, position);
free(temp);
}
// Traverse forward
void traverseForward() {
if (head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = head;
printf("List (forward): ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// Traverse backward
void traverseBackward() {
if (head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
printf("List (backward): ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->prev;
}
printf("\n");
}
// Main function with menu
int main() {
int choice, value, position;
while (1) {
printf("\n--- Doubly Linked List Operations ---\n");
printf("1. Insert at Beginning\n");
printf("2. Insert at End\n");
printf("3. Insert at Position\n");
printf("4. Delete at Beginning\n");
printf("5. Delete at End\n");
printf("6. Delete at Position\n");
printf("7. Traverse Forward\n");
printf("8. Traverse Backward\n");
printf("9. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter value to insert: ");
scanf("%d", &value);
insertAtBeginning(value);
break;
case 2:
printf("Enter value to insert: ");
scanf("%d", &value);
insertAtEnd(value);
break;
case 3:
printf("Enter value and position to insert: ");
scanf("%d%d", &value, &position);
insertAtPosition(value, position);
break;
case 4:
deleteAtBeginning();
break;
case 5:
deleteAtEnd();
break;
case 6:
printf("Enter position to delete: ");
scanf("%d", &position);
deleteAtPosition(position);
break;
case 7:
traverseForward();
break;
case 8:
traverseBackward();
break;
case 9:
printf("Exiting program\n");
exit(0);
default:
printf("Invalid choice! Try again.\n");
}
}
return 0;
}