Exercises

1.

Write the enqueue function for the Array Based Queue.

You do not need to worry about the queue being full, but you should correctly handle wrapping back around to 0 when the end index reaches the end of the array.

🔗

2.

Write the dequeue function for the Array Based Queue.

🔗

Make sure to correctly handle wrapping around to 0 when the start index reaches the end of the array.

🔗

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

import ArrayBasedQueue;

#include <iostream>
using namespace std;

^^^!
          
template<typename T>
T Queue<T>::dequeue() {
    if (empty()) {
        throw out_of_range("Dequeue on empty queue");
    }
    // Write your code here
}
===!

// doctest.h already included

TEST_CASE("Dequeue1") {
  Queue<char> q;

// cheat a little
  q.list[0] = 'A';
  q.list[1] = 'B';
  q.list[2] = 'C';
  q.end = 3;

char x = q.dequeue();

INFO(q.toString());
  REQUIRE(q.start == 1);
  REQUIRE(q.end == 3);
  REQUIRE(x == 'A');
}

TEST_CASE("DequeueMultiple") {
  Queue<char> q;

// cheat a little
  q.list[0] = 'A';
  q.list[1] = 'B';
  q.list[2] = 'C';
  q.end = 3;

char x = q.dequeue();
  char y = q.dequeue();
  char z = q.dequeue();

INFO(q.toString());
  REQUIRE(x == 'A');
  REQUIRE(y == 'B');
  REQUIRE(z == 'C');
}

TEST_CASE("WrapStart") {
  Queue<char> q;
  
  // cheat a little
  q.list[6] = 'A';
  q.list[7] = 'B';
  q.list[0] = 'C';
  q.list[1] = 'D';
  q.start = 6;
  q.end = 2;

q.dequeue();
  q.dequeue();
  q.dequeue();
  INFO(q.toString());
  REQUIRE(q.start == 1);
  REQUIRE(q.end == 2);

q.dequeue();
  INFO(q.toString());
  REQUIRE(q.start == 2);
  REQUIRE(q.end == 2);
}

🔗

3.

Write the full function for the Array Based Queue.

🔗

You will need your enqueue and dequeue functions.

🔗

Hint.

Remember that there are two cases for detecting when the queue is full. Normally, we just want to know if the end index is one position behind the start index. But, if the start index is at 0, the queue is full if end reaches the last position in the array.

🔗

4.

Write the grow function for the Array Based Queue.

🔗

It should double the size of the underlying array and copy the existing elements to the new array in the correct order.

🔗

You will need your enqueue and dequeue functions.

🔗

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

import ArrayBasedQueue;

#include <iostream>
using namespace std;

^^^!
          
// Paste your enqueue and dequeue implementations here

template<typename T>
void Queue<T>::grow() {
    // Write your code here
}
===!

void addTestData(Queue<char>& q) {
  for (int i = 0; i < 6; i++)
    q.enqueue(static_cast<char>('A' + i));
}

// doctest.h already included

TEST_CASE("Grow") {
  Queue<char> q;
  addTestData(q); // A B C D E F
  q.grow();

INFO(q.toString());
  REQUIRE(q.dequeue() == 'A');
  REQUIRE(q.dequeue() == 'B');
  REQUIRE(q.dequeue() == 'C');
  REQUIRE(q.dequeue() == 'D');
  REQUIRE(q.dequeue() == 'E');
  REQUIRE(q.dequeue() == 'F');
}

TEST_CASE("GrowAfterWrap") {
  Queue<char> q;
  addTestData(q); // A B C D E F
  for (int i = 0; i < 6; i++)
    q.dequeue();
  q.enqueue('G');
  q.enqueue('H');
  q.enqueue('I');
  q.enqueue('J');

q.grow();

INFO("After grow:" << q.toString());
  REQUIRE(q.dequeue() == 'G');
  REQUIRE(q.dequeue() == 'H');
  REQUIRE(q.dequeue() == 'I');
  REQUIRE(q.dequeue() == 'J');
}

Hint 1.

You will need to loop from start to end and may need to wrap around while looping.

🔗

Hint 2.

You will likely need/want a different counter for the location in the new array. The logic is easiest if you place the elements in the new array starting from 0. They will never need to wrap in the new array.

🔗

Welcome to Programming and Data Structures

Exercises 29.7 Exercises

1.

2.

3.

4.