4003CEM-datastructures

As you write more and more advanced software you are going to encounter different data structures and types. Data structures and types are how we store and organised multiple pieces of information in our software.

This week you will be writing your own implementations of some of the more common data types. Unless otherwise stated you will be writing array based implementations, there is an option to explore linked list implementations as part of the advanced tasks.

stack

Although C++ has a stack type already included in and the Python list can behave like one it's going to be useful for you to understand how to create your own data structures.

1. Look at the code in stack.h and stack.cpp.
2. Notice that we have put the class prototype in the stack.h file but the function bodies are in the stack.cpp file.
   • This is a better way to organise our code than having everything in a single .h file as it allows for faster compile times.
   • If you are unsure why this is, go back over the material from the compilation slides and tasks.
3. Compile and test the stack code
   • Notice that there are a large number of problems in our stack code.
   • You don't need to fix them all right now, we'll come back to that in a bit

Fix num_items()

1. Fix the num_items() function code in stack.cpp

Fix pop()

1. Fix the pop() function

Fix top()

1. Fix the top() function

Fix everything

1. Make sure that stack is completely error free.

Linked list stack

1. Try and implement a stack using a linked list. You may find it helpful to use your array implementation as a starting point.
   • If you are using C++ then you will need to use pointers and dynamic memory allocation.
   • Don't worry if you can't do this yet, it will be covered in much greater depth next year.

queue

Complete the code in the queue.h and queue.cpp file so that it passes the tests.

• You many find it helpful to refer back to your stack code.

• Both C++ and Python have built in queue types, you can't use them for this task, that would be cheating.

  • The default Python queue is actually a dequeue (double ended queue) which allows you to push and pop from both ends of the queue but it can still be used as a normal queue.
  • C++ also has a double ended queue type called a deque.

Priority queues

1. Research the behaviour of priority queues.
2. Using your existing queue code as a starting point, implement a priority queue.
   • When elements are added to the queue they will need to supply a priority.
   • You will need to consider how this priority affects where in the queue new elements get placed.

A First In First Out (FIFO) structure. Often used as a buffer to hold items for processing in the order in which they arrive. New elements can be added to the back of queue only. Old elements can be removed from the front of the queue only. There is no access to the middle of the queue.

set

1. Implement your own set type using an array in the set.h and set.cpp files..
   • You may find it helpful to refer back to your stack and queue code.
   • Test that your set works correctly.