Data Structures Flashcards
What is a stack ADT
- A stack (or LIFO) is an ADT that serves as a collection of elements, with two principal operations: push, and pop.
List Stack Operations
void clear() – clear the stack
bool isEmpty() const – check to see if the stack is empty
void push(el) – put the element el on the top of the stack
T pop() – take the topmost element from the stack
T& top() – return the topmost element in the stack without removing it
Stack implementations
as vector:
- poping and pushing are executed in constant time O(1)
- pushing worst case O(n) (requires resizing and copying)
as linked list (doubly):
- poping and pushing are executed in constant time O(1)
- matches ADT more closely as number of nodes in list is the same as number of stack elements
Queue ADT
a waiting line that grows by adding elements to its end and shrinks by taking elements from its front
List Queue Operations
void clear() – clear the queue
bool isEmpty() – check to see if the queue is empty
void enqueue(el) – put the element el at the end of the queue
T dequeue() – take the first element from the queue
T& first() – return the first element in the queue without removing it
Queue Implementations
as array:
- enqueuing and dequeuing can be executed in constant time O(1)
- may not be the best choice, as cells can be left empty and need to be managed
as linked list (doubly):
- enqueuing and dequeuing can be executed in constant time O(1)
- generally the best choice
as linked list:
- enqueuing and dequeuing can be executed in constant time O(n)
Priority Queue ADT
A data structure that stores items and restricts accesses to the highest priority item
List Priority Queue Operations
void create() – Make an empty priority queue
bool isEmpty() – check to see if the queue is empty
void insert() – inserts an item
T top() – RETURNS the item with the highest priority
void pop() – REMOVES the item with the highest priority
Implementation of Priority Queue
as linked list:
- insert could be O(1) by putting the new item on the front of the list.
- top and pop however would require O(N) to scan through all of the items
as sorted linked list:
- top and pop could be O(1) by just dealing with the first item
- insert however would require O(N) to scan through all of the items
Heap ADT
a special type of binary tree usufle for implementing priority queues; has these two properties:
1) The value of each node is greater than (for max heap, less than for min heap) or equal to the values stored in each of its children
2) The tree is perfectly balanced, and the leaves in the last level are all in the leftmost position (complete tree)
* root will contain largest (or smallest) element in heap
Heap Operations
heapEnqueue(el)
- add element at the end of heap as the last leaf;
- restore heap property by moving from the last leaft toward the root
heapDequeue()
- remove the root element (greastest priority);
- replace with last leaf;
- restore heap property by moving new root down the tree
access heap elements:
left child
right child
parent
LC: heap[2 * i + 1]
RC: heap[2 * i + 2]
P: heap[( i - 1 ) / 2]
heap enqueueing algorithm
heapEnqueue(el)
put el at the end of the heap;
while el is not in the rool and el > parent (el)
swap el with its parent;
heapDequeue() algorithm
heapDequeue()
extract the element from the root;
put the element from the last leaf in its place;
remove the last leaf;
p = the root;
while p is not a leaf and p < any of its children
swap p with the larger child;
bubbleDown()
void bubbleDown( int index ) {
// while index is not at the last level
// set child to node with the largest value
// if index is smaller than child
// swap index with child
// else
// done
// update index and child
int child = (index * 2) + 1;
while ( child < size ) {
if ( (child + 1 < size) && (array[child + 1] > array [child])) {
child++;
}
if ( array[index]){
swap( array[index], array[child] );
}
index = child;
child = ( index * 2 ) + 1;
}
}
bubbleUp()
void bubbleUp( int el) {
// while el is not in the root and el > parent(el)
// swap el with its parent;
}
Heap Efficiency: Average and Worst case
Average-case__Worst-case
insertion: O(1) O(log N)
top: O(1) O(1)
pop: O(log N) O(log N)
buildHeap: O(N) O(N)
STL Stack member functions
*defaults is deque container, can use list or vector
bool empty() const – return true if the stack has no elements, false otherwise
void pop() – remove the top element of the stack
void push(const T& el) – insert el at the top of the stack
size_type size() const – return the number of elements on the stack
stack() – create an empty stack
T& top() – return the top element on the stack
const T& top() const – return the top element on the stack
STL Queue Member Functions
*defaults is deque container, can use list, cannot use vector
T& back() – return last element in the queue
const T& back() const – return last element in the queue
bool empty() const – return true if the queue has no elements, false otherwise
T& front() – return first element in the queue
const T& front() const – return first element in the queue
void pop() – remove the first element in the queue
void push(const T& el) – insert el at the end of the queue
queue() – creare an empty queue
size_type size() const – return the number of elements in the queue
STL priority_queue container
*defaults is vector, can deque
bool empty() const – return true if the queue has no elements, false otherwise
void pop() – remove an element in the queue with the highest priority
void push(const T& el) – insert el in the proper location on the priority queue
priority_queue(comp f())
– creare an empty priority queue that uses a two-argument boolean function f to order elements on the queue
priority_queue(iterator first, iterator last, comp f())
– creare an empty priority queue that uses a two-argument boolean function f to order elements on the queue; initialize the queue with elements from the range indicated by iterators first and last
size_type size() const – return the number of elements in the priority queue
T& top() – return the element with highest priority
const T& top() const – return the element with highest priority
Pro/Cons:
Arrays
Pros
- Direct indexing: O(1)
- Sequential access: O(N)
Cons
- Sorting: O(N log N)
- Searching: O(N), and O(log N) if sorted
- Inserting and deleting: O(N) because of shifting items.
Pro/Cons:
Stack
Stack Pros
- Provides control over how memory is allocated and deallocated
- No need to remember cleanup of objects
- Not easily corruptible
Stack Cons
- Stack memory is limited.
- Large stack increases likelihood of stack overflow
- No random access
Pros/Cons:
Linked List
Pros
- Inserting and deleting: O(1)
- Sequential Access: O(N)
Cons
- No Direct Access; Only Sequential Access
- Searching: O(N)
- Sorting: O(NLogN)
Pros/Cons:
Stacks and Queues
Pros
- Push/Add: O(1)
- Pop/Remove: O(1)
- Peek: O(1)
Cons
- Limited memory
- Not designed for random access
Pros/Cons
Heaps
Pros
- Find Min/Find Max: O(1)
- Inserting: O(LogN)
- Delete Min/Delete Max: O(LogN)
Cons
- Searching and deleting: O(N)
