Data Structures Flashcards
What is a data structure?
A group/collection of related data elements
What is an array?
- Data structure where there is a predetermined number of elements of the same type.
- Elements are accessed via indexes
What is a record?
Set of data items which are all related to a single entity and can contain data of different types
What is a stack?
‘First In, Last out’ data structure where data elements can only be added and removed at the top
What examples can stacks be used for?
- Store subprogram addresses
- Store recursion values
- Store short-term arithmetical results
- Undo Function
What does a ‘Push’ and a ‘Pop’ include in a stack data structure?
- Push adds items to the top of a stack and pop removes the item from the top.
- Underflow may occur if you attempt to pop an empty stack and overflow occurs if you attempt to push to a full stack.
Why are stacks and queues commonly used for most situations?
The natural processing order is first in last out or first in first out depending on the situation.
How would a stack be implemented?
Would be stored in an array and a pointer would keep track of the top of the stack.
Pseudocode for pushing onto a stack:
If stackPointer < stackMaximum then:
stackPointer = stackPointer + 1
stackArray(stackPointer) = dataItem
Else:
Output “Stack is full - your data has not been saved”
Pseudocode for popping from a stack:
If stackPointer > 0 then:
dateItem = stackArray(stackpointer)
stackPointer = stackPointer - 1
Else:
Output “Stack is empty - no data can be retrieved”
What is a Queue?
‘First In, First Out’ data structure which could be used for printer queues and keyboard buffers
How would you implement a queue?
Data would be stored in an array and two pointers would keep track of the front and the back of the queue.
What is a linked list?
A set of data elements where each element contains the data itself and a pointer to the next element.
What are the benefits of using a linked list?
Items can be added without rearranging the entire order and can use memory more efficiently if programmed dynamically.
What are the drawbacks of using linked lists?
More difficult to program and manipulate than an array, extra programming is needed to send the data in the opposite direction and it can only be accessed in a linear manner.
