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.

🔗

2.

Write the dequeue function for the Array Based Queue.

🔗

#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
}
===!

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.

🔗

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));
}

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.