Queue in Java and some of its common methods

dreamecho100

dreamecho100

Mazen Mohamed
created at: tags: data-structure, programming, queue, java
Queue in Java and some of its common methods

What is a Queue

A Queue is a linear structure that follows a particular order in which the operations are performed.

The order is First In First Out (FIFO).

A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first.

Here we will implement the queue in Java with some of its common methods like (enqueue, dequeue, peak, and print).

Queue vs Stack

The difference between stacks and queues is in removing. In a stack, we remove the item the most recently added.

In a queue, we remove the item the least recently added.

Stack implementation in Java

let's start with a class [ "MyQueue" ] and add the basic properties and methods that we will need.

1public class MyQueue {
2
3 private int front;
4 private int rear;
5 private int maxSize;
6 private int numberOfElements;
7 private int list[];
8
9 MyQueue(int maxSize) {
10  this.front = 0;
11  this.rear = -1;
12  this.list = new int[maxSize];
13  this.maxSize = maxSize;
14  this.numberOfElements = 0;
15 }
16
17 public boolean isFull() {
18  return this.maxSize == this.numberOfElements;
19 }
20
21 public boolean isEmpty() {
22  return this.maxSize == 0;
23 }
24}
  • [ "front" ]: An integer that holds the value of the first index of the queue.
  • [ "rear" ]: An integer that holds the value of the last index of the queue.
  • [ "maxSize" ]: A variable we will use to Know the maximum size allowed for the queue.
  • [ "numberOfElements" ]: A variable that we will use to keep track of the number of elements in the queue.
  • [ "list" ]: An array where we will store the values of the queue.
  • [ "isFull" ]: A method that will return true if the queue is empty.
  • [ "isEmpty" ]: A method that will return true if the queue is full.

When we call the [ "MyQueue" ] class:

  • It will take an integer that will determine the [ "maxSize" ] of the queue.
  • [ "front" ]: will be 0;
  • [ "rear" ]: will be -1 since there is no element yet;
  • we will initialize the size of the [ "list" ] array by the [ "maxSize" ]
  • And lastly, the [ "numberOfElements" ] will be 0.

Add an element to Stack in Java

1public int enqueue(int item) {
2  // Check if the last item in the queue is at the end of the queue (at the last allowed index)
3  if (this.rear == this.maxSize - 1) {
4    // Change the `rear` to point at the first of the array
5    this.rear = 0;
6  } else {
7    // Increase both `rear` and `numberOfElements` by one.
8    this.rear++;
9    this.numberOfElements++;
10  }
11
12  // Place the item to index that `rear` value is
13  this.list[this.rear] = item;
14
15  // Return the index of the item in the queue.
16  return this.rear;
17}
  • First, We will check if the last item in the queue is at the end of the queue (at the last allowed index), we will change the [ "rear" ] to point at the first of the array, else we increase both [ "rear" ] and [ "numberOfElements" ] by one.
  • Then that we will place the item to the index value of [ "rear" ].
  • Finally, we will return the index of the item in the queue.

Remove an element to Stack in Java

In A Queue when removing an item we remove the first item to come in.

1public int dequeue() {
2  // Check if the queue is empty
3  if (isEmpty()) {
4    // Exit or you can throw an exception.
5    System.out.println("Underflow\nProgram Terminated");
6    System.exit(-1);
7  }
8
9  // Store the item in the index `front` in `removedItem` to return it
10  int removedItem = this.list[front];
11
12  // Increase the value of `front` and decrease the value nof `numberOfElements`
13  this.front++;
14  this.numberOfElements--;
15
16  // If the `front` is at the last index of the queue
17  if (this.front == this.maxSize - 1) {
18    // Assign it to 0 _(at the first of the queue)_
19    this.front = 0;
20  }
21
22  // Return the `removedItem`
23  return removedItem;
24}
  • First, We will check if the queue is empty, and if true we exit or you can throw an exception.
  • Then that we will store the item in the index [ "front" ] in [ "removedItem" ] to return it.
  • After that, we will increase the value of [ "front" ] and decrease the value of [ "numberOfElements" ].
  • We also will check if the [ "front" ] is at the last index of the queue and assign it to 0 (at the first of the queue) if true.
  • Finally, we will return the [ "removedItem" ].

Looking at the first element of the queue (Peak)

