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;
}
}
