Lab: Abstract Data Type (Queue)

A more focused container abstraction

An ADT is a class that implements certain data storage functionality. It's abstract because you don't care how it's implemented under the hood - only that it supports certain operations. Real ADT classes also provide performance guarantees for the different things they can do.

Back in lab 1, you created a List ADT that was a better array. You could add things to it, remove them, find them, etc. Internally, it used an array to hold the things, and could dynamically resize it, but from the outside, you don’t need to know or care about that. This distinction between the external interface (the things it can do) and the internal implementation (how it does it) is critical for good software engineering and computer science.

Two of the simplest common ADTs in computer science are the stack and queue. Each provides a specific, limited set of functions for storing things. In this lab, you're going to create a queue that uses a linked list as the internal data storage.

Here is the empty repo for you to commit your work.

https://cssvn.utrgv.edu/svn_etomai/201720_2380/lab04_queue/<your username>

Commit your work at the end of lab for lab credit!

Get in line

A queue is a line, just like at the grocery store. The key characteristic is that you add items (people) at the back, and access them at the front. This is more constrained than our prior list, where you could access, insert and remove any item anywhere. Just like lines, queues are very useful for certain data situtions where you want things to be processed in order.

A queue can hold anything, and later in the course we'll see how to make it more flexible with C++ templates. But for now, your queue is going to hold coordinates (this will be useful in the homework). A coordinate is an integer x,y pair referring to a position on a grid. We'll all use this simple public-data class for our coordinates:

class coord
{
public:
  int x, y;
  coord() { x = 0; y = 0; }
  coord(int _x, int _y) { x = _x; y = _y; }
};

Your queue class must support the following operations (public methods):

• empty: return true if the queue has 0 items in it
• size: return the number of items in the queue
• push: add a new item to the back of the queue
• pop: remove and return the item at the front of the queue

Internally, you must use a private linked list to implement this functionality. That means you'll also need a node class that holds data of type coord.

Doin' work

Start by stubbing out your classes. coord, node and your queue class, the last one with the public methods specified above. Then use this test code to ensure that your queue works. Remember!

1. First, look over the whole thing to make sure you understand what you're trying to accomplish.
2. Then, work on the tests a few at a time.

#include <cassert>
...

int main()
{
  ListQueue q;

  // empty case
  assert(q.size() == 0);
  assert(q.empty() == true);

  // add some items
  coord c(1, 2);
  q.push(c);
  
  // note: reusing c works here because we're storing copies of c in the queue
  c.x = 3;
  c.y = 4;
  q.push(c);

  // note: here is a simpler way, omitting the name of the temporary coord
  // note: this is called an "anonymous" object, which is used and discarded
  q.push(coord(5,6));

  // test!
  assert(q.size() == 3);
  assert(q.empty() == false);

  coord check = q.pop();
  assert(q.size() == 2);
  assert(check.x == 1);
  assert(check.y == 2);

  check = q.pop();
  assert(q.size() == 1);
  assert(check.x == 3);
  assert(check.y == 4);

  check = q.pop();
  assert(check.x == 5);
  assert(check.y == 6);

  assert(q.size() == 0);
  assert(q.empty() == true);

  return 0;
}