Data structure that stores elements of the same type, like an egg box. Simplest array has one dimension e.g. array of 12 strings to store the months of the year. 'Egg box' has two dimensions, 2 x 3 or 1 x 5, etc.
Elements in array accessed by index. First cell is e.g. data[1], second item is data[2], etc. Two dimension array requires two indices e.g. egg_box[1,1], egg_box[1,1], egg_box[2,1], egg_box[2,2], egg_box[3,1], egg_box[3,2].
Record structure can hold data items of different type e.g. name, date of birth and salary.
LIFO: Last In First Out. Works like a stack of plates, the last one placed on the stack is the first one taken off (you don't take a plate from the bottom of the stack!)
A stack has a single pointer that points to the top of the stack (TOS). The TOS pointer is typically incremented when an item is added to the stack (push operation) and decremented when an item is removed (pop operation).
A stack can be implemented using an array or dynamically using pointers (more on this in the A2 units). The size of the array limits the number of items that the stack can store. The TOS pointer is implemented as an integer.
FIFO: First In First Out. Works like any queue, new items are added (pushed) at the rear and items are taken off (popped) at the front.
A queue has two pointers, one for the front (where items are popped) and one for the rear (where new items are pushed).
A queue can be implemented in an array with the front and rear pointers implemented as integers. As new items are added the rear queue pointer will be incremented so it points to a cell further along the array. As items are removed the front pointer will also be incremented so that it points to the new front item. As a result the front pointer will eventually follow the rear pointer to the end of the queue/array. To allow the earlier cells to be used again the pointers should wrap around to the first array cell, thus creating a circular queue.
A binary tree stores data in nodes that consist of a single data item and a left and right pointer. Binary trees are constructed by placing items that are less than the current data item in a new node to the left of the current node and items that are greater than the current data item in a new node to the right.
The first node in a tree is called the 'root'. It is good strategy when creating a binary tree to place an item in the root that is in the middle of the data - Malcolm, for example, not Anne or Yvonne. As new items are added roughly half of them will be on the left side of the root node and half on the right side.
A binary tree can be implemented using an array with two dimensions such as 3 x 5, which can be represented as a table:
| Index | Data | Left Pointer | Right Pointer |
| 1 | Malcolm | 2 | 4 |
| 2 | David | - | 3 |
| 3 | Edward | - | - |
| 4 | Mike | - | 5 |
| 5 | Walter | - | - |
One of the columns here is used for data, the other two are used for the left and right pointers. In this example data items arrive in order Malcolm, David, Edward, Mike, Walter. Each new item is inserted in the next free array cell.
Malcolm is in the root node. David is added to the left of Malcolm so the left pointer of data item 1 points to item 2. Edward is inserted left of Malcolm and right of David so David's right pointer is set to data item 3. Mike goes to the right of Malcolm so the right pointer of data item 1 (Malcolm) is set to 4. Walter goes to the right of Mike so the right pointer of item 4 is set to 5. The other pointers are still null as they have not yet been set.