Introduction to Abstract Data Types (ADT)

Computer Science AS · Data types and structures. The idea in plain words, the rules to remember, the mistake to avoid and a worked example, written and checked by Mega Lecture.

Test this topic free All Computer Science AS topics

The idea

An abstract data type is a collection of data and a set of operations on that data. It says what can be done with the data, not how the data is stored.

A stack is last in, first out: items are added and removed at the same end, the top. A queue is first in, first out: items join at the rear and leave from the front. A linked list is a chain of nodes. Each node holds data and a pointer to the next node, so an item is inserted or deleted by changing pointers and no data is moved.

All three can be built from arrays together with integer variables used as pointers.

Rules to remember

Stack: LIFO. Push adds to the top, pop removes from the top. Uses: return addresses, undo, reversing data
Queue: FIFO. Add at the rear, remove from the front. Uses: print jobs, keyboard buffer
Linked list: a start pointer gives the first node; the last node holds the null pointer
Stack in an array: TopPointer. Push: check not full, add 1 to TopPointer, store the item. Pop: check not empty, take the item, subtract 1
Queue in an array: FrontPointer and RearPointer. In a circular queue a pointer at the upper bound moves next to the lower bound
Linked list in arrays: Data[i] holds the item and Pointer[i] holds the index of the next node; unused nodes are kept in a free list
Insert X between P and Q: X points to Q, then P points to X. Delete Q: the node before Q points to the node after Q

Common mistake

Removing from the wrong end. A queue gives up its oldest item and a stack gives up its newest item. Write down the contents after every operation.

Worked example

The values 4, 9 and 2 are added, in that order, to an empty stack and also to an empty queue. Two items are then removed from each. Which item is left in each structure?

Stack: 2 was pushed last, so it is popped first, then 9. The item 4 is left.
Queue: 4 joined first, so it leaves first, then 9. The item 2 is left.

Answer: The stack holds 4 and the queue holds 2.

Ask about this

Type what you are stuck on. The helper finds the explanation, worked examples and the notes to read, free and instant.

Keep going

← Files Programming basics →Take a Computer Science AS test