Write a program to implement a queue using an array. In this tutorial, You are going to learn about Queue data structure and their implementation using an array in C, C++ & Java. In my previous posts, I have explained Stack and Linked List data structure.
Queue Data Structure
In Queue data structure, An element is inserted at one end called rear and deleted at other end called front. As compared to stack data structure in which insertion and deletion are allowed only at one end. Queue data structure is also called FIFO (First In First out).
Enqueue – In queue, insertion operation is called as enqueue.
Dequeue – In queue, delete operation is called as Dequeue
Program to implement stack using array
Queue Data Structure Implementation Using an Array
In this tutorial, We’ll implement a Queue using an array. To implement queue using an array, we need to take two variables to keep track of both ends.
rear – points an index of last added item.
front – points an index of last removed item.
Implementation Logic
1. Initialize rear = front = -1. Initially, Queue is empty so rear and front both have assigned a value -1.
2. To insert a new data, rear should be incremented by 1. If the front index is -1, then front is incremented and set to 0.
3. If any element is deleted from a queue, then the value of front should be incremented by 1.
Implement a Queue using an Array in C
Now you have understood what is Queue data structure and it’s basic terminologies. Let’s implement a queue data structure in C.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include <stdio.h> #define MAX 100 int front = -1; int rear = -1; int arr[MAX]; /* Create a function for insertion. */ void enqueue(int data){ /* If memory is not available. */ if(rear == MAX-1){ printf ("Memory overflow \n"); return; } /* If a queue is empty. */ if ( front == -1){ front = 0; } /* After incrementing rear, insert the data. */ arr[++rear] = data; } /* Method to delete an element from queue. */ int dequeue(){ int value; /* When queue is empty. */ if(front == rear+1 || front == -1){ printf ("Queue underflow"); return 0; } value = arr[front]; /* Increment the value of front by 1. */ front++; printf("\n Deque element is %d",value); return value; } void display(){ int i; if(front == -1 || front == rear+1){ printf("Queue is empty\n"); return; } /* If queue is not empty. Print element of a queue. */ for(i = front; i <= rear; i++){ printf("%d\n",arr[i]); } } main() { enqueue (5); enqueue (8); enqueue (9); display(); dequeue(); } |
Implement a Queue using an Array in Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
package queuedemo; import java.util.*; public class QueueDemo { private int size; private int queueArr[]; private int front = -1; private int rear = -1; private int currentsize = 0; public QueueDemo(int size) { this.size = size; queueArr = new int[this.size]; } public void enqueue(int value) { if(currentsize + 1 <= size) { queueArr[++rear] = value; //Increment current size currentsize++; front = (front == -1) ? 0 : front; } else { System.out.println("Overlow ! Memory is full"); } } public void dequeue() { //Check if current size is greater than 0 if(currentsize > 0) { front++; currentsize--; } else { System.out.println("Nothing available to remove"); } } public void display() { if (currentsize == 0) { System.out.println("Queue is empty"); } else { System.out.println("Current queue is"); for (int i = front; i <= rear; i++){ System.out.println(queueArr[i]); } } } public void peek() { System.out.println("Peek element is " + queueArr[front]); } public static void main(String[] args) { QueueDemo qd = new QueueDemo(5); qd.enqueue(3); qd.enqueue(4); qd.display(); qd.dequeue(); qd.display(); qd.peek(); } } |
