4.2.1 Data Structures Flashcards
How many pointers do linear queues have?
Two: Front and Rear Pointer
How would this linear queue of size 5 look like after the .dequeue() function is applied. Rear pointer is at position 2 and the front pointer is at 0.
- Jack 1.Emily 2.____3._____4._____
The rear pointer would remain where it is the front pointer would be moved to position 1 and “Jack” is removed from the queue.
- _____ 1.Emily 2.____ 3._____ 4._____
FIFO? Example?
- First in First Out
- Queues
What data structures do linear queues use primarily?
Arrays
What is an ADT give 2 examples?
- Abstract Data Types
- Stacks
3.Queues
FILO? Example?
- First in, Last out
- Stacks
Define “Abstract Data Types”
ADTs are data structures that don’t exist as a data structure but make use of other data structures such as an array or linked list to form a new way of storing data.
Define “Array”
A finite indexed set of related elements which have the same data type.
How does a Circular queue deal with the enqueue() function when the front pointer is in position 0 with the size of the array being 5.
When the front pointer is at 0 and the enqueue function is used the front pointer will loop round to the end of the queue at position 4 making that the new start of the queue and adding the person in there.
If two items in a priority queue have the same priority what order are they removed in?
First in First out (FIFO)
Describe a tree data structure.
All nodes stem from one root node.
a = [4, 5]
b = [5, 3]
What is a.b?
a.b is (4x5)+(5x3)
→ (20)+(15)
→ 35
What is the name of the procedure that adds an item to a stack? Describe the process?
Push
Push adds the new value onto the top of a stack think of this like adding another pancake onto a “stack” of pancakes
What is the name of the procedure that removes an item to a stack? Describe the process?
Pop
Empties and if top pointer = -1 then it returns stack empty
How many pointers do stacks have?
One : Top pointer
