Implementing a Queue, Explained with Code Examples

UPI Study › Courses › Programming in C › Free lessons › Lesson 11.5 Free with a free account

Implementing a Queue

Programming in C · Chapter 11: Dynamic Memory, Linked Lists, Stacks, and QueuesSection 11.5 · lesson 75 of 787 min · free with a free account

← Implementing a StackNext lesson: Dynamic Linked List Operations →

Earn 3 college credits for Programming in CRecommended for credit by NCCRS · Computer Science 240 · self-paced · one payment, lifetime access
Enroll in Programming in C · $250 →Download the syllabus (PDF)

In this lesson

Building a FIFO queue as a circular array and linked list.

  • Explain the FIFO rule and the enqueue and dequeue operations
  • Implement a circular array queue that wraps indexes with the remainder operator
  • Use a count to tell a full circular queue from an empty one
  • Implement a linked queue with head and tail pointers

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 (934 words). Read along, or search it.

Opening Question

First Come, First Played

Every machine at the Starlight Arcade has a line of players, and everyone agrees on one rule: whoever arrived first plays first. Nobody cuts in, and nobody at the back gets served early. That fair line is a data structure called a queue. Today you'll build two queues: one in an array that wraps around like a clock, and one made of linked nodes.

Definition

First In, First Out

A queue is a collection where items leave in the same order they arrived. The rule is FIFO: first in, first out. A stack, from 11.4, is the opposite: last in, first out. enqueue adds an item at the rear, the back of the line. dequeue removes the item at the front, and hands it back. You also need to check for empty, with nothing waiting. And for an array, for full, with no room left. Our players are just ticket numbers, so these queues hold plain ints.

The Catch

Wrapping Indexes Around a Circle

The simple idea is an array with two indexes. front says where the next player leaves from, and rear says where the next player will stand. Enqueue moves rear forward. Dequeue moves front forward. But there's a catch. After a few players leave, the first slots are empty, while rear has already reached the end. The array looks full, and it isn't. The fix is to treat the array as a circle: when an index passes the last slot, it goes back to zero. The remainder operator from 2.5 does it in one step. rear plus one, remainder four, gives 1, 2, 3, and then 0.

Array Version

A Circular Queue With a Count

Here's the whole queue. Next to front and rear, it keeps a third number, count: how many players are waiting. enqueue refuses when count equals CAP. Otherwise, it stores the ticket at rear, moves rear forward with the wrap, and adds one to count. dequeue refuses when count is zero. Otherwise, it reads the ticket at front, moves front forward with the same wrap, and subtracts one. Both indexes need the wrap. Write rear plus one without the remainder, and rear runs past slot 3, outside the array. That's undefined behavior. main fills the line with four tickets, serves two, lets two more join, and then serves everyone.

Sample Run

Full and Empty Look the Same

Build and run. After four tickets join, front and rear are both zero, because rear already wrapped around. And count is four: the line is full. So ticket 105 must wait. Then 101 and 102 are served, and front moves to 2. 105 and 106 join. They land in slots 0 and 1, so rear ends at 2. Then everyone is served in arrival order: 103, 104, 105, 106, even across the wrap. Now compare the first and last reports. front equals rear both times, but once the line is full, and once it's empty. Only count tells them apart.

Quick Check

Where Rear Lands After Wrapping

Quick check. A queue with five slots, so CAP is 5. rear is at slot 3, and three more players join. Where does rear end up? Pause and predict. Build and run: rear equals one. Step by step: 3 becomes 4. 4 plus 1 is 5, and the remainder after dividing by 5 is 0. Then 0 becomes 1. Without the remainder, rear would be 6, two past the last slot, which is slot 4.

Linked Version

Head for Leaving, Tail for Joining

An array has a fixed size, so the line can be full. A linked queue has no such limit: each player gets a node from malloc. The queue keeps two pointers. head is the front, where players leave. tail is the rear, where they join. With tail, enqueue never walks the list to find the end. It's the trick from 11.1: hook the new node on after tail, then move tail. Dequeue takes the node at head, copies the ticket out, moves head along, and frees the old node.

