Stacks and Queues Flashcards
stack basics
last in first out
aka push down stack
stack operations
push - append element to stack
pop - get recent element and delete from stack
top - get recent element but does not delete
is_empty - if True, stack has no elements
get_size - returns the count of elements in the stack
stack exception cases
underflow - pop or top attempted on an empty stack
overflow - when push is attempted but stack has taken up all allotted space
how to declare an empty stack
my_stack = []
queue basics
controls flow of tasks
first in first out
enqueue, dequeue
queue operations
enqueue - appends element to queue
dequeue - fetches the value from the least recent element and removes it
front - fetches the value of the least recent element enqueued and removes it
is_empty
get_size
queue rules
- appending and removing need to happen at opposite end of the list being used to act like a queue
- avoid queues.py
priority queues
- add in a new element and its priority
- every element has a priority
- can be a fixed size
- if there is another element added w/ the same priority, then the most recently added one will go first
application of stacks and queues
stacks evaluate prefix, postfix and infix expressions
queues - job queuing, buffering keyboard input
enqueue
appends element to queue
dequeue
returns the value of least recent element and removes it
front
fetches the value of the least recent element enqueued but doesn’t remove it
is_empty
if True, queue/stack has no elements
get_size
returns the count of elements on the queue/stack
push
appends element to stack
pop
returns value of most recent element in stack and deletes it
top
returns value of most recent element in stack but doesn’t delete it
