Extra Lab Exercise

• To acquaint you with the queue ADT
• To understand the difference between interface and implementation in ADTs
• To manipulate a list-based data structure
• To manipulate an array-based data structure
• To implement core queue operations

This lab is not marked and there is no submission for it.

At the end of COMP1511, you may have learned about the stack ADT, a last-in first-out (LIFO) collection of elements. Very closely related is the queue ADT, which is first-in first-out (FIFO). Since the queue is an important data structure that we'll be using in some tree and graph algorithms later, it will be useful to have a look at it in more detail.

Queues

You should be reasonably familiar with the concept of a queue in the real world. The way it works in computing is exactly the same! A queue is a linear data structure, with a front and a back. Items enter the queue by joining the back of the queue, and items are removed one at a time from the front of the queue. The operations of adding an item to the back and removing an item from the front are known as enqueuing and dequeuing respectively.

ADTs

A queue is an example of an abstract data type (ADT), which is a data type whose implementation details are hidden from the user. This means that users of an ADT do not have access to its internal representation, and thus cannot access or manipulate the data directly. Instead, users must interact with the ADT through its interface, which defines the operations that are allowed to be performed on the ADT.

In terms of code, the interface to an ADT is defined in its header (*.h) file, and consists of a collection of function declarations. The implementation of these functions are contained in the corresponding *.c file. Only the header file is #included in the main program, which means that users of the ADT do not have access to the internal representation of the ADT (i.e., the fields contained in the struct) and do not know how the functions declared in the header file are implemented.

You can think of an ADT as a box with buttons on the outside corresponding to each of the operations that can be performed on the ADT. For example, the queue ADT has two main operations: enqueue and dequeue. If a user enqueues some items, they can expect that when they dequeue, they will get the items back in the same order, because that is how a queue is expected to work. The user is not concerned with the mechanism inside the box (the implementation).

Queue Implementations

A queue can be implemented in several different ways, for example, using a linked list or using an array. Although each implementation should produce the same queue-like behaviour, some implementations may be more efficient than others so it is important to analyse the implementations and choose the right one to use. Here are the different queue implementations we will explore:

List Queue

In this implementation, the items in the queue are stored in a linked list. To enqueue an item, the item is added to the end of the list, and to dequeue an item, the item is removed from the beginning of the list. To enable both operations to be efficient, the queue contains pointers to the first and last nodes in the list. Here are some diagrams demonstrating the enqueue and dequeue operations on the list queue:

After enqueuing 5:

After dequeuing 3:

Array Queue

In this implementation, the items in the queue are stored in an array. To enqueue an item, the item is simply placed in the next available slot in the array, and to dequeue an item, the item at index 0 is removed and the rest of the items are shifted down. Since the implementation uses an array, the array may become full and if more items need to be inserted, the array will need to be expanded. Also, since the array will usually not be full, we will need to keep track of both the number of items (i.e., the size of the queue) and the size of the array (i.e., the capacity). Here are some diagrams demonstrating the enqueue and dequeue operations on the array queue:

After enqueuing 5:

After dequeuing 3:

The following diagrams show the behaviour of the array queue when the queue becomes full and more items need to be inserted:

After enqueuing 5:

To make room for the new item, the array is resized to double its original size. Note that the capacity field is updated to reflect the new size of the array.

Circular Array Queue

This implementation is similar to the array queue, except that when we dequeue, we don't shift the rest of the items down - we simply leave them and the next index becomes the front of the queue. If the front of the queue was at the end of the array, then it circles back to the start of the array (which is where the name circular array comes from). If enough enqueues and dequeues are performed, the queue may circle around the array many times. Since the front of the queue is not necessarily at index 0 anymore, another variable is needed to keep track of the index containing the item at the front of the queue. The following diagrams demonstrate the behaviour of the queue:

After enqueuing 5:

After dequeuing 3:

When enough enqueues and dequeues are performed, the back of the queue will wrap around the end of the array, as shown in the following diagrams:

After enqueuing 3:

Note that when the array becomes full, we will still need to resize the array if another item needs to be enqueued. One of the tasks in this lab will involve working out what needs to be done during a resizing.

Create a directory for this lab, change into it, and run the following command:

unzip /web/cs2521/24T1/labs/week12/downloads/files.zip

If you're working at home, download files.zip by clicking on the above link and then run the unzip command on the downloaded file.

If you've done the above correctly, you should now have the following files:

Makefile

a set of dependencies used to control compilation

Queue.h

interface to the Queue ADT

ListQueue.c

implementation of the Queue ADT using a linked list (incomplete)

ArrayQueue.c

implementation of the Queue ADT using an array (complete)

CircularArrayQueue.c

implementation of the Queue ADT using a circular array (incomplete)

testQueue.c

tests for the Queue ADT

runQueue.c

interactive test program for the Queue ADT

Before you start using these programs, it's worth having a quick look at the code, especially the Queue ADT interface and its various implementations. If there are any constructs you don't understand, ask your tutor.

Once you've understood the programs, run the command:

make

This will leave these executable files in your working directory (along with some .o files):

testListQueue, testArrayQueue, testCircularArrayQueue

These executables run tests on each of the queue implementations. All of the tests come from the same source file testQueue.c - you should read this file to see what the tests do. Currently, only testArrayQueue passes all the tests, as the ListQueue and CircularArrayQueue implementations are incomplete. Once you've got both of them working, all programs should produce the following output:

./testListQueue
Test 1...
Passed!
Test 2...
Passed!
Test 3...
Passed!
Test 4...
Passed!
Test 5...
This is left blank for you to add your own test.

As the output suggests, we recommend you to add your own test to the testQueue5() function in testQueue.c, as the given tests may not cover all the possible edge cases.

runListQueue, runArrayQueue, runCircularArrayQueue

These executables allow you to test the queue implementations interactively by entering commands in the terminal. Here is an example run of the program (once you've got the queue implementations working):

./runListQueue
Interactive Queue Tester
Enter ? to see the list of commands.
> ?
Commands:
    + <num>              enqueue an element
    -                    dequeue an element
    f                    get the front element
    s                    get the queue size
    d                    call QueueDebugPrint
    ?                    show this message
    q                    quit

> + 3
Enqueued 3
> + 1
Enqueued 1
> + 4
Enqueued 4
> s
Queue size is 3
> f
Front element is 3
> -
Dequeued 3
> -
Dequeued 1
> f
Front element is 4
> -
Dequeued 4
> s
Queue size is 0
> q