Stacks and Queues Flashcards
What’s the order of inserts/deletes for stacks?
Last in, first out
What’s the order of inserts/deletes for queues?
First in, first out
Time complexity of push in to stack?
O(1)
Time complexity of pop from stack?
O(1)
How do you return the top of the stack without popping it?
Peek
stack[-1]
What is a common application for using a stack?
For parsing
What built-in can you use to implement a stack?
List
How do you push an element in to a stack built using a list?
stack.append(e)
How do you retrieve/peek at the top element of a stack?
stack[-1]
How do you remove and return the top element of a stack?
stack.pop()
How do you test if a stack is empty?
len(stack) == 0
What operations does a queue support?
enqueue and dequeue
What data structure can be used to implement a queue?
Linked list
Time complexity for enqueue?
O(1) if we have a pointer to the tail
Time complexity for dequeue?
O(1) if we have a pointer to the head
How is a deque (double-ended queue) implemented?
Doubly linked list
Where can you insert or delete from a deque?
At the head or the tail of the linkedlist
What Python built-in can you use to create a queue?
collections.deque
from collections impor deque
q = deque()
How do you append to a queue?
q.append(e)
How do you retrieve, but not remove, the element at the front of the queue?
q[0]
How do you remove and return the element at the front of the queue?
q.popleft()
What should you always check before q.popleft() (dequeueing)?
that q is not empty
if q
When should you consider a queue?
When order matters (ex: “buildings with an ocean view”)
How do you implement stack with a linkedlist?
Have a pointer to the head/top
Add and remove items from the same side (where the pointer points to)
