One powerful concept in computer program is that of abstract data types.

We can classify digital objects which have properties and we can perform operations on those properties.

A very basic example of this would be to define a Square abstract data type. Here is a non-language specific representation of this idea:

Now that we have a definition of a abstract data type, we can construct an object:

STACKS

We can design a STACK to be an abstract data type.

We could use a 1D array to store the data in the STACK - this would be one of the properties of the adt.

Another property would be a variable storing the top of the stack.

We could then perform 2 operations on a stack:

• push(x)
• pop()

A stack is a last in, first out structure.

Let's imagine that a stack, s, has been set up as follows:

 

Now we can perform operations on the stack.

What would the stack, s, look like after the following operations have been performed? Draw the stack and make sure you show the final position of the top of the stack.

Another stack, s1 is set up similarly, but notice the top of the stack pointer.

What would the stack, s1, look like after the following operations have been performed? Draw the stack and make sure you show the final position of the top of the stack.

 

QUEUES

We can design a QUEUE to be an abstract data type.

We could use a 1D array to store the data in the QUEUE - this would be one of the properties of the adt.

Another property would be a variable storing the start of the queue and the end of the queue.

We could then perform 2 operations on a stack:

• enqueue(x)
• dequeue()

A queue is a first in, first out structure.

Let's imagine that a queue, q, has been set up as follows:

 

Now we can perform operations on the queue.

What would the queue, q, look like after the following operations have been performed? Draw the queue and make sure you show the final position of the pointers.

Linked Lists

A linked list is a list of non-contiguous nodes. This means that the nodes do not exist next to each other in memory.

Each node in the list has a pointer to the next node in the list. This is a singly linked list (example above).

A doubly linked list means that each node has a link to the previous and and the next node in the list!

We can:

• search a list
• insert a new node into a list
• delete a node from a list

When we are inserting and deleting, we are really just updating the pointers of nodes in the list.

For example, if we want to delete a node from a list, we just update the pointer of the previous node in the list:

Another example is inserting a new node into an ordered list:

For the exam, you may be asked to draw a diagram to show the result of an operation. You may also be asked to describe how an operation would be performed.

A key point to consider is that when processing a Linked List, always start at the root node!

Sample Exam Style Question

A queue is a first in, first out structure.

A queue, q, has been set up as follows:

 

The following operations are performed on the queue.

Describe the enqueue and dequeue operations. [4]