Chapter 4: Queue

In the early years of computing, a mainframe computer did one job at a time. A user handed in a deck of punched cards, an operator fed it to the machine, and the machine ran that job from start to finish — including printing the result. The printer was mechanical and slow. While it clattered through a few hundred lines, the processor, which could have finished thousands of calculations in the same time, sat idle waiting for it.

The fix, worked out on mainframe systems in the 1960s, was to stop making the processor wait. Instead of sending output straight to the printer, a job wrote its output to disk and finished. The printer then drew from the disk at its own pace, printing jobs one after another in the order they had arrived. The technique was named spooling, from Simultaneous Peripheral Operations On-Line, and every print job you send today still passes through a version of it.

Notice what made the idea work. The waiting jobs were kept in a definite order, new jobs joined at one end, and the printer took jobs only from the other end. Nobody’s output overtook anybody else’s, and nothing was lost. That simple discipline — join at the back, leave from the front — is a data structure in its own right, and this chapter is about it.

Fig. 4.0 – A print queue.

Curiosity Corner

Q1. In the print queue above, which job leaves first — the one that arrived first or the one that arrived last? What is that rule called? Q2. A queue has two ends. Why is it not enough to remember just one of them? Q3. What should a program do when someone asks it to remove an element from a queue that is already empty? Q4. Python’s list already has methods to add and remove items. Why, then, do we bother writing separate functions to build a queue out of a list? Q5. Is there a structure that lets you add and remove at both ends? Would it still be a queue?

The chapter that follows will answer each of these questions.

4.1 Introduction to Queue

You have already met one restricted data structure in this book. A stack keeps its elements in order but lets you touch only the most recent one — the last plate placed on the pile is the first plate lifted off. That restriction turned out to be exactly right for undo lists and for expression evaluation, where the newest item is always the one you need next.

Not every problem works that way. A printer, a ticket counter, a helpline and a school office all deal with requests that must be served in the order they arrived. Serving the newest request first would be unfair, and in a computer system it would mean that an early request could be left waiting forever while newer ones kept overtaking it. What these situations need is the opposite discipline: whoever came first, goes first.

A queue is a data structure built on precisely that discipline. It is an ordered linear collection of elements in which new elements are added at one end and existing elements are removed from the other end. Because the two operations happen at two different ends, the order of arrival is preserved automatically — no element can jump ahead of an element that was already waiting.

The word is borrowed from ordinary English, and the borrowing is honest. A queue at a bus stop behaves in exactly the way the data structure does: you join at the back, you wait, and you board when everyone who arrived before you has boarded.

Definition

(A queue is an ordered linear collection of elements in which insertion of a new element is allowed only at one end, and deletion of an element is allowed only at the other end.)

Notice how much the definition forbids. You may not insert an element into the middle of a queue, you may not remove an element from the middle, and you may not remove the element you inserted most recently unless it happens to be the only one left. A structure that allowed any of these would be a list, not a queue.

4.1.1 First In First Out (FIFO)

The rule a queue obeys has a standard name: first in first out (FIFO). The element that entered the queue earliest is the element that leaves it earliest, and the element that has been waiting longest is always the next one to go. The same rule is also called first come first served (FCFS), especially when the elements represent requests being serviced rather than data being stored.

Consider four job codes entering an empty queue in the order J1, J2, J3, J4. When removal begins, J1 leaves first, then J2, then J3, then J4. The order coming out is identical to the order going in, as Fig. 4.1 shows. This is worth stating carefully, because it is the property that makes a queue useful: a queue does not sort, filter or reorder anything. It simply preserves arrival order across a delay.

Fig. 4.1

Fig. 4.1 – The First In First Out (FIFO) discipline.

Theory Snapshot

The FIFO discipline Statement: In a queue, the element that has been present longest is the next element to be removed. In words: Whatever goes in first comes out first; nothing overtakes anything that was already waiting. Why it holds: Insertion is permitted at one end only and deletion at the other end only, so an element can be removed only after every element ahead of it has already been removed. Used for: Servicing requests in arrival order, buffering data between a fast producer and a slow consumer, and scheduling work fairly. Watch out: FIFO is fair, but it is not sensitive to urgency. An important item that arrives late still waits behind every ordinary item that arrived earlier.

Because you have just studied the stack, the contrast between the two disciplines is worth drawing sharply. Both are ordered linear structures with restricted access; the restriction is what differs, and everything else follows from it.

Compare Table

The last row of Table 4.1 explains why neither structure is “better”. A pile of plates is convenient because you take the plate you last washed; a ticket counter is fair because it serves the person who has waited longest. The problem decides which discipline is correct.

Curiosity Corner

Q1. In the print queue above, which job leaves first — the one that arrived first or the one that arrived last? What is that rule called?

A. The job that arrived first leaves first. Waiting jobs join at one end and are taken from the other, so no later job can overtake an earlier one. The rule is called first in first out, or FIFO, and it is also described as first come first served.

Try Yourself

List five queues you meet in an ordinary day — at school, at home, on the road. For each one, write down which end people join and which end they leave from, and note any case where somebody is allowed to break the FIFO rule.

4.1.2 Front and Rear of a Queue

A stack needs only one marker, because both of its operations happen at the top. A queue needs two, because its two operations happen at opposite ends, and each end must be identified separately.

The end at which new elements are added is called the rear of the queue; it is also called the tail. The end from which elements are removed is called the front; it is also called the head. In Fig. 4.2 the front is drawn at the left and the rear at the right, and the two arrows show clearly that traffic moves in one direction only — in at the rear, along the queue, and out at the front.

Fig. 4.2

Fig. 4.2 – Front and rear of a queue.

Both ends change as the queue is used, and they change independently. Adding an element moves the rear outward but leaves the front where it was. Removing an element moves the front inward but leaves the rear where it was. This is the practical reason the earlier question matters: if a program remembered only one end, it would know where to add elements but not where to take them from, or the reverse.

Curiosity Corner

Q2. A queue has two ends. Why is it not enough to remember just one of them?

A. Because the two operations of a queue use different ends. New elements are added at the rear and existing elements are removed from the front, and the two ends move independently as the queue grows and shrinks. Knowing only one of them would leave the program unable to carry out one of its two basic operations.

When a queue is stored in a Python list, the choice of which end of the list plays which role is yours to make, but it must be made once and then kept. If index 0 is treated as the front, then the last index is the rear and every insertion must happen there; swapping the roles halfway through would destroy the FIFO order. Section 4.3 takes up this choice in detail.

4.1.3 Applications of Queue

A queue is not an artificial classroom construction. Wherever items must wait their turn, a queue is either already present or is the structure that should be used, and it is worth seeing this in both the everyday world and inside a computer.

4.1.3.1 Applications in Everyday Life

