Stacks, Queues and Deques Using Classes

Hello students, welcome to Kwickprep. At a wedding, you take the top plate from a pile. At a ticket counter, the first person in line is served first. These two everyday rules are two famous data structures. Today we build a stack, a queue, a circular queue and a deque, using a Java class and an array.

A data structure is a way of storing data so that we can use it well. A stack is a data structure where items enter and leave from one end only, called the top. So it follows LIFO, which means last in, first out, just like a pile of plates. Push means adding an item on top. Pop means removing the top item. Peek means looking at the top item, without removing it.

Let us trace a stack stored in an array, with a variable top that holds the index of the top item. Push ten, and top becomes zero. Push twenty, and top becomes one. Push thirty, and top becomes two. Pop removes the last item added, which is thirty, and top goes back to one. Peek shows twenty, but the stack does not change.

Now we build the stack as a Java class. The array a stores the items, and top starts at minus one, which means empty. Push first increases top, then stores x at that index. Pop first gives the item at top, then decreases top. In main, s is our stack object. We push four, then nine, and pop gives nine, the last item pushed.

A real stack must check two dangers. Overflow means pushing when the stack is already full, so top equals the array length minus one. In that case, we print Overflow instead of storing. Underflow means popping when the stack is empty, so top equals minus one. Here pop returns minus one, so the caller must check that the stack is not empty first. Exams give marks for these checks, so never skip them.

Now the ticket counter. A queue is a data structure where items join at one end, called the rear, and leave from the other end, called the front. So it follows FIFO, which means first in, first out. Insert, also called enqueue, adds an item at the rear. Delete, also called dequeue, removes the item at the front.

Here is a queue class. The variable f is the front index and r is the rear index. The method ins, short for insert, moves r forward and stores the item. The method del, short for delete, gives the item at f and moves f forward. We insert four, then nine. Delete gives four, because four came first. A full version checks overflow when r equals size minus one, and underflow when f is greater than r.

A simple queue has a hidden problem. Every delete moves the front forward, so the cells behind it become empty. Soon the rear reaches the last index, and the queue says it is full. But the cells at the start are empty, and they are wasted. The fix is to let the rear wrap around to index zero, which gives us a circular queue.

In a circular queue, the last cell is joined back to the first cell, like seats on a merry go round. The variable count keeps how many items are stored. If count equals size, the queue is truly full. Otherwise, r becomes r plus one, modulus size. With size five, when r is four, four plus one modulus five is zero, so the rear wraps to the start. Delete moves the front in the same way.

Pause the video and predict the next rear index, using r plus one, modulus size. With size five and rear two, the next rear is three. With size five and rear four, the next rear is zero, because it wraps around. With size four and rear three, the next rear is also zero. The wrap happens exactly at the last index.

A deque, pronounced deck, is a double ended queue. In a full deque, we can insert and delete at both the front and the rear. An input restricted deque allows insertion at only one end, but deletion at both ends. An output restricted deque allows insertion at both ends, but deletion at only one end. A deque can behave like a stack or like a queue, as we choose.

Let us compare stacks and queues, a common exam question. A stack follows LIFO, while a queue follows FIFO. A stack uses one end, the top, while a queue uses two ends, front and rear. We add with push in a stack, and with insert in a queue. We remove with pop in a stack, and with delete in a queue. Undo in an editor and method calls use a stack, while printer jobs wait in a queue.

Let us revise. A stack is LIFO, with push, pop and peek at the top. A queue is FIFO, inserting at the rear and deleting from the front. A circular queue wraps around using rear plus one, modulus size. A deque allows insert and delete at both ends. In Java, we build them with a class holding an array and index variables, and we always check overflow and underflow.