Stack, Queue, Circular Queue and Dequeue in Java (ISC Class 12 Computer Science)

Understand Stack, Queue, Circular Queue and Dequeue in Java

class Stack {
    int[] a; int top;
    Stack(int n) { a = new int[n]; top = -1; }
    void push(int x) {
        if (top == a.length - 1) System.out.println("Overflow");
        else a[++top] = x;
    }
    int pop() {
        if (top == -1) { System.out.println("Underflow"); return -1; }
        return a[top--];
    }
}

void enqueue(int x) {
    if (count == n) System.out.println("Overflow");
    else { rear = (rear + 1) % n; a[rear] = x; count++; }
}
int dequeue() {
    if (count == 0) { System.out.println("Underflow"); return -1; }
    int x = a[front]; front = (front + 1) % n; count--; return x;
}

Stack, Queue, Circular Queue and Dequeue in Java: key facts

Stack operations

Empty	top = -1
Full	top = n - 1
push	a[++top] = x
pop	return a[top--]

LIFO: the last pushed leaves first.

Queue ends

• •Add at the rear
• •Remove from the front
• •FIFO
• •Simple queue can waste freed space

The order of service is the order of arrival.

Circular queue

• •rear = (rear + 1) % n
• •front = (front + 1) % n
• •Full: count == n
• •Empty: count == 0

Indices wrap round to 0.

Dequeue

• •addFront and addRear
• •removeFront and removeRear
• •Both ends open
• •Works as a stack or a queue

Also called a double-ended queue.

How to answer Stack, Queue, Circular Queue and Dequeue in Java questions

1. 1Draw the array with indices, and write top (or front, rear and count) beside it.
2. 2Apply the operations one by one: check overflow or underflow before every insertion or removal.
3. 3For a circular queue, compute the new rear or front with the % n rule.
4. 4Write the removed value for each pop or dequeue and the print line for each overflow or underflow.
5. 5After the last operation, list the structure in order (bottom to top, or front to rear).
6. 6State the final top, or front and rear.

Stack, Queue, Circular Queue and Dequeue in Java in real life

The idea, met in an everyday situation. Answer the question in your own words, then compare with the model answer. The one-line hook is what to remember.

Tricks to remember Stack, Queue, Circular Queue and Dequeue in Java

Short memory aids. Say each one aloud once, then use it on a question the same day.

• LIFO and FIFO

  Stack = Last In First Out, Queue = First In First Out.

  Use it when: Definitions.

• Plus one, mod n

  Move the pointer by 1 and wrap with % n.

  Use it when: Circular queue indices.

• Full or empty by count

  rear sits just behind front (modulo n) in both the full and the empty state, so front and rear alone cannot tell them apart; keep a count.

  Use it when: Circular queue conditions.

• Check first, then act

  Test overflow before inserting and underflow before removing.

  Use it when: Writing push, pop, enqueue, dequeue.

Stack, Queue, Circular Queue and Dequeue in Java: solved examples

Ordered from board level to HOTS. Try each one before you open the solution.

s.push(5); s.push(8); s.push(2); s.push(9);
System.out.println(s.pop() + " " + s.pop());
s.push(7);
System.out.println(s.top);

Where students lose marks in Stack, Queue, Circular Queue and Dequeue in Java

The slips examiners see most often, and what to write instead.

• ✗Mistake: No overflow or underflow test

  A push on a full array and a pop on an empty one both throw ArrayIndexOutOfBoundsException (a[-1] on pop).

  Wrong working

  void push(int x) { a[++top] = x; }

  Right working

  if (top == a.length - 1) overflow else a[++top] = x;

  ✓Do this: Test before changing the pointer.

  Usually costs: 1 mark

• ✗Mistake: Forgetting % n

  The index moves past the end of the array instead of wrapping.

  Wrong working

  rear = rear + 1;

  Right working

  rear = (rear + 1) % n;

  ✓Do this: Apply % n to both front and rear.

  Usually costs: 1 mark

• ✗Mistake: Mixing LIFO and FIFO

  The removal end decides the structure.

  Wrong working

  A queue removes the newest element

  Right working

  A queue removes the oldest element

  ✓Do this: Say stack = last in first out, queue = first in first out.

  Usually costs: 1 mark

Practice questions on Stack, Queue, Circular Queue and Dequeue in Java

Write each answer on paper first. Open the hint only if you are stuck, and the answer only when you have finished.

1. Q1 · 1 mark · MCQBoard level

   Which data structure removes the element that was inserted first?
   (a) stack (b) queue (c) tree (d) array

   Hint

   First in, first out.

   Answer

   (b) queue

2. Q2 · 2 marks · Short answerBoard level

   Define overflow and underflow. Why is a circular queue better than a simple array queue?

   Hint

   Think of cells freed at the front.

   Answer

   Overflow is trying to insert into a full structure; underflow is trying to remove from an empty one. A circular queue wraps the indices round with % n, so cells freed by deletions are reused, which a simple array queue cannot do.

3. Q3 · 3 marks · Short answerHarder board level

   An array queue of size 3 holds 1, 2, 3. Two items are removed and 4 is then added. Show why a simple queue reports Overflow but a circular queue accepts 4.

   Hint

   Follow front and rear.

   Answer

   After the two removals front = 2 and rear = 2, with two free cells at indices 0 and 1. In a simple queue rear == n - 1 = 2, so it reports Overflow. In a circular queue, count is 1, so there is space: rear = (2 + 1) % 3 = 0 and 4 is stored at index 0.

4. Q4 · 3 marks · Short answerHarder board level

   Write a method of class Stack that displays the elements from the top to the bottom without removing them, and give its output for the stack 4, 7, 1 (1 on top).

   Hint

   Loop from top down to 0.

   Answer

   void display() {
       for (int i = top; i >= 0; i--)
           System.out.print(a[i] + " ");
   }

   With a = {4, 7, 1} and top = 2, the output is: 1 7 4

5. Q5 · 4 marks · Case-basedHOTS / competency

   A queue holds 1, 2, 3 (1 at the front). Using one stack, reverse the queue so that 3 is at the front. Show the steps, the number of operations, and say which two principles are combined.

   Hint

   Empty the queue into the stack and then back.

   Answer

   Dequeue 1, 2, 3 and push each: the stack holds 1, 2, 3 with 3 on top. Pop 3, 2, 1 and enqueue each in turn, giving the queue 3, 2, 1 with 3 at the front. The operations are 3 dequeues, 3 pushes, 3 pops and 3 enqueues, 12 in all. FIFO of the queue and LIFO of the stack together reverse the order.

Test your recall

Answer in your head or on paper first, then open the card. Pulling an answer out of memory makes it stick far better than re-reading.

1. 1.What is the value of top for an empty array stack?Show answer

   -1.

2. 2.Which end does a queue remove from?Show answer

   The front.

3. 3.What is the advantage of a circular queue?Show answer

   It reuses freed space.

4. 4.What condition shows a full circular queue with a counter?Show answer

   count == n.

5. 5.How many ends can a dequeue use for insertion?Show answer

   Both ends.

6. 6.What is underflow?Show answer

   Removing from an empty structure.

Stack, Queue, Circular Queue and Dequeue in Java: frequently asked questions