A Queue Class

Programming Workshop 2 (CSCI 1061U)

Faisal Qureshi

Faculty of Science, UOIT

http://vclab.science.uoit.ca


Introduction

The goal of this lab is to use a class as a container within another class. We will use two classes: 1) a queue class and 2) a string class. The string class will be used as a container within the queue class.

Part 1

Use the string class that you implemented in part 1 and use it to implement a character queue. The Queue should support the following functions.

The code should work as follows:

class que {
protected:
    str _storage; // This is your string class that
                  // can dynamically grow when
                  // needed.
    
public:
    que();  // Default constructor.  Creates an empty queue.
    ~que(); // Destructor.
    
    char pop();
    void push(char c); 
}

We can use this code as follows:

que q;
q.push('h');
q.push('d');
cout << q.pop() << endl;
cout << q.pop() << endl;

The output of this program is

h
d

Caveat

A push may force the storage to grow. But a pop should be rather efficient.

Part 2

You will notice that as you add (push) and remove (pop) characters into this queue, the underlying storage may continue to grow. Find a way to fix that. Provide the following two functions in the queue class.

See usage below

#include <iostream>
#include <cstdlib>
#include <cassert>

using namespace std;

class que {
  ...
};

char random_char()
{
  char ch = char((rand() % 26) + 65);
  return ch;
}

int main()
{
  que q;

  for (int i=0; i<10; ++i) q.push(random_char());
  cout << "size = " << q.size() << endl;
  
  for (int i=0; i<4; ++i) cout << q.pop() << endl;
  cout << "size = " << q.size() << endl;

  q.compress();
  cout << "size = " << q.size() << endl;
  
  return 0;
}

Submission

Please submit que.h and que.cpp files via Blackboard.