121 Week 6 - Abstract Data Structures + Queue

Question 1

Abstract data structure (ADT)

Answer 1

A type (or class) for objects whose behaviour is defined by a set of values and a set of operations. It will state operations to be performed but not how they will be performed.

Question 1

Queue example

Answer 1

An ADT which is an ordered collection of items.
It has a head and tail which are the first and last items in the queue.
Items are added to the tail and removed from the head - First in Last out.

Question 2

Operations of a queue

Answer 2

queue() - create a new empty queue
enqueue(item) - add item to the end of the queue
dequeue() - if the queue isn’t empty, remove the item at the head of the queue and return its value
isEmpty() - test if the queue is empty
size() - find the size of the queue

Question 3

Abstraction

Answer 3

Removing unnecessary information and hiding internal details

Question 4

Difference between data structure and abstract data structure

Answer 4

Data structure is the physical representation of the structure of the data being stored in memory.
Abstract data structure is both the data structure and the procedures/functions which manipulate that data structure.

Question 5

Encapsulation

Answer 5

A way of stopping the user from directly interacting with the ADT but instead providing an interface through which they can interact with the ADT instead.
Encapsulation is strong if details on how the data structure is stored is completely hidden from the user.

Question 6

Queue implementation through pointers

Answer 6

A queue can be implemented by having a head pointer which points to the first item in the queue.
Each item then points to the next item in the queue.
The last item will point to NULL, indicating the end of the queue.
An empty queue is indicated by head being NULL.

Question 7

Bounded queue implementation through arrays

Answer 7

Assume queue can have at most max_size elements.
Create an array of length max_size.
Enqueue an item into the next free space in the array as long as the array is not full.
Dequeue an item by setting the last stored item in the array to be free