UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 10.2 Free with a free account
Processing the Earliest Added Element First
Data Structures and Algorithms · Chapter 10: Stacks, Queues, and DequesSection 10.2 · lesson 40 of 879 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Data Structures and Algorithms.
Lesson complete
Earn the 3 college credits for Data Structures and Algorithms
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Adding and Removing at Both Ends of a Sequence →← StacksNext lesson: Adding and Removing at Both Ends of a Sequence →
In this lesson
First-in, first-out queues with circular arrays and linked nodes.
- Describe the queue abstract data type and its FIFO rule
- Implement a circular array queue that wraps indexes with the remainder operator
- Implement a linked queue with head and tail references
- Distinguish a full ring from an empty one using a size counter
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (1,301 words). Read along, or search it.
Opening Question
Waiting in Line at a Counter
Think about waiting in line at a counter. The person who arrived first is served first, and a newcomer joins at the back. Nobody expects the latest arrival to jump to the front. That rule is first in, first out, or FIFO, and a structure that follows it is a queue. It sounds simple. But a queue changes at both ends: items enter at one end, and leave at the other. A careless array version becomes slow, and a careless linked version loses items.
Definition
The Queue Abstract Data Type
As an abstract type, a queue is defined by what it does. Enqueue adds an item at the rear. Dequeue removes and returns the item at the front. Front looks at the front item without removing it. And is empty, and size, report on the queue. Dequeue or front on an empty queue is a mistake, so a good queue reports it clearly, by throwing an exception. Java's own Queue interface uses the names offer, poll and peek, and its poll and peek return null on an empty queue instead.
Trace
Enqueue and Dequeue in Order
Trace a short run, with the front on the left. Enqueue A, then B, then C. Dequeue returns A, the item that waited longest. Front then shows B, and leaves it in place. Enqueue D joins at the rear, and the next dequeue returns B. Each removal takes the item that has waited longest. That's the whole point of a queue.
The Problem
Shifting or Drifting in an Array
Now store a queue in an array. Where should the front go? Keep the front at index zero, and every dequeue must shift all the remaining items one place left. Each dequeue costs order n. Let the front index move right instead, and dequeue is cheap. But the whole queue drifts toward the end, leaving free cells at the left that can never be used.
Implementation
Wrapping Indexes in a Circular Array
The cure is to treat the array as a ring. When an index would move past the last slot, it wraps back to slot zero. In arithmetic, wrapping is the remainder operator. Index plus one, mod capacity, gives the next slot, and returns to zero after the last. Then two numbers describe the whole queue: front, the index of the first item, and size. The next free slot, where enqueue writes, is front plus size, mod capacity. Dequeue reads the slot at front, then moves front forward one, with the same wrap. Here's a real run on a ring of five slots. Enqueue A, B, C and D fill slots zero to three. Two dequeues return A and B. Front moves to two, and size drops to two. Enqueue E goes to slot four. Then enqueue F: the next free slot is two plus three, mod five, which is zero. F wraps to the start. Enqueue G fills slot one. Now size is five, so an enqueue of H is refused: the queue is full. Items leave in the order C, D, E, F, G. Every operation is a little arithmetic and one array access, so enqueue and dequeue are order one. In one test with eighty thousand items, the shifting version took seconds. The ring took under a millisecond.
Quick Check
Where the Next Enqueue Writes
Quick check. A ring has capacity six. Front is four, and size is five. In which slot will the next enqueue write: slot three, slot nine, or slot four? Pause, and decide. Slot three. Front plus size is nine, and nine mod six is three. Nine forgets the wrap: there is no slot nine. Four is where the front item already sits. And with a size of six, the ring would be full, and the enqueue refused.
Implementation
A Linked Queue with Head and Tail
A chain of nodes avoids the capacity limit. A queue acts at both ends, so it keeps two references: head for the front, and tail for the rear. Enqueue links a new node after the tail, and moves the tail to it. Dequeue takes the value at the head, and moves the head to the next node. Both are order one. The ends are chosen on purpose. To remove the last node of a singly linked chain, you'd walk the whole chain to find the node before it. That would cost order n.
Common Mistake
Forgetting to Reset the Tail
One line is easy to forget. When dequeue removes the last node, the head becomes null, and the tail must be set to null as well. Forget it, and the tail still points at the removed node. The next enqueue links after that dead node, the head stays null, and the new item is lost.
Comparison
Ring Versus Linked Chain
So there are two sound designs. A ring's capacity is fixed when it's created, so it can be full. A chain grows with every item, and is full only when memory runs out. A ring spends one array slot per item. A chain spends a whole node: the value, plus a reference to the next. And the bookkeeping differs: the ring tracks a front index and a size, while the chain tracks head and tail references.
Key Problem
Telling Full from Empty
A ring has one more puzzle. Suppose it stores only a front index and a rear index, where rear is the next free slot. When the queue is empty, front equals rear. Fill every slot, and rear moves all the way around, and equals front again. So equal indexes can't tell full from empty. There are three standard fixes. Keep a size counter: empty at zero, full at capacity. Or leave one slot always unused, so full means rear plus one, mod capacity, equals front. That ring holds one item fewer. Or keep a flag recording whether the last operation was an enqueue or a dequeue. The size counter is the easiest to reason about, and uses every slot. A linked queue never has the puzzle: it's empty exactly when head is null.
Common Mistakes
Overwrites, Missing Mod, and Empty Checks
When a bounded ring is full, an enqueue must never quietly overwrite the front item. It refuses, by throwing an exception, or by returning a flag. Two more slips come up often. Advance an index with plus one and no mod, and it runs past the last slot, into an out-of-bounds error. And calling dequeue or front without checking for empty gives an exception, or a null that fails later, somewhere unrelated.
Comparison
Stack Reverses, Queue Keeps Order
The stack and the queue are built from the same materials, but they obey opposite rules. Add A, B and C to each. The stack hands back C, then B, then A: it reverses the order. The queue hands back A, then B, then C: it keeps it. Both give order one operations, so cost doesn't decide between them. The deciding question is which item you need next: the most recent one, or the one that's waited longest.
Quick Check
From a Queue into a Stack
One more check. The numbers one, two, three, four pass through a queue, and whatever comes out goes straight into a stack. Then the stack is emptied. In what order do they finally come out: four three two one, one two three four, or two one four three? Pause, and predict. Four, three, two, one. The queue keeps the order, so the stack receives one, two, three, four. The stack then reverses it. One two three four would need a second reversal; the queue alone never changes the order.
Key Takeaways
Queue Essentials
To sum up. A queue is first in, first out: add at the rear, remove at the front. A circular array wraps its indexes with the remainder operator, so nothing shifts, and no slot is wasted. A linked queue keeps head and tail, and must reset the tail when the last node leaves. Equal indexes can't tell full from empty, so keep a size counter. And both designs give order one operations.
Think About It
A Queue Built from Two Stacks
Something to think about. Could you build a queue out of two stacks? Where would enqueue put items, where would dequeue take them from, and when would you move items from one stack to the other?
About Data Structures and Algorithms at UPI Study
Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →
Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms
Why take it here
Why students take Data Structures and Algorithms with UPI Study
Where the credit goes
Universities that work with NCCRS
Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Processing the Earliest Added Element First
What is a queue in data structures?
How does a circular array queue work?
How do you tell if a circular queue is full or empty?
Why must a linked queue reset the tail when it becomes empty?
About the Data Structures and Algorithms course
How many college credits is Data Structures and Algorithms?
How much does Data Structures and Algorithms cost and what is included?
Which universities accept UPI Study credits?
How long does Data Structures and Algorithms take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Data Structures and Algorithms.
87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →