What is a data structure?
A conceptual way of arranging data
Explain the differences between static and dynamic data structures. (MS)
static data structures have storage size determined at compile-time / before program is run / when program code is translated; dynamic data structures can grow/shrink during execution / at run-time;
//
Static data structures can waste storage space/memory if the number of data items stored is small relative to the size of the structure; whereas dynamic data structures only take up the amount of storage space required for the actual data;
//
Static data structures have fixed (maximum) size; whereas size of dynamic data structures can change;
//
Dynamic data structures (typically) require memory to store pointer(s) to the next item(s); which static data structures (typically) do not need; NE. Dynamic data structures use pointers
//
Static data structures (typically) store data in consecutive memory locations; which dynamic data structures (typically) do not;
What is overflow in static data structures?
Attempting to store more data than is available with set memory locations.
What data structures are static and which are dynamic?
Static:
- Arrays
- Some stacks
- Some queues
- Graphs which use adjacency matrix
Dynamic:
- Some stacks
- Some queues
- Graphs which use an adjacency list
- Lists
What is an array?
A finite, indexed set of related elements of the same data type.
What is a stack?
An abstract data structure which operates on a FILO (first-in-last-out) basis
What components are there in a stack?
Stack array / list - stores the items in the stack
Stack pointer - indicates the top of the stack
What are the key operations we can perform on a stack?
1) Push (add item to top of stack)
2) Pop (remove item from top of stack)
3) Peek (return the value at the top of the stack)
4) Checking if a stack is empty
5) Checking if a stack is full
How can you check if a stack is empty?
You can check if the index of the stack pointer is at -1 (initial value).
private bool IsEmpty() {
return stackPointer == -1;
}How to check if a stack is full?
Check if the index of the stack pointer is at the max size of the stack - 1;
private bool IsFull() {
return stackPointer == stack.Length - 1;
}How to push an item onto the top of the stack?
1) Check if the array storing the stack is full. If it is, raise an error / exception.
2) If not full, increment the stack pointer by 1.
3) Store the item at the new memory that the stack pointer points to.
public int[] Push(int x) {
if (!IsFull()) {
stackPointer++;
stack[stackPointer] = x;
return stack;
} else {
System.Console.WriteLine("The Stack is full.");
return stack;
}
}How to pop an item off the top of a stack?
1) Check if the array storing stack is empty. If empty, raise an error or throw an exception
2) If not, decrement the stack pointer by 1.
3) Return the value of the item at index stack pointer + 1.
public void Pop() {
if (!IsEmpty()) {
stackPointer--;
System.Console.WriteLine(stack[stackPointer + 1] + " has been popped from the stack.");
} else {
System.Console.WriteLine("The list is empty! Cannot pop!");
}
}How to peek an item in a stack?
1) Check if array storing stack is empty. If it is, raise an error
2) Return value of item at index of stack pointer.
public int? Peek() {
if (!IsEmpty()) {
System.Console.WriteLine("Your number is " + stack[stackPointer]);
return stack[stackPointer];
} else {
System.Console.WriteLine("Stack is empty! Nothing to peek!");
return null;
}
}What is a multi-dimensional array?
an n-dimensional array is a set of elements of the same data type with each element being of type array with n-1 dimension
What is an abstract data stucture?
An unimplemented data structure which makes use of other data structures to form a new way of storing data. (e.g. stacks using arrays)
Key differences between static and dynamic data structures
What is a queue?
An abstract data structure that operates on a FIFO (first-in-first-out) basis.
What are the types of queues?
1) Linear Queues
2) Circular Queues
3) Priority Queues
What are the elements of a linear queue?
- Array or list for the items
- Front and rear pointer (for start and end of the queue)
What are the key operations of a linear queue?
1) Check if the array for the queue is empty
2) Check if the array for the queue is full
3) Enqueue (add) an item to the end of the queue
4) Dequeue (remove) an item from the start of the queue
How do you check if a LINEAR queue’s array is empty?
Check if the value of rear pointer is less than the value of the front pointer
public bool IsEmpty() {
if (rearPointer < frontPointer) {
return true;
else {
return false;
}
} How to check if a queue is full?
Check if the index of the rear pointer is at the max size - 1.
public bool IsFull() {
if (rearPointer == maxSize - 1) {
return true;
else {
return false;
}
} What are the advantages and disadvantages of linear queues?
Advantages:
- Simple to program
Disadvantages:
- Can lead to wasted capacity due as memory is stored statically (static)
- Process of shuffling is inefficient
What is a circular queue?
A type of queue that allows the front and rear pointer over the ends of the queue. This makes it a more efficient structure.
-
Data Representation39
-
Image Representation10
-
Sound Representation11
-
Compression and Encryption19
-
Data Structures and Algorithms86
-
Databases and SQL47
-
Programming29
-
Communication77
-
Object-Oriented Programming33
-
Theory of Computation86
-
Computer Systems45
-
Computer Organisation and Architecture96
-
Networking102
-
Functional Programming25
-
Big Data16
-
Ethics0