Think of a railway reservation that has not been confirmed. A waiting-list ticket carries a number, and the numbers are served in increasing order: when a confirmed passenger cancels, the seat goes to the waiting-list ticket at the front, not to whichever passenger happens to be standing at the counter. The waiting list is a queue, and the ticket number is simply a record of the position in it.

A helpline works the same way. When you call and hear that all executives are busy, your call has been placed at the rear of a queue of waiting callers. Each time an executive becomes free, the call at the front is connected. The recorded message that tells you your position is reading out how far you are from the front.

Roads offer a third example. On a single-lane one-way stretch, or in the lane approaching a toll booth, no vehicle can overtake another, so the vehicle that entered the lane first is the vehicle that leaves it first. The physical arrangement enforces FIFO even though nobody is managing it.

4.1.3.2 Applications in Computer Science

Inside a computer, queues appear wherever one part of the system produces work faster than another part can consume it.

A web server is a clear case. A school’s result website may be able to serve a limited number of requests at the same time, but on the morning results are declared, tens of thousands of requests may arrive. The requests that cannot be served immediately are held in a queue and taken up in arrival order, so that every visitor is eventually served and none is dropped because newer requests kept arriving.

Task scheduling in an operating system is a second case. A processor can execute only one task at any instant, yet a modern system always has many tasks wanting to run. The waiting tasks are held in a queue, and the simplest scheduling policy is to give the processor to the task at the front — that is, to run tasks in the order in which they asked for the processor.

Queues also sit between devices that work at very different speeds. When you type quickly, the characters do not go straight into the program; they are held in a small queue called a buffer and delivered in the order typed, so that nothing is lost and nothing arrives out of sequence. The same idea is used when data arriving over a network is held until the receiving program is ready to read it.

Side Note

Notice the pattern common to all these examples. A queue is used when the work cannot be done at once, the order of arrival matters, and no item may be discarded. If any one of those three conditions is missing, some other structure is usually the better choice.

Try Yourself

In the school results example, suppose the school administrator’s request must be attended to before the students’ requests, even though it arrives later. Write down, in two or three sentences, how you would arrange the waiting requests so that urgent ones are served early without any ordinary request being left waiting forever.

4.2 Operations on Queue

A data structure is defined as much by what you are allowed to do with it as by how it stores its elements. For a queue, the permitted actions follow directly from the FIFO discipline: something must put an element in at the rear, something must take an element out at the front, and a few small helper actions are needed so that these two can be carried out safely.

There are two principal operations, enqueue and dequeue, and three supporting ones — is empty, peek and is full. The supporting operations do not change the contents of the queue; they report on it, so that the principal operations are not attempted at a moment when they cannot succeed.

4.2.1 Enqueue and Overflow

Adding a new element to a queue is called an enqueue operation. The element is placed at the rear, behind every element already waiting, and the rear then refers to this new element. The front is untouched — unless the queue was empty before the insertion, in which case the single new element is both the front and the rear.

Definition

(Enqueue is the operation that inserts a new element at the rear end of a queue, leaving the order of the existing elements unchanged.)

In Fig. 4.3 a queue holding 31, 47 and 52 receives the element 19. Compare the two rows of the figure carefully: nothing already in the queue has moved, and 19 has simply taken its place behind 52.

Fig. 4.3

Fig. 4.3 – Enqueue operation.

An enqueue can fail. If the queue has been given a fixed capacity — say, storage for at most fifty waiting requests — then an attempt to add an element when all fifty places are occupied cannot be carried out. This situation is called overflow.

Definition

(Overflow is the error condition that arises when an enqueue operation is attempted on a queue that is already holding as many elements as its capacity allows.)

Overflow is a property of the storage, not of the FIFO rule. A queue whose storage can grow as long as memory is available will not overflow in ordinary use, and Section 4.3 explains why this is the situation you meet when a queue is built on a Python list. The condition still matters, because real systems do fix a capacity: a server that accepts an unlimited number of waiting requests will eventually exhaust its memory, so it is safer to refuse the fifty-first request than to accept it and fail unpredictably later.

Algorithm

Enqueue — inserting an element at the rear Input: A queue Q, and the element E to be inserted. Output: Q with E added at its rear end. Method:

1. If Q is full, report overflow and stop.
2. Place E at the rear end of Q, after the element currently at the rear.
3. Treat E as the new rear of Q.
4. If Q had no elements before this insertion, treat E as the front as well.

Why it works: The new element is placed behind every element already waiting, so no waiting element is overtaken and the arrival order is preserved. Watch out: Step 1 must come first. Checking for space after writing the element is too late, and the empty-queue case in step 4 is easy to forget.

4.2.2 Dequeue and Underflow

Removing an element from a queue is called a dequeue operation. The element removed is always the one at the front — the element that has waited longest — and the element behind it becomes the new front. The rear does not move.

Definition

(Dequeue is the operation that removes the element at the front end of a queue and returns it, leaving the order of the remaining elements unchanged.)

Two details in that definition are worth pausing on. First, a dequeue returns the removed element; the value is not thrown away, because the whole point of taking an element out of a queue is to do something with it. Second, only the element at the front may be removed, which is why a queue can never be used to cancel a request sitting in the middle of the line.

Fig. 4.4 shows a dequeue on the queue built in the previous subsection. The value 31 leaves, 47 becomes the front, and 19 remains the rear exactly as before.

Fig. 4.4

Fig. 4.4 – Dequeue operation.

A dequeue can fail too, and it fails far more often than an enqueue does. If the queue holds no elements at all, there is nothing at the front to remove. This condition is called underflow.

Definition

(Underflow is the error condition that arises when a dequeue operation is attempted on a queue that contains no elements.)

Underflow is not an unlikely accident. Any program that keeps serving a queue until it runs dry will reach the empty state as a matter of course, and it will then attempt one dequeue too many unless it has been written to check first. That is exactly what the is-empty operation is for.

Algorithm

Dequeue — removing an element from the front Input: A queue Q. Output: The element that was at the front of Q, with that element removed from Q. Method:

1. If Q is empty, report underflow and stop.
2. Note the element currently at the front of Q.
3. Remove that element from Q.
4. Treat the element behind it as the new front of Q.
5. Return the noted element.

Why it works: The element at the front is the element that entered earliest and is still waiting, so removing it services requests in arrival order. Watch out: Step 2 must happen before step 3 — once the element is removed, its value is no longer available to return. If Q becomes empty after step 3, both the front and the rear cease to refer to any element.

Curiosity Corner

Q3. What should a program do when someone asks it to remove an element from a queue that is already empty?

A. It must recognise the situation as underflow and refuse to remove anything. A dequeue on an empty queue has no element to return, so the program should test whether the queue is empty before attempting the removal, and report the condition instead of trying to take a value that does not exist.

4.2.3 Supporting Operations — Is Empty, Peek and Is Full

The three supporting operations exist so that enqueue and dequeue can be performed without ever running into overflow or underflow.

The is-empty operation reports whether the queue currently holds any element. It answers a question and changes nothing, and it is normally called immediately before a dequeue, so that an empty queue is detected before an impossible removal is attempted.

The peek operation reads the element at the front of the queue without removing it. It is what a cashier does when glancing at the next token number without calling the person forward — the queue is exactly as it was afterwards. Peek is useful whenever a program must decide what to do on the basis of the next element without committing to serving it.

Definition

(Peek is the operation that returns the value of the element at the front of a queue without removing it and without altering the queue in any way.)

Peek fails on an empty queue for the same reason a dequeue does: there is no front element to read. It therefore has to test for emptiness first, just as a dequeue does.

The is-full operation reports whether the queue has room for another element, and it belongs with enqueue in the way that is-empty belongs with dequeue. It is meaningful only where a capacity has been fixed in advance. Where the storage grows on demand, the operation has no useful answer and is simply not implemented.

Compare Table

4.2.4 Tracing a Sequence of Queue Operations

The surest way to be certain that you have understood these operations is to trace a sequence of them by hand, writing down the state of the queue after each one. Table 4.3 does this for a queue that starts empty. The queue is written from front to rear, so the leftmost value is always the one that will leave next.

Table

Table 4.3 – Status of a queue after each operation, with the front element, the rear element and the value returned | Operation | Queue after the operation (front → rear) | Front | Rear | Value returned | |—|—|—|—|—| | enqueue(31) | 31 | 31 | 31 | — | | enqueue(47) | 31, 47 | 31 | 47 | — | | enqueue(52) | 31, 47, 52 | 31 | 52 | — | | dequeue() | 47, 52 | 47 | 52 | 31 | | peek() | 47, 52 | 47 | 52 | 47 | | enqueue(19) | 47, 52, 19 | 47 | 19 | — | | dequeue() | 52, 19 | 52 | 19 | 47 | | dequeue() | 19 | 19 | 19 | 52 | | dequeue() | empty | — | — | 19 | | dequeue() | empty | — | — | underflow |

Read down the last column of Table 4.3 and you will see the values leaving in the order 31, 47, 52, 19 — precisely the order in which they entered. Read the peek row and you will see that it alone changes nothing: the queue before it and the queue after it are the same. The final row is the one to dwell on. The queue had already been emptied by the previous dequeue, so this eleventh operation has nothing to remove, and a correctly written program must report underflow rather than fail.

Two smaller observations fall out of the same table. After the operation enqueue(31), the single element 31 is both the front and the rear, which is what any queue holding exactly one element looks like. And after the ninth operation, both markers cease to refer to anything at all, because an empty queue has neither a front nor a rear.

Try Yourself

Starting from an empty queue, trace this sequence on paper and write out a table like Table 4.3: enqueue(8), enqueue(15), dequeue(), enqueue(23), enqueue(4), dequeue(), peek(), dequeue(), dequeue(), dequeue(). At which step does underflow occur, and what is the complete sequence of values returned?

4.3 Implementation of Queue using Python

So far the queue has been an idea: elements in order, additions at the rear, removals at the front. Python has no built-in type called a queue, so if you want one in a program you must build it. The question is what to build it out of.

The answer, for this chapter, is the list. A Python list already stores elements in a definite order, already allows an element to be added at its end, and already allows an element to be taken out from any position. All of that is more freedom than a queue is supposed to allow — and that, as you will see, is the whole design problem.

4.3.1 Creating a Queue Using a List

You met lists in Class XI. A list holds its elements in positions numbered from 0 upwards, it can hold values of any type, and it can grow or shrink while the program runs. An empty list is created either with a pair of square brackets or with the list() function, and both are used in this chapter:

counter_queue = list()

At this moment counter_queue is an empty list. What makes it a queue is not the list itself but the discipline the program agrees to follow when using it.

That discipline needs one decision taken at the start: which end of the list is the front and which is the rear. Either choice can be made to work, but it must be made once and then never varied. Throughout this chapter, index 0 is the front and the last index is the rear, as Fig. 4.5 shows. Elements will therefore be added at the end of the list and removed from the beginning of it.

Fig. 4.5

Fig. 4.5 – A queue implemented using a Python list.

This raises a fair question: if a list can already add and remove elements, why write functions at all? Because a list can do far more than a queue may. A list allows you to insert a value in the middle, to remove the third element, to sort the whole thing, or to overwrite any position you like. A queue that permitted those actions would no longer preserve arrival order, and the FIFO guarantee would be lost.

Writing enqueue and dequeue as functions turns the discipline into code. Every insertion in the program goes through one function, every removal through another, and the rest of the program never touches the list directly. If the FIFO order is ever broken, there are exactly two places to look.

Curiosity Corner

Q4. Python’s list already has methods to add and remove items. Why, then, do we bother writing separate functions to build a queue out of a list?

A. Because a list permits much more than a queue allows — insertion in the middle, removal from any position, sorting, overwriting. A queue is a list used under a restriction, and the functions are how that restriction is enforced. All insertions pass through enqueue, all removals through dequeue, and the FIFO order is therefore guaranteed by construction rather than by the programmer remembering to be careful.

4.3.2 Inserting an Element — the Enqueue Function

With index 0 fixed as the front, the rear is the end of the list, and adding an element at the end of a list is exactly what the append() method does. The enqueue function is therefore short:

def enqueue(queue, element):
    queue.append(element)

The function takes two parameters — the queue to work on and the element to insert — and it returns nothing, because inserting an element produces no value that the caller needs. The change is made to the list itself. Lists are mutable, so the object the caller passed in is the same object the function modifies, and no value has to be sent back.

Note that no test for overflow appears here. A Python list is not created with a fixed size; it grows as elements are added, for as long as memory allows. There is therefore no state in which the list is “full” and no is-full function to write. Overflow, described in Section 4.2.1, belongs to implementations that reserve a fixed block of storage in advance.

Side Note

This is a genuine convenience, but it is not a free one. A queue that can never be full will also never refuse work, so a program that enqueues faster than it dequeues will simply consume more and more memory. In a real server, the limit that overflow represents is often put back deliberately.

4.3.3 Testing for an Empty Queue

Before anything can be removed from the queue, the program must be able to ask whether the queue holds any element at all. The number of elements in a list is what len() returns, so the test is a comparison against zero:

def is_empty(queue):
    return len(queue) == 0

The expression len(queue) == 0 is itself either True or False, so it can be returned directly. Writing an if that returns True in one branch and False in the other produces the same result, but it says the same thing twice.

This function changes nothing and answers one question. It will be called at the start of every operation that reads or removes the front element, which is why it is written before them.

4.3.4 Removing an Element — the Dequeue Function

Removing the front element means removing the element at index 0, and the list method that removes an element by position is pop().

Syntax Snapshot

removing an element from a list with pop()

list_object.pop(index)

Parts: list_object is the list to remove from; index is the position of the element to be removed, and it is optional. Returns / Effect: The removed element is returned, and it is deleted from the list. Every element after it moves one position closer to the front. If index is omitted, the last element is removed. Example:

tokens = ["T01", "T02", "T03"]
print(tokens.pop(0))
print(tokens)

This prints T01 on the first line and ['T02', 'T03'] on the second.

The optional index is the point on which the whole implementation turns. pop(0) takes the element at the front; pop() with no argument takes the element at the rear. One gives a queue, the other gives a stack.

Compare Table

Common Error

writing pop() where pop(0) was meant What students write:

def dequeue(queue):
    if is_empty(queue):
        print("Queue is empty")
        return None
    return queue.pop()

What happens: No error message appears and the program runs to completion — which is what makes this mistake hard to catch. But the values come out in reverse order: enqueue “T01”, “T02”, “T03” and the first dequeue returns T03, not T01. The structure has silently become a stack. The fix: Write queue.pop(0). The argument names the position to remove from, and the front of this queue is position 0.

Putting the guard and the removal together gives the dequeue function:

def dequeue(queue):
    if is_empty(queue):
        print("Queue is empty")
        return None
    return queue.pop(0)

The order of the two statements matters. The emptiness test comes first, because pop(0) on an empty list raises an IndexError and stops the program. By testing first, the function turns a crash into a message and a return value of None, which the caller can check.

The removal itself also does more than delete a value. As Fig. 4.6 shows, every remaining element shifts down by one position, so that the element which was at index 1 becomes the new element at index 0 — the new front. This shifting is done for you, but it is real work: on a very long queue, removing from the front costs more than removing from the rear, because every surviving element has to be moved.

Fig. 4.6

Fig. 4.6 – Element shifts during a dequeue.

4.3.5 Finding the Size and Reading the Front

Two small functions complete the set. The first reports how many elements are waiting:

def size(queue):
    return len(queue)

The second reads the front element without removing it:

def peek(queue):
    if is_empty(queue):
        print("Queue is empty")
        return None
    return queue[0]

Compare peek with dequeue line by line. The guard is identical and the position is identical; the only difference is that peek uses queue[0], which reads the value at index 0, while dequeue uses queue.pop(0), which reads it and takes it out. That single character of difference is the difference between looking and serving.

4.3.6 A Complete Queue Application

The five functions can now be assembled into a working program. The situation modelled is a token counter at a school library: readers take a token when they arrive, the librarian serves the oldest waiting token, and more readers keep arriving while earlier ones are being served.

Program

Serving tokens at a library counter using a queue Problem: Maintain a queue of token codes. Add three tokens, report how many are waiting and which will be served next, serve one, add two more, serve one, then clear the queue completely and attempt one further removal so that the empty-queue case can be seen. Assumes: No input file. All token codes are fixed in the program.

def is_empty(queue):
    return len(queue) == 0


def enqueue(queue, element):
    queue.append(element)


def dequeue(queue):
    if is_empty(queue):
        print("Queue is empty")
        return None
    return queue.pop(0)


def size(queue):
    return len(queue)


def peek(queue):
    if is_empty(queue):
        print("Queue is empty")
        return None
    return queue[0]


counter_queue = list()

for token in ["T01", "T02", "T03"]:
    enqueue(counter_queue, token)

print("Tokens waiting now:", size(counter_queue))
print("Next token to be served:", peek(counter_queue))
print("Serving:", dequeue(counter_queue))

enqueue(counter_queue, "T04")
enqueue(counter_queue, "T05")
print("Tokens waiting now:", size(counter_queue))
print("Serving:", dequeue(counter_queue))

print("Clearing the remaining tokens")
while not is_empty(counter_queue):
    print("Serving:", dequeue(counter_queue))

print("Serving:", dequeue(counter_queue))

Sample output:

Tokens waiting now: 3
Next token to be served: T01
Serving: T01
Tokens waiting now: 4
Serving: T02
Clearing the remaining tokens
Serving: T03
Serving: T04
Serving: T05
Queue is empty
Serving: None

Identifier description:

Notes: The five functions never assume anything about which queue they are working on, so the same set would serve a second queue in the same program without being rewritten. The final dequeue is deliberate: it shows what the program does when asked for one token too many, printing the message from the guard and returning None.

Read the output alongside the token codes and the FIFO discipline is visible in a single glance — T01, T02, T03, T04, T05 come out in exactly the order they went in, even though T04 and T05 were added after serving had already begun.

The while loop deserves a closer look, because it is the shape that almost every queue-draining program takes. Its condition is not a count; it is the emptiness test itself. The loop keeps serving as long as something is waiting and stops the moment nothing is.

Dry Run

the while loop of the library counter program, entered with the queue holding “T03”, “T04”, “T05” | Check | is_empty(counter_queue) | Queue at the check (front → rear) | Value returned by dequeue | Printed | |—|—|—|—|—| | 1 | False | T03, T04, T05 | T03 | Serving: T03 | | 2 | False | T04, T05 | T04 | Serving: T04 | | 3 | False | T05 | T05 | Serving: T05 | | 4 | True | empty | — | — | Result: Three lines are printed and the loop then ends without a fourth. The trace shows that the loop can never cause underflow, because the emptiness test is re-evaluated before every removal.

The statement after the loop is a different matter. It calls dequeue on a queue that is known to be empty, and the guard inside the function is all that stands between the program and an IndexError.

Try Yourself

The last line of the output reads Serving: None, which is not a sensible thing to show a librarian. Change the program so that this case prints a clear message instead. Do not remove the guard inside dequeue — decide instead what the caller should do with the value it gets back.

Try Yourself

Practical link: This assignment exercises the queue implementation of Section 4.3 and is filed under Python programs in the practical report file. Write a program that maintains a queue of bus route numbers at a depot. Provide the functions enqueue, dequeue, is_empty, size and peek, and a menu that lets the user add a route number, dispatch the bus at the front, view the next route without dispatching it, and display how many buses are waiting. The program must never stop with an error when a dispatch is requested on an empty queue. Test it with a run in which four route numbers are added and six dispatches are attempted.

4.4 Introduction to Deque

A queue is strict about its two ends: one is for entering, the other for leaving, and neither end does the other’s work. That strictness is exactly what makes a queue fair, and for most waiting problems it is what you want.

But some situations do not fit it. Think of a counter where a person who has just been served comes back to collect a receipt, and is allowed to step in at the front rather than walk to the back of the line. Or think of a list of recently visited web pages that is only allowed to hold twenty entries: a new page is added at one end, and when the twenty-first arrives, the oldest entry has to be discarded from the other end. In both cases additions and removals are wanted at both ends.

The structure that permits this is called a deque, pronounced “deck”. The name is short for double ended queue, and it describes a linear structure in which an element may be inserted at either end and removed from either end. Nothing may still be inserted or removed in the middle — that restriction, which a queue and a stack both keep, a deque keeps too.

Definition

(A deque is an ordered linear collection of elements in which insertion and deletion are both permitted at either end — the front and the rear — but at no other position.)

Fig. 4.7 shows why a deque is drawn with four arrows where a queue needs only two.

Fig. 4.7

Fig. 4.7 – Allowed operations on a deque.

Because a deque can do everything a queue can do and everything a stack can do, it can be made to behave as either of them simply by restricting which of its four operations a program uses. Use insertion at the rear together with deletion at the front and you have a queue. Use insertion and deletion at the same end — both at the rear, or both at the front — and the element removed is always the one most recently inserted, which is a stack.

Curiosity Corner

Q5. Is there a structure that lets you add and remove at both ends? Would it still be a queue?

A. Yes — it is called a deque, or double ended queue, and it allows insertion as well as deletion at both the front and the rear. It is not a queue, because it no longer guarantees FIFO order: an element inserted at the front can leave before elements that arrived earlier. A deque is the more general structure, and a queue is what you get when you allow yourself only two of its four operations.

Compare Table

4.4.1 Applications of Deque

Everyday examples of the deque are less common than examples of the queue, because most waiting lines are deliberately strict. They appear wherever a line has a recognised exception at one end.

At a railway ticket window, the ordinary line is a queue. A passenger who has already bought a ticket and returns a minute later to ask about the platform number is often allowed to speak from the front rather than rejoin at the back. Seen as a structure, the line has just accepted an insertion at its front end.

A second example appears where several counters are open. When one counter at a canteen closes, the people still waiting there do not scatter; those at the tail of that line — the last to have joined — leave it and join the tail of a neighbouring line. Elements are being removed from the rear of one structure, which a plain queue would not allow.

In computer science, three uses are worth knowing.

The first is a list of recently used items kept at a fixed length: recently visited pages in a browser, recently opened files in an editor. The newest item is inserted at one end, and when the list is full the oldest item is deleted from the other end. Both ends are in use at once, which is precisely a deque.

The second is the pair of undo and redo facilities in an editor. Actions are added at one end as they are performed and taken back from the same end when undone, while the oldest actions are dropped from the far end once the history grows past its limit.

The third is testing whether a string is a palindrome, and it is the one this chapter works out in full, because it uses both ends of the deque at the same moment.

4.4.2 Operations on Deque

A deque supports four principal operations. Their names say where they act.

INSERTFRONT inserts a new element at the front of the deque. The element becomes the new front, and every element already present is now one place further from it.

INSERTREAR inserts a new element at the rear. This is exactly the enqueue operation of a queue, and it leaves the front untouched.

DELETIONFRONT removes the element at the front and returns it. This is exactly the dequeue operation of a queue.

DELETIONREAR removes the element at the rear and returns it. It is the operation a queue does not have, and it is what allows the oldest — or, depending on how the deque is filled, the newest — element to be discarded from the far end.

The three supporting operations of a queue are needed here too, in slightly extended form. Is empty guards every deletion, exactly as before, since neither end of an empty deque holds anything to remove. Size reports the number of elements. Peek, which reads without removing, now has two versions: one that reads the front element and one that reads the rear element, because either end may be the one a program cares about.

Overflow and underflow mean the same things they meant in Section 4.2, and underflow can now be reached from either side — an attempt at DELETIONFRONT and an attempt at DELETIONREAR fail for the same reason on an empty deque.

Try Yourself

Take an empty deque and perform this sequence, writing down the contents after each step: insertrear(7), insertfront(3), insertrear(11), deletionfront(), insertfront(5), deletionrear(), deletionrear(). State the contents at the end and the values that were removed, in order.

4.4.3 Checking a Palindrome Using a Deque

A palindrome is a string that reads the same forwards and backwards — kayak is one, table is not. Checking a string for this property means comparing its first character with its last, its second with its second-last, and so on inwards.

A deque suits the job because those two characters sit at its two ends. If the characters of the string are inserted one by one at the rear, in the order they occur, the front of the deque holds the first character and the rear holds the last. Removing one character from each end gives exactly the pair that must be compared, and after the removal the next pair is at the two ends, ready for the same treatment.

Algorithm

Checking whether a string is a palindrome using a deque Input: A string S, and an empty deque D. Output: A report of whether S is a palindrome. Method:

1. Read the characters of S from left to right, one at a time.
2. For each character read, insert it into D using INSERTREAR.
3. Repeat step 1 and step 2 until every character of S has been inserted.
4. If D holds fewer than two elements, report that S is a palindrome and stop.
5. Remove one character from the front of D using DELETIONFRONT.
6. Remove one character from the rear of D using DELETIONREAR.
7. Compare the two removed characters.
8. If they are not the same, report that S is not a palindrome and stop.
9. Go back to step 4.

Why it works: Inserting at the rear keeps the characters in their original order, so at every stage the front of the deque holds the outermost unchecked character from the left and the rear holds the outermost unchecked character from the right. Each pass compares one such pair and removes it, so after k passes the first k and the last k characters have been checked against each other. Watch out: The stopping test in step 4 must allow for both lengths. A string of even length empties the deque exactly; a string of odd length leaves its middle character alone in the deque, and that character has nothing to be compared with, so it must not be treated as a failure.

Fig. 4.8 shows the deque for the string kayak at the moment the last character has been inserted, and Table 4.7 traces the comparisons that follow.

Fig. 4.8

Fig. 4.8 – Palindrome check using a deque.

Table

Table 4.7 – Checking the string kayak, showing the deque before each pass and the pair compared | Pass | Deque before the pass (front → rear) | Removed from front | Removed from rear | Do they match? | Deque after the pass | |—|—|—|—|—|—| | 1 | k, a, y, a, k | k | k | Yes | a, y, a | | 2 | a, y, a | a | a | Yes | y | | 3 | y | — | — | Not compared | y |

At the third pass the deque holds a single character, so no pair can be formed and the process stops. Every pair that was formed matched, and the string is therefore reported as a palindrome. Had the string been table, the very first pass would have compared t with e, found them different, and stopped at once — which is worth noticing, because a mismatch anywhere ends the work immediately, while a palindrome must be checked all the way in.

Try Yourself

Trace this algorithm on paper for the string noon, in a table like Table 4.7. How many passes are made, and how many elements are left in the deque when the process stops? Compare your answer with the trace for kayak and state the general rule connecting the length of the string to what is left at the end.

4.5 Implementation of Deque Using Python

A deque, like a queue, is an ordered linear collection, so a Python list can hold its elements just as well. What changes is the set of functions written around the list. A queue needed one insertion function and one deletion function; a deque needs two of each, because both ends are working ends.

The convention of Section 4.3 is kept throughout: index 0 is the front and the last index is the rear. Every function below is written against that convention, and mixing it with the opposite one halfway through a program would make the results meaningless.

Table 4.8 shows the whole implementation in outline before any of it is written. Read it as a plan: each deque operation becomes one function, and each function is one list operation with a guard in front of it where a guard is needed.

