Extra Lab Exercise
ADTs and Queues
Objectives
- 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
Admin
This lab is not marked and there is no submission for it.
Background
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.
Setting Up
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, onlytestArrayQueue
passes all the tests, as theListQueue
andCircularArrayQueue
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 intestQueue.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
Task 1
Complete the ListQueue
implementation by implementing the enqueuing and dequeuing functions in ListQueue.c
.
To get an idea of how these functions should behave, you can refer to the diagrams above. You must implement the functions as described above.
Once you think you have got the functions working, recompile and run the tests for ListQueue
:
make ... ./testListQueue
If you get an assertion failed message, that means you didn't pass all the tests, and you'll need to fix your code. For example, here is one error message you might get:
./testListQueue testListQueue: testQueue.c:32: testQueue1: Assertion `QueueSize(q) == 10' failed. Aborted
This particular message says that the assertion on line 32 of testQueue.c
failed, and hence you should go to line 32 of testQueue.c
, see what the test does, and then try to figure out where your code is going wrong.
Once you pass tests 1 to 4, you can be fairly certain that your ListQueue
implementation works.
Task 2
Complete the CircularArrayQueue
implementation by implementing the enqueuing and dequeuing functions in CircularArrayQueue.c
.
To get an idea of how these functions should behave, you can refer to the diagrams above. You must implement the functions as described above.
Keep in mind that your enqueuing function must be able to handle the situation where the array containing the items is full and needs to be expanded. You may implement the expansion in any way you want, as long as it allows the queue to continue behaving as expected (i.e., items should always be dequeued in the same order as they were enqueued). You do not need to reduce the size of the array if the number of items goes below a certain threshold.
Once you think that you have got the functions working, recompile and run the tests for CircularArrayQueue
:
make ... ./testCircularArrayQueue
Unlike in the previous task, passing tests 1 to 4 does not guarantee that your implementation is correct. We strongly recommend that you add at least one more test to testQueue.c
to cover some additional cases, especially those that exercise the array-resizing part of your implementation.
You may add as many tests or as few tests as you like. You will not be submitting your tests, and you will not be marked on your tests. However, note that the given tests do not cover all the cases that your code is expected to handle, so if you choose not to write any tests, you may not know whether your code handles these cases correctly.