Data Structures 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
What are the uses for queues and stacks?