Code Walkthrough

Resetting Tail When the Last Node Leaves

In the code, Queue holds head and tail. An empty queue has both set to NULL. enqueue makes the node, with next set to NULL. If tail is NULL, the line was empty, so the new node becomes the head too. Otherwise, it's hooked on after the old tail. Either way, tail moves to the new node. dequeue copies the ticket from head, and moves head to the next node. Then comes the special case. When the last node leaves, head becomes NULL, and tail must be set to NULL too. Only then is the old node freed. Sam found this bug in an early version. tail still pointed at the freed node, and the next enqueue wrote into memory that had been given back.

Sample Run

Three Tickets Served in Order

Build and run. Three tickets join: 201, 202 and 203. 201 is served first, and the line now reads 202, then 203. After the last one, 203, is served, head and tail are both NULL again. And one more dequeue reports that the line is empty.

Quick Check

No Cutting In Line

Quick check. The same linked queue. Tickets 7, 8 and 9 join, and two are served. Then 10 joins, and one more is served. Which ticket does it print? Pause and predict. Build and run: served 9. 7 and 8 left first, because they joined first. 10 joined behind 9, so 9 is next out. If you said 10, that's stack thinking: last in, first out. A queue never lets the newest player cut in.

Key Takeaways

Join at the Rear, Leave at the Front

To sum up. A queue is first in, first out: enqueue at the rear, dequeue at the front. An array queue wraps its indexes around with the remainder operator. front equals rear can mean full or empty, so keep a count. A linked queue keeps head and tail. When the last node leaves, set tail to NULL too.

About Programming in C at UPI Study

Programming in C (Computer Science 240) is a self-paced online course of 78 video lessons in 11 chapters, from pseudocode and your first program to data types, decisions, loops, functions, arrays, strings, pointers, files, structures, dynamic memory and linked lists. 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: C vs C++

Why take it here

Why students take Programming in C with UPI Study

How programs work close to the machineProgramming in C teaches how a program uses memory: variables and data types, control flow, functions, arrays and strings, pointers, files, structures and dynamic memory. C is the base for operating systems, embedded devices and many computer-science courses.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Programming in C 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 UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks 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 Implementing a Queue

What is the difference between a stack and a queue?
A queue is first in, first out, or FIFO: items join at the rear and leave from the front in arrival order. A stack is last in, first out, so the newest item leaves first. If tickets 7, 8, and 9 join a queue and 10 joins after two are served, the next one out is 9, while a stack doing the same steps would hand back 10.
What is a circular queue in C?
A circular queue is an array queue whose indexes wrap back to 0 after the last slot, so slots freed at the front can be reused. Each move uses the remainder operator: rear = (rear + 1) % CAP. With 4 slots, rear goes 1, 2, 3, and then 0. Without the wrap, the index runs past the end of the array, which is undefined behavior.
How do you tell whether a circular queue is full or empty?
One simple way is to keep a separate count of waiting items. In a circular array queue, front equals rear both when the queue is full and when it is empty, so the indexes alone cannot tell them apart. With a count, the queue is empty when count is 0 and full when count equals the capacity, and enqueue and dequeue update it every time.
Why must tail be set to NULL when a linked queue becomes empty?
When dequeue removes the last node, head becomes NULL, but tail still points at the node about to be freed. If tail is not reset too, the next enqueue hooks its new node onto freed memory, a use-after-free bug. So dequeue checks whether head became NULL, sets tail to NULL in that case, and only then frees the old node.

About the Programming in C course

How many college credits is Programming in C?
Programming in C (Computer Science 240) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Programming in C cost and what is included?
$250, paid once, with lifetime access: all 78 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Programming in C take?
It is self-paced with no deadlines. The 78 lessons total about 9 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Programming in C.

78 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Programming in C →Download the syllabusEvery course with PRO →
Programming in C
3 credits · NCCRSEnroll →