I was about to continue the design and implementation of the single link queue using C++ and decided to write this blog to illustrate the TDD process that I follow when developing code. The initial architecture and design phases have already passed. I am now facing the design, implementation and testing of some methods that could be used around the implementation of dequeue (remove) the next element in a FIFO (First In First Out) fashion.
Please note that I am using C++ and the Visual Studio 2013 IDE running on a Windows 10 platform.
Following is relevant test code that I have written for the dequeue method in C++:
// **** loop inserting elements into the queue ****
for (int i = 1; i <= 5; i++) {
slq->enqueue(i);
}
cout << “main <<< slq: ” << slq->toString() << endl;
// **** loop removing elements from the queue ****
for (int i = 0; i < 6; i++) {
cout << “main <<< i: “ << i << ” dequeue: “ << slq.dequeue() << endl;
}
Note that I included a loop that inserts elements into (at this time empty) 
queue. There are five elements inserted. The following loop is the last piece of code in the test program. Of interest are the indices for the loop. The loop will execute six times and we only have five elements in the queue. The most important item is that the test code invokes the slq->dequeue() method that should remove the node at the head of the queue. At this time the dequeue() method does not exist:
Error 1 error C2228: left of ‘.dequeue’ must have class/struct/union C:\MyProjects\LinkedLists\LinkedLists\Solution.cpp 133 1 LinkedLists
After implementing the dequeue() method all seems to work fine if we disregard that the program crashes as illustrated by the following screen capture:
main <<< i: 0 dequeue: 1
main <<< slq: this: 0x1918068eb20 count: 4 maxCount: 0 head: 0x1918068ebe0 tail: 0x1918068e880
p: 0x1918068ebe0 data: 2 next: 0x1918068e760
p: 0x1918068e760 data: 3 next: 0x1918068e5e0
p: 0x1918068e5e0 data: 4 next: 0x1918068e880
p: 0x1918068e880 data: 5 next: 0x1918068eb20
main <<< i: 1 dequeue: 2
main <<< slq: this: 0x1918068eb20 count: 3 maxCount: 0 head: 0x1918068e760 tail: 0x1918068e880
p: 0x1918068e760 data: 3 next: 0x1918068e5e0
p: 0x1918068e5e0 data: 4 next: 0x1918068e880
p: 0x1918068e880 data: 5 next: 0x1918068eb20
main <<< i: 2 dequeue: 3
main <<< slq: this: 0x1918068eb20 count: 2 maxCount: 0 head: 0x1918068e5e0 tail: 0x1918068e880
p: 0x1918068e5e0 data: 4 next: 0x1918068e880
p: 0x1918068e880 data: 5 next: 0x1918068eb20
main <<< i: 3 dequeue: 4
main <<< slq: this: 0x1918068eb20 count: 1 maxCount: 0 head: 0x1918068e880 tail: 0x1918068e880
p: 0x1918068e880 data: 5 next: 0x1918068eb20
main <<< i: 4 dequeue: 5
main <<< slq: this: 0x1918068eb20 count: 0 maxCount: 0 head: 0x1918068eb20 tail: 0x1918068eb20
The issue appears when we attempt to remove (dequeue) an element after the queue is empty. The issue is caused by the following code part of the dequeue() method:
// **** check if the queue is empty ****
if (count <= 0) {
throw QueueIsEmpty;
}
We could address the issue with the test code as follows:
// **** dequeue and display the value from the next element ****
try {
cout << “main <<< i: ” << i << ” dequeue: ” << slq->dequeue() << endl;
} catch (int ex) {
cerr << “main <<< EXCEPTION – dequeue() ex: ” << ((ex == slq->QueueIsEmpty) ? “QueueIsEmpty” : “UNKNOWN exception”) << endl;
break;
}
The console would now display:
main <<< i: 4 dequeue: 5
main <<< slq: this: 0x2c98015e5d0 count: 0 maxCount: 0 head: 0x2c98015e5d0 tail: 0x2c98015e5d0
main <<< EXCEPTION – dequeue() ex: QueueIsEmpty
Perhaps there is a more elegant way to address this issue.
// **** loop removing elements from the queue ****
for (int i = 0; i < 6; i++) {
// **** check if the queue is empty ****
if (slq->getCount() <= 0) {
break;
}
// **** dequeue and display the value from the next element ****
try {
cout << “main <<< i: ” << i << ” dequeue: ” << slq->dequeue() << endl;
} catch (int ex) {
cerr << “main <<< EXCEPTION – dequeue() ex: ” << ((ex == slq->QueueIsEmpty) ? “QueueIsEmpty” : “UNKNOWN exception”) << endl;
break;
}
// **** display the contents of the queue ****
cout << “main <<< slq: ” << slq->toString() << endl;
}
Take a look at the following partial screen capture:
main <<< i: 4 dequeue: 5
main <<< slq: this: 0x2069024ed50 count: 0 maxCount: 0 head: 0x2069024ed50 tail: 0x2069024ed50
main <<< queue is empty :o(
It looks better. The test code follows:
// **** check if the queue is empty ****
if (slq->getCount() <= 0) {
cout << “main <<< queue is empty :o(” << endl;
break;
}
We made us of a getter method which we just implement after we attempt to call a non existing method. Let’s try yet a more elegant approach:
The test code would no look as follows:
// **** loop removing elements from the queue ****
while (!slq->isEmpty()) {
// **** dequeue and display the value for the next element ****
cout << “main <<< i: ” << i << ” dequeue: ” << slq->dequeue() << endl;
// **** display the contents of the queue ****
cout << “main <<< slq: ” << slq->toString() << endl;
}
After implementing the isEmpty() method the screen capture for the console follows:
main <<< dequeue: 1
main <<< slq: this: 0x231a340ee20 count: 4 maxCount: 0 head: 0x231a340eee0 tail: 0x231a340ec40
p: 0x231a340eee0 data: 2 next: 0x231a340ea60
p: 0x231a340ea60 data: 3 next: 0x231a340e880
p: 0x231a340e880 data: 4 next: 0x231a340ec40
p: 0x231a340ec40 data: 5 next: 0x231a340ee20
main <<< dequeue: 2
main <<< slq: this: 0x231a340ee20 count: 3 maxCount: 0 head: 0x231a340ea60 tail: 0x231a340ec40
p: 0x231a340ea60 data: 3 next: 0x231a340e880
p: 0x231a340e880 data: 4 next: 0x231a340ec40
p: 0x231a340ec40 data: 5 next: 0x231a340ee20
main <<< dequeue: 3
main <<< slq: this: 0x231a340ee20 count: 2 maxCount: 0 head: 0x231a340e880 tail: 0x231a340ec40
p: 0x231a340e880 data: 4 next: 0x231a340ec40
p: 0x231a340ec40 data: 5 next: 0x231a340ee20
main <<< dequeue: 4
main <<< slq: this: 0x231a340ee20 count: 1 maxCount: 0 head: 0x231a340ec40 tail: 0x231a340ec40
p: 0x231a340ec40 data: 5 next: 0x231a340ee20
main <<< dequeue: 5
main <<< slq: this: 0x231a340ee20 count: 0 maxCount: 0 head: 0x231a340ee20 tail: 0x231a340ee20
I agree this is a simple example but developers should always attempt to use a TDD approach. It not only helps creating tested code but helps improving the design and in cases the architecture of the software.
If you have comments or questions regarding this or any other post please do not hesitate and send me a message. I will respond as soon as possible.
John
john.canessa@gmail.com
Follow me on Twitter: @john_canessa