Stacks and Queues

Question 1

What’s the order of inserts/deletes for stacks?

Answer 1

Last in, first out

Question 2

What’s the order of inserts/deletes for queues?

Answer 2

First in, first out

Question 3

Time complexity of push in to stack?

Answer 3

O(1)

Question 4

Time complexity of pop from stack?

Answer 4

O(1)

Question 5

How do you return the top of the stack without popping it?

Answer 5

Peek

stack[-1]

Question 6

What is a common application for using a stack?

Answer 6

For parsing

Question 7

What built-in can you use to implement a stack?

Answer 7

List

Question 8

How do you push an element in to a stack built using a list?

Answer 8

stack.append(e)

Question 9

How do you retrieve/peek at the top element of a stack?

Answer 9

stack[-1]

Question 10

How do you remove and return the top element of a stack?

Answer 10

stack.pop()

Question 11

How do you test if a stack is empty?

Answer 11

len(stack) == 0

Question 12

What operations does a queue support?

Answer 12

enqueue and dequeue

Question 13

What data structure can be used to implement a queue?

Answer 13

Linked list

Question 14

Time complexity for enqueue?

Answer 14

O(1) if we have a pointer to the tail

Question 15

Time complexity for dequeue?

Answer 15

O(1) if we have a pointer to the head

Question 16

How is a deque (double-ended queue) implemented?

Answer 16

Doubly linked list

Question 17

Where can you insert or delete from a deque?

Answer 17

At the head or the tail of the linkedlist

Question 18

What Python built-in can you use to create a queue?

Answer 18

collections.deque

from collections impor deque

q = deque()

Question 19

How do you append to a queue?

Answer 19

q.append(e)

Question 20

How do you retrieve, but not remove, the element at the front of the queue?

Answer 20

q[0]

Question 21

How do you remove and return the element at the front of the queue?

Answer 21

q.popleft()

Question 22

What should you always check before q.popleft() (dequeueing)?

Answer 22

that q is not empty

if q

Question 23

When should you consider a queue?

Answer 23

When order matters (ex: “buildings with an ocean view”)

Question 24

How do you implement stack with a linkedlist?

Answer 24

Have a pointer to the head/top

Add and remove items from the same side (where the pointer points to)

Question 25

How do you add items to a stack implemented as a linkedlist?

Answer 25

new_node.next = top # “shifting” the old top further down stack

top = new_node # setting the new node as the top of stack

Question 26

How do you pop from a stack implemented as a linked list

Answer 26

item = top.data

top = top.next # nothing is pointing to the ‘old’ top and will be garbage collected

return item

Question 27

What data structure can be used to implement a recursive algorithm iteratively?

Answer 27

Stack

Question 28

What’s the difference between pointers used in linkedlists for stacks and queues?

Answer 28

Stack only needs pointer to the head/top

Queue needs pointer to the head and tail

Question 29

What type of data structure to use for BFS?

Answer 29

Queue

Question 30

What type of data structure to use for DFS?

Answer 30

Stack