1public int peek() {
2  // Check if the queue is empty
3  if (isEmpty()) {
4    // Exit or you can throw an exception.
5    System.out.println("Underflow\nProgram Terminated");
6    System.exit(-1);
7  }
8
9  // Return the first element in the queue
10  return this.list[this.front];
11}
  • First, We will check if the queue is empty, and if true we exit or you can throw an exception.
  • Then we will return the first element in the queue.

Printing all the elements of the queue

I have added two variations and I advise you to test both of them and see the difference 😁.

Printing all the elements of the queue V1

1public void printV1() {
2  if (this.isEmpty()) {
3    System.out.println("Queue is Empty");
4    return;
5  }
6
7  int i;
8  if (this.rear >= this.front) {
9   for (i = this.front; i < this.rear; i++) {
10    System.out.println(list[i]);
11   }
12  } else {
13   for (i = this.front; i < this.maxSize; i++) {
14    System.out.println(list[i]);
15   }
16
17   for (i = 0; i <= this.rear; i++) {
18    System.out.println(list[i]);
19   }
20  }
21}

Printing all the elements of the queue V2

1public void printV2() {
2  if (this.isEmpty()) {
3    System.out.println("Queue is Empty");
4    return;
5  }
6
7  int i;
8  if (this.rear > this.front) {
9    for (i = this.front; i <= this.rear; i++) {
10      System.out.println(list[i]);
11    }
12  } else {
13    int rearLimit = this.rear == this.front ? this.rear : -1;
14
15  for (i = this.front; i < this.maxSize; i++) {
16    System.out.println(list[i]);
17  }
18
19  if (this.rear != this.front)
20    for (i = 0; i <= this.rear; i++) {
21      System.out.println(list[i]);
22    }
23  }
24}

full code for queue implementation in Java

1public class MyQueue {
2
3 private int front, rear, maxSize, numberOfElements;
4 private int list[];
5
6 MyQueue(int maxSize) {
7  this.front = 0;
8  this.rear = -1;
9  this.list = new int[maxSize];
10  this.maxSize = maxSize;
11  this.numberOfElements = 0;
12 }
13
14 public boolean isFull() {
15  return this.maxSize == this.numberOfElements;
16 }
17
18 public boolean isEmpty() {
19  return this.maxSize == 0;
20 }
21
22 public int enqueue(int item) {
23  if (this.rear == this.maxSize - 1) {
24   this.rear = 0;
25  } else {
26   this.rear++;
27   this.numberOfElements++;
28  }
29
30  this.list[this.rear] = item;
31
32  return this.rear;
33 }
34
35 public int dequeue() {
36  if (isEmpty()) {
37   System.out.println("Underflow\nProgram Terminated");
38   System.exit(-1);
39  }
40
41  int removedItem = this.list[front];
42
43  this.front++;
44  this.numberOfElements--;
45
46  if (this.front == this.maxSize - 1) {
47   this.front = 0;
48  }
49
50  return removedItem;
51 }
52
53 public int peek() {
54  if (isEmpty()) {
55   System.out.println("Underflow\nProgram Terminated");
56   System.exit(-1);
57  }
58
59  return this.list[this.front];
60 }
61
62  public void printV1() {
63    if (this.isEmpty()) {
64      System.out.println("Queue is Empty");
65      return;
66    }
67
68    int i;
69    if (this.rear >= this.front) {
70    for (i = this.front; i < this.rear; i++) {
71      System.out.println(list[i]);
72    }
73    } else {
74    for (i = this.front; i < this.maxSize; i++) {
75      System.out.println(list[i]);
76    }
77
78    for (i = 0; i <= this.rear; i++) {
79      System.out.println(list[i]);
80    }
81    }
82  }
83
84  public void printV2() {
85    if (this.isEmpty()) {
86      System.out.println("Queue is Empty");
87      return;
88    }
89
90    int i;
91    if (this.rear > this.front) {
92      for (i = this.front; i <= this.rear; i++) {
93        System.out.println(list[i]);
94      }
95    } else {
96      int rearLimit = this.rear == this.front ? this.rear : -1;
97
98    for (i = this.front; i < this.maxSize; i++) {
99      System.out.println(list[i]);
100    }
101
102    if (this.rear != this.front)
103      for (i = 0; i <= this.rear; i++) {
104        System.out.println(list[i]);
105      }
106    }
107  }
108}