Data Structures and Algorithms Flashcards
What is a data structure?
A conceptual way of arranging data
What is the difference between a static and dynamic data structure?
Static:
- Stored contiguously in memory as a series of sequential memory locations
- Storage size is fixed in compilation
Dynamic:
- Changing storage size during run time
- Store pointers as well as data to point between to next memory location
- Data dynamically allocated from the heap
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 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 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.
What mathematical operation do we use in implementation of a circular queue for indexing?
Modulo function e.g. with enqueue
~~~
public void Enqueue(T toAdd) {
if (!isFull()) {
rearPointer = (rearPointer ++) % maxSize;
items[rearPointer] = toAdd;
queueSize++;
} else {
System.Console.WriteLine(“The queue is full!”);
}
}
~~~
What is a priority queue?
A queue that has each item assigned with a priority with items with the highest priority being dequeued before low priority happen.
Within a given priority, items are dequeued in a first-in-first-out basis.
What are the uses for queues and stacks?
What is a recursive subroutine?
A subroutine that is defined in terms of itself
What is the role of the stack when a recursively-defined subroutine is exected?
- store parameters
- store return addresses
- store local variables / return values
What is used to see the priority of an element in a queue and what does it represent in implementation?
An integer used for priority
It represents which array of the 2d array to add the element to
What is a graph?
An abstract data structure to represent complex relationships between items within datasets.
How to represent a vector with components in reals and n components represented as?
ℝ^n
