Railroad FAQ

Q: Why shouldn't my Stack, Queue, and Vector inherit from my Deque?

Remember that in inheritance, your children classes will gain all the functionality that the parent class has. Your Deque class has several functions that simply aren't applicable to the data structures we are making. For example, a stack is only able to insert at the top, so having a pushBack() function doesn't make sense. So, instead of inheriting from Deque, it makes more sense to include a Deque in your data structure classes. Then, you can set it up so each data structure only uses the Deque functions that are applicable.

Q: What are the differences between the various data structures in the lab?

All of the lab data structures are sequential data structures with different limitations on where you can add or remove elements.

A stack is a Last-In, First-Out (LIFO) data structure. This means that the only thing you can access from the stack is the most-recently inserted element, also known as the top element.

A queue is a First-In, First-Out (FIFO) data structure. This means that the only thing you can access from the queue is the first element that you inserted. This is similar to our help queue system, where the first one in the queue is the first one helped (in theory).

A deque is also known as a double-ended queue. It works like a queue, except that you can insert and remove on both ends. There are two variants of the deque, the input-restricted deque and the output-restricted deque. An IR deque only allows insertions at the top of the deque, but it allows removal from either end. An OR deque allows insertion at both ends, but only allows removal from the top.

How do I deal with Valgrind errors?

The most likely place you are having errors with Valgrind for this lab is in your circular array. Most likely, you are either:

  1. Not moving your front and rear indexes properly and are therefore accessing out of bounds memory.
  2. Not deleting the old array when you are realocating and therefore have memory leaks.
Make sure that you are checking in all of those places and double check that your code never does either of those. As always, the page for understanding valgrind can be a big use to you, and you can find that here

How do I move functions longer than 10 lines for templated classes?

You can find this answer in the first FAQ for lab 3, here