Table

The two insertion functions need no guard because a Python list has no fixed capacity, exactly as in Section 4.3.1. The four functions that touch an existing element all need one, because an empty deque has no element at either end.

4.5.1 Creating a Deque and Inserting at Both Ends

A deque begins as an empty list, and the two supporting functions are written first because everything else calls them.

my_deque = list()


def is_empty(deque):
    return len(deque) == 0


def size(deque):
    return len(deque)

Insertion at the rear is the operation you already know. It adds the element after the last one, and append() does it directly.

def insert_rear(deque, element):
    deque.append(element)

Insertion at the front is new. The element must be placed before the current first element, so that it becomes the element at index 0, and the list method for putting a value at a stated position is insert().

def insert_front(deque, element):
    deque.insert(0, element)

Syntax Snapshot

inserting an element at a stated position in a list

list_object.insert(index, item)

Parts: list_object is the list to insert into; index is the position the new element is to occupy; item is the value being inserted. Returns / Effect: Returns nothing. item is placed at index, and every element from that position onwards moves one place further along, so the list grows by one. Example:

>>> stops = ["B2", "B3"]
>>> stops.insert(0, "B1")
>>> stops
['B1', 'B2', 'B3']

The phrase “every element moves one place further along” is the part worth picturing, and Fig. 4.9 shows it. Nothing is overwritten: the value that was at index 0 is still present, now at index 1.

Fig. 4.9

Fig. 4.9 – Element shifts during an insert at the front.

Notice that insert_rear and insert_front differ only in where the element lands, and that the difference costs something. Appending at the rear leaves the existing elements exactly where they are; inserting at the front moves every one of them. On a short deque this is not worth thinking about, but on a very long one it is real work done on every insertion.

4.5.2 Deleting from Both Ends

Both deletion functions follow the same shape as dequeue in Section 4.3.4: test for emptiness, then remove and return.

def deletion_front(deque):
    if is_empty(deque):
        print("Deque is empty")
        return None
    return deque.pop(0)


def deletion_rear(deque):
    if is_empty(deque):
        print("Deque is empty")
        return None
    return deque.pop()

The only difference between the two lies in the argument to pop(). With 0 it removes the front element; with no argument at all it removes the last one, which here is the rear. In Section 4.3 the argument-free form was a mistake to be avoided; in a deque it is a required operation with a name of its own. The method has not changed — the structure has.

Common Error

calling the guard function without its argument What students write:

def deletion_rear(deque):
    if not is_empty():
        return deque.pop()
    else:
        print("Deque is empty")

What happens: The program stops at the first call with TypeError: is_empty() missing 1 required positional argument: 'deque'. The function is_empty needs to be told which deque to examine, and it has no way of knowing that the caller meant the one it is working on. The fix: Pass the deque through — if not is_empty(deque):. A function receives nothing except what it is given in its arguments, however obvious the intended value may look in the surrounding code.

Both functions return None after reporting an empty deque, so a caller can tell the difference between a value that was removed and a removal that did not happen. And because either end can be asked, underflow can now be reached from two directions, though the guard against it is the same test in both.

4.5.3 Reading the Front and the Rear

Peeking needs two functions as well, one for each end.

def get_front(deque):
    if is_empty(deque):
        print("Deque is empty")
        return None
    return deque[0]


def get_rear(deque):
    if is_empty(deque):
        print("Deque is empty")
        return None
    return deque[len(deque) - 1]

The front element is at index 0, which is fixed. The rear element is at the last index, and the last index of a list of n elements is \(n-1\) — which is what len(deque) - 1 computes. The subtraction is necessary because positions are counted from 0, so a deque holding five elements uses indices 0 to 4.

Neither function changes the deque. Calling get_rear twice in succession returns the same value twice, while calling deletion_rear twice returns two different values and leaves the deque two elements shorter.

Side Note

Python’s standard library also provides a ready-made double-ended structure in its collections module. It is worth knowing that it exists, but building the structure from a list is how you learn what it is actually doing, and it is the approach used throughout this chapter.

4.5.4 A Complete Deque Application

The palindrome test of Section 4.4.3 can now be written as a program. It is a good test of the implementation because it uses three of the four principal operations — characters go in at the rear, and they come out from both ends at once.

The algorithm is already established, so the work here is to translate it faithfully, and one detail of the translation deserves attention in advance. The algorithm stops when fewer than two elements remain, which becomes the loop condition while size(deque) > 1. Written this way, the loop handles a string of odd length and a string of even length without any separate case: an odd-length string ends with its middle character still in the deque, and an even-length string ends with the deque empty.

Program

testing strings for the palindrome property using a deque Problem: For each string in a given list, report whether it is a palindrome. Insert the characters of the string at the rear of a deque, then repeatedly remove one character from the front and one from the rear and compare them, stopping as soon as a pair does not match. Assumes: No input file. The strings to be tested are fixed in the list words.

def is_empty(deque):
    return len(deque) == 0


def size(deque):
    return len(deque)


def insert_rear(deque, element):
    deque.append(element)


def deletion_front(deque):
    if is_empty(deque):
        print("Deque is empty")
        return None
    return deque.pop(0)


def deletion_rear(deque):
    if is_empty(deque):
        print("Deque is empty")
        return None
    return deque.pop()


def is_palindrome(text):
    char_deque = list()
    for letter in text:
        insert_rear(char_deque, letter)
    while size(char_deque) > 1:
        first = deletion_front(char_deque)
        last = deletion_rear(char_deque)
        if first != last:
            return False
    return True


words = ["level", "python"]

for word in words:
    if is_palindrome(word):
        print(word, "is a palindrome")
    else:
        print(word, "is not a palindrome")

Sample output:

level is a palindrome
python is not a palindrome

Notes: is_palindrome builds a fresh deque on every call, so each string is tested independently and no leftover character can affect the next test. The return False inside the loop ends the work at the first mismatch, which is why a long non-palindrome costs no more than one comparison. insert_front, get_front and get_rear are not needed by this task and are therefore not included; the functions of Sections 4.5.1 to 4.5.3 form a toolkit, and a program uses the part of it the problem calls for.

Dry Run

is_palindrome(“level”), from the moment all five characters have been inserted | Pass | char_deque at the start of the pass (front → rear) | size(char_deque) | first | last | first != last | |—|—|—|—|—|—| | 1 | ['l', 'e', 'v', 'e', 'l'] | 5 | 'l' | 'l' | False | | 2 | ['e', 'v', 'e'] | 3 | 'e' | 'e' | False | | 3 | ['v'] | 1 | — | — | loop not entered |

Result: The function returns True. The trace shows the deque shrinking by two characters per pass and the loop stopping with the middle character 'v' still inside, never compared with anything — which is exactly what an odd-length palindrome should leave behind.

Try Yourself

Change the list words to ["noon", "level", "queue"] and predict the three output lines before running the program. Then modify is_palindrome so that it also reports how many comparisons it made for each string, and check your prediction of which string cost the fewest.

4.6 Summary

A queue is an ordered linear collection of elements in which insertion is allowed only at one end and deletion only at the other end. No element may be inserted into, or removed from, the middle.
Because the two operations use two different ends, the order of arrival is preserved automatically. This discipline is called first in first out (FIFO), and it is also known as first come first served (FCFS).
The end at which elements are added is the rear, also called the tail. The end from which elements are removed is the front, also called the head. The two ends move independently, so a program must keep track of both.
A queue does not sort, filter or reorder its elements. Its only contribution is to hold them across a delay without disturbing the order in which they arrived.
The two principal operations are enqueue, which inserts an element at the rear, and dequeue, which removes the element at the front and returns it. A dequeue always removes the element that has waited longest.
Overflow is the error condition reached when an enqueue is attempted on a queue that is already holding as many elements as its capacity allows. Underflow is the error condition reached when a deletion is attempted on a queue that holds no elements at all.
Three supporting operations make the principal ones safe. Is empty reports whether any element is present, peek reads the front element without removing it, and is full reports whether space remains for another element. None of the three changes the contents of the queue.
A queue is built in Python by storing the elements in a list and writing functions that use the list only in the ways a queue permits. The list is chosen because it keeps its elements in order, can be changed after creation, and grows as elements are added.
Once index 0 is fixed as the front and the last index as the rear, insertion means adding at the end of the list, deletion means removing the element at position 0, and peeking means reading the element at position 0 without removing it. The choice of which end is the front must be made once and never varied.
A list carries no fixed capacity, so a queue built on a list never overflows in ordinary use and needs no is-full function. Underflow remains possible, and every function that reads or removes the front element must test for an empty queue before acting.
The functions matter because a list permits far more than a queue allows. Wrapping the permitted actions in named functions is what turns a list into a queue, keeps the emptiness check in one place, and makes the discipline visible to anyone reading the program.
Removing the element at the front shifts every remaining element one position closer to the front. Removing from the rear does not, which is why the two ends of a list are not interchangeable in cost.
A deque, short for double ended queue, permits insertion as well as deletion at both the front and the rear, but still at no other position. It is the more general structure; a queue is what remains when only two of its four operations are used.
The four principal deque operations are INSERTFRONT, INSERTREAR, DELETIONFRONT and DELETIONREAR. The supporting operations of a queue are needed here too, with peek appearing in two versions, one for each end.
A deque can be made to behave as a queue by inserting at one end and deleting at the other, and as a stack by inserting and deleting at the same end. It therefore guarantees no ordering of its own; the program using it decides the order.
Testing a string for the palindrome property is a natural use of a deque. The characters are inserted at the rear in their original order, so the first and last unchecked characters always sit at the two ends and can be removed and compared in one pass.
That test stops when fewer than two elements remain. A string of even length leaves the deque empty; a string of odd length leaves its middle character behind, and that character has nothing to be compared with.
Queues appear wherever work must wait its turn and nothing may be lost — waiting lists, calls held on a helpline, requests arriving faster than a server can answer them, tasks waiting for a processor, and data held between devices of unequal speed. Deques appear wherever a line has a recognised exception at one end, such as a fixed-length list of recent items in which the newest is added at one end and the oldest discarded from the other.
FIFO is fair but not sensitive to urgency. An important element that arrives late still waits behind every ordinary element that arrived earlier, and any system that must serve urgent work early needs something more than a plain queue.

4.7 Key Terms

Deque — an ordered linear collection in which insertion and deletion are both permitted at either end, the front and the rear, but at no position in between.
Dequeue — the operation that removes the element at the front of a queue and returns it, leaving the order of the remaining elements unchanged.
Double ended queue — the full form of deque; the name records that both ends of the structure are working ends.
Enqueue — the operation that inserts a new element at the rear of a queue, leaving the existing elements where they are.
FCFS — first come first served.
FIFO — first in first out.
First come first served (FCFS) — another name for the FIFO discipline, used when the elements of the queue stand for requests waiting to be serviced.
First in first out (FIFO) — the rule a queue obeys, by which the element that entered earliest is the element removed earliest.
Front — the end of a queue from which elements are removed; also called the head.
Head — another name for the front of a queue.
Is empty — the supporting operation that reports whether a queue or deque currently holds any element; it is used to guard every deletion against underflow.
Is full — the supporting operation that reports whether space remains for another element; it is meaningful only where a capacity has been fixed in advance.
LIFO — last in first out.
Overflow — the error condition that arises when an insertion is attempted on a queue that is already holding as many elements as its capacity allows.
Palindrome — a string that reads the same forwards and backwards, so that its first character matches its last, its second matches its second-last, and so on inwards.
Peek — the operation that returns the value of the element at an end of a queue or deque without removing it and without altering the structure.
Queue — an ordered linear collection of elements in which insertion is allowed only at one end and deletion only at the other end.
Rear — the end of a queue at which new elements are added; also called the tail.
Tail — another name for the rear of a queue.
Underflow — the error condition that arises when a deletion is attempted on a queue or deque that contains no elements.

4.8 Points to Ponder

A queue built on a Python list can never be full, and that sounds like an advantage. But a server that never refuses a waiting request will keep accepting work until its memory runs out. Is a fixed capacity, and the overflow condition that comes with it, a limitation of a structure or a safeguard built into it?
A deque can be used as a queue and also as a stack, so it can do everything both of them can. Why, then, is it not simply the structure we always use? What is gained by choosing a structure that refuses to do things you might one day want to do?
Removing an element from the front of a list shifts every remaining element one place closer to the front, while removing from the rear shifts nothing. If a queue were to hold ten lakh elements, would this difference change the way you would choose to store it — and could you keep FIFO behaviour while removing from the end of a list instead?
FIFO is described as fair, and in a ticket queue that seems clear enough. But in an operating system, a very short task may wait behind a very long one that arrived a moment earlier. Is serving in arrival order the same thing as serving fairly, and how would you decide?
The palindrome check empties the deque as it works, so the string cannot be examined again afterwards. Is destroying the structure an acceptable price for the method, and would a version that leaves the deque intact still be using the deque for what it is good at?
A queue and a stack both restrict access to a single element at a time, yet they are used for completely different kinds of problem. What is it about a problem that tells you, before you write any code, which of the two disciplines it needs?

4.9 Objective Questions

In a queue, a new element is inserted at the ______ and an existing element is removed from the ______.
1. front, front
2. rear, rear
3. rear, front
4. front, rear [1 mark]
A queue is stored in a Python list with index 0 fixed as the front. Which list operation correctly removes one element from the queue?
1. queue.pop()
2. queue.pop(0)
3. queue.append(0)
4. queue.insert(0, element) [1 mark]
An attempt is made to remove an element from a queue that holds no elements. This situation is called
1. overflow
2. underflow
3. traversal
4. peek [1 mark]
Which of these operations leaves the number of elements in a queue unchanged?
1. enqueue
2. dequeue
3. peek
4. insertrear [1 mark]
Assertion (A): A deque can be made to behave as a stack. Reason (R): A deque permits insertion and deletion at both of its ends.
1. Both A and R are true, and R is the correct explanation of A.
2. Both A and R are true, but R is not the correct explanation of A.
3. A is true but R is false.
4. A is false but R is true. [1 mark]
Assertion (A): A queue built on a Python list does not need an is-full operation. Reason (R): A Python list is created with a fixed number of positions that cannot change while the program runs.
1. Both A and R are true, and R is the correct explanation of A.
2. Both A and R are true, but R is not the correct explanation of A.
3. A is true but R is false.
4. A is false but R is true. [1 mark]
Fill in the blanks.
1. The rear of a queue is also known as its ______.
2. The operation that reads the front element of a queue without removing it is called ______.
3. A structure that allows insertion and deletion at both ends is called a ______.
4. Elements ‘M’, ‘N’, ‘P’ and ‘Q’ are enqueued in that order and then removed one at a time. The order in which they are received is ______. [1 mark]
State whether each statement is True or False.
1. A queue allows an element to be removed from any position, provided the order of the rest is preserved.
2. After a peek operation, the number of elements in the queue is one less than before.
3. In a deque, underflow can be caused by a deletion at either end.
4. Inserting at the front of a Python list moves every existing element one position further along. [1 mark]
Write the full form of FIFO, FCFS and LIFO. [1 mark]

4.10 Check Your Concepts

Define a queue, and state the one restriction that distinguishes it from an ordinary list. [2 marks]
Name the two ends of a queue and state which operation acts at each. Why must a program keep track of both ends rather than one? [2 marks]
Differentiate between overflow and underflow, with one example of a situation that produces each. [3 marks]
A queue is stored in a Python list. Explain, with a short example of your own, why the choice of which end is the front must be fixed once and kept for the whole program. [3 marks]
Differentiate between a queue and a deque on four points, and state one task for which a deque is the better choice. [4 marks]
A queue of waiting requests is to be built in Python using a list. Give reasons for each of these design decisions: (i) removing with pop(0) rather than pop(), (ii) testing for emptiness inside the removal function rather than at every place it is called, and (iii) not writing an is-full function at all. [4 marks]
Write a user-defined function dequeue(queue) that removes and returns the front element of a queue stored as a list, and reports the condition if the queue is empty. Then explain, in three or four sentences, why the emptiness test must come before the removal and what your function returns in each of the two cases. [5 marks]

4.11 Output & Debugging

Predict the complete output of the following program.

def enqueue(queue, element):
    queue.append(element)

def dequeue(queue):
    return queue.pop(0)

marks = list()
for value in [12, 25, 8]:
    enqueue(marks, value)

print(dequeue(marks))
enqueue(marks, 40)
print(marks)
print(dequeue(marks))
print(len(marks))

[3 marks]

The following program is meant to serve token codes in the order they arrive, but it does not. State the output it actually produces, explain in one line why the order is wrong, and correct the program by changing a single character.

def is_empty(queue):
    return len(queue) == 0

def dequeue(queue):
    if is_empty(queue):
        print("Queue is empty")
        return None
    return queue.pop()

tokens = list()
for code in ["A1", "A2", "A3"]:
    tokens.append(code)

print(dequeue(tokens))
print(dequeue(tokens))

[3 marks]

Predict the complete output of the following program, and state which end of the deque holds "S2" at the end of it.

def insert_front(dq, element):
    dq.insert(0, element)

def insert_rear(dq, element):
    dq.append(element)

def deletion_rear(dq):
    return dq.pop()

stops = list()
insert_rear(stops, "S1")
insert_front(stops, "S2")
insert_rear(stops, "S3")
print(stops)
print(deletion_rear(stops))
print(stops)

[3 marks]

The following program stops with an error instead of printing a value. Name the error, state the line that causes it, and rewrite that line correctly.

def is_empty(queue):
    return len(queue) == 0

def peek(queue):
    if is_empty():
        print("Queue is empty")
        return None
    return queue[0]

waiting = [5, 11, 7]
print(peek(waiting))

[2 marks]

4.12 Case-Based Questions

A small stationery shop prints a bill number for every customer who reaches the billing counter, and the bills are settled strictly in the order the customers arrived. The bill numbers waiting at one moment are held in a queue stored as a Python list, with index 0 as the front:

["B21", "B22", "B23"]

The following operations are then performed on this queue, in the order given:

enqueue("B24")
dequeue()
peek()
dequeue()
dequeue()
dequeue()

a. Show the contents of the queue after each of the six operations, along with the value each operation returns. [2 marks]
b. State at which operation underflow occurs, and explain why it occurs there and not earlier. [1 mark]
c. Write a user-defined function `peek(queue)` that returns the bill number at the front of the queue without removing it, and handles the empty queue safely. [2 marks]

[5 marks]

At a school canteen counter, tokens are normally served in arrival order, but a student who has already collected an order and returns immediately to correct it is allowed to rejoin at the front. The counter therefore keeps its token codes in a deque stored as a Python list, with index 0 as the front. At one moment the deque holds:

["C5", "C6"]

The following operations are then performed, in the order given:

insert_front("C4")
insert_rear("C7")
deletion_rear()
deletion_front()
deletion_front()
deletion_front()
deletion_front()

a. Show the contents of the deque after each of the seven operations. [2 marks]
b. Name the operation at which underflow is reported. [1 mark]
c. Explain why the first operation in the list could not have been carried out if the counter had used a plain queue instead of a deque. [1 mark]

[4 marks]

4.13 Programming Practice

Write a user-defined function count_waiting(queue, limit) that accepts a queue of positive integers representing parcel weights in kilograms, and returns how many of them are greater than limit. The queue must be exactly as it was before the call. Submit the function only, together with one line stating how you have ensured that the queue is unchanged. [3 marks]
A science laboratory issues equipment against request codes, one request at a time, in arrival order. Write a complete program that accepts request codes from the user until the word STOP is entered, storing them in a queue, and then issues them one by one, printing each code as it is issued and a suitable message when no request is left. Define and use the functions enqueue, dequeue and is_empty. Submit the complete program with an identifier description table, and state what your program prints if STOP is the very first input. [4 marks]
Write a complete menu-driven program that maintains a deque of heat numbers for a school sports meet, stored as a Python list. The menu must offer five choices: insert at the front, insert at the rear, delete from the front, delete from the rear, and display the deque from front to rear. Define the functions insert_front, insert_rear, deletion_front, deletion_rear and is_empty, and make sure that a deletion requested on an empty deque prints a message instead of stopping the program with an error. Submit the complete program, an identifier description table, and a record of one test run in which four heat numbers are inserted and six deletions are attempted. [5 marks]