(2) Fundamentals of Data Structures Flashcards
What is data structures?
Containers that store and organise data in a specific way
What does the following operations do in a stack data structure PUSH, POP, IsEmpty?, IsFull?, Peek
Push - Adds a value in the stack
Pop - Removed a value in the stack
Peek - Checks what’s at the top of the stack
IsEmpty? - Checks if the whole stack is empty
IsFull? - Checks if the whole stack is full
What is a static data structure with an example?
Static data structures have storage size determined before program is run. Has fixed maximum size
Eg an array
What is dynamic data structure with an example?
Dynamic data structures can grow/shrink during execution
Eg a list
What is the advantages and disadvantages of static data structures?
+Easy to program
+An array allows random access
+Easy to check for overflows
- The programmer has to estimate the maximum amount of space that is going to be added
- Can waste a lot of space
What is the advantages and disadvantages of dynamic data structures?
+Only uses the space needed at any time
+Makes efficient use of memory
- Difficult to program
- Can be slow to add searches
What is abstract data type?
Data types which are not defined by their implementation
Describe a stack data structure and where is it used?
- Uses Last In First Out (LIFO) to determine when data is executed
- Uses one pointer at the top of the stack
Used anywhere you need to back track
Describe a queue data structure and where is it used?
- Uses a First In First Out rule (FIFO) to determine when data is executed
- Uses two pointers, one for the front and back of the queue
Eg print jobs waiting to be printed
What is a graph data structure?
A set of vertices connected by edges. The edges may be one or two way
What is a linear queue?
What is a circular queue?
What is a priority queue and where can it be used?
Works the same way as a regular queue however they are ranked by their priority. The highest priority items are at the front of the queue and lowest priority at the back of the queue.
Eg a hospital
What is a front and rear pointer?
Indicates what’s the first and last element of the queue
What is the typical uses of a graph data structure?
Internet (Vertices: Web pages, Edges: Hyperlinks)
Social networks (Vertices: People, Edges: Friendships)
Transportation (Vertices: Airports, Edges: Air routes)