Introduction to Abstract Data Types (ADT) (Cambridge (CIE) A Level Computer Science): Flashcards
Exam code: 9618
1/340Still learning
Know0
- FrontADT Overview
Define abstract data type (ADT).
Was this flashcard helpful?
Cards in this collection (34)
Define abstract data type (ADT).
An abstract data type is a collection of data and a set of operations on that data.
Name three common abstract data types.
Stacks, queues and linked lists.
Define stack.
A stack is an abstract data type that stores data using the Last In, First Out (LIFO) principle.
What everyday object is a stack like?
A pile of plates: the last item you put on is the first one you take off.
What do PUSH and POP do?
PUSH adds an item to the top of the stack. POP removes the item from the top.
Name the two pointers that a stack uses.
A base pointer, which points to the first item in the stack, and a top pointer, which points to the last item.
What happens to the pointer when data is pushed onto a stack?
The pointer increments by 1, signifying the new top of the stack.
What happens to the pointer when data is popped from a stack?
The pointer decrements by 1, to point at the new top of the stack.
Define stack overflow.
A stack overflow is an attempt to push an item onto a full stack.
Define stack underflow.
A stack underflow is an attempt to pop an item from an empty stack.
What does
peek()do on a stack?It returns the top value of the stack without removing it, after first checking that the stack is not empty.
True or False?
Data that is popped is always erased from the stack.
False.
The data is not necessarily erased. The top pointer moves, and depending on the implementation the value may be deleted, replaced with a null value, or left to be overwritten.
Define queue.
A queue is an abstract data type that stores data in the order it arrives, using the First In, First Out (FIFO) principle.
What do ENQUEUE and DEQUEUE do?
ENQUEUE adds an item to the back of the queue. DEQUEUE removes the item from the front.
What does
peek()do on a queue?It returns the value of the item at the front of the queue without removing it from the queue.
Define linear queue.
A linear queue is a data structure that consists of an array, where items are added to the next available space and removed from the front.
What must be checked before adding an item to a linear queue?
That the queue is not full.
Before removing an item from a queue you must make sure that the queue is not .
Before removing an item from a queue you must make sure that the queue is not empty.
What happens to the rear index pointer when an item is enqueued?
If the end of the array has not been reached, the rear index pointer is incremented and the new item is added to the queue.
What happens to the front pointer when an item is dequeued?
The item at the front of the queue is returned and the front is incremented by 1.
Define circular queue.
A circular queue is a static array with a fixed capacity that reuses the empty slots at the front of the array which are freed when items are dequeued.
Why is a circular queue used instead of a linear queue?
In a linear queue it would take time to move items up to the start of the array to free space at the end, so a circular queue reuses the empty slots instead.
When is a circular queue full?
When the next position to be used is already occupied by the item at the front of the queue.
What happens when the only item in a circular queue is dequeued?
The rear and front pointers are reset.
Define linked list.
A linked list is an abstract data type where each item, or node, contains a data field and a pointer to the next node in the sequence.
What two things does each node in a linked list store?
The actual data, and a pointer to the next item in the list.
In a linked list, the field contains the address of the next item in the list.
In a linked list, the pointer field contains the address of the next item in the list.
Where are new items usually added in a linked list?
To the start of the list.
What signals that the end of a linked list has been reached?
The pointer field is empty or null.
How is a linked list traversed?
Check the list is not empty, start at the node the Start pointer points to, output the item at that node, then follow the pointer to the next node, repeating until the pointer field is empty.
When a node is added to a linked list, what happens to the node it follows?
The pointer field of that node is updated to point to the new node.
How is a node removed from a linked list?
The pointer field of the previous node is updated to bypass the deleted node.
True or False?
A removed node is erased from the linked list.
False.
The node is not truly removed, it is only ignored. This is easier, but it wastes memory.
Give two disadvantages of a linked list compared with an array.
Storing pointers means more memory is required, and items can only be traversed in sequence, so an item cannot be directly accessed as it can in an array.
Sign up to unlock flashcards
or