queue and stack

Question 1

what is FIFO data structure

Answer 1

the first element added to the queue will be processed first

Question 2

explain enqueue

Answer 2

new element is always added at the end of the queue

Question 3

explain dequeue

Answer 3

only allowed to remove first element

Question 4

drawback to naive implementation of queue using array and one pointer

Answer 4

with the movement of start pointer more and more space is wasted

Question 5

explain circular queue

Answer 5

use a fixed sized array and two pointers to indicate starting and ending position.

Question 6

when is queue a good choice

Answer 6

When you want to process the elements in order

Question 7

python lib for queue

Answer 7

from queue import Queue

Question 8

python lib for queue and stack both

Answer 8

from collections import deque

Question 9

application of breadth first search

Answer 9

to find the shortest path from root node to target node

OR

do traversal

Question 10

processing order of nodes in bfs

Answer 10

in the first round, we process the root node. in the second round, we process the nodes next to the root node. In the third round, we process the nodes which are two steps from the root node and so on.

Similar to tree’s level order traversal, the nodes closer to the root node will be traversed earlier.

If a node X is added to the queue in the kth round, the length of the shortest path between the root node and X is exactly k.

Question 11

what is enqueue and dequeue order of the queue

Answer 11

we first enqueue the root node. then in each round, we process the nodes which are already in the queue one by one and add all their neighbours to the queue.

the processing order is same order as they were added to the queue, FIFO

Question 12

Template I for bfs

returns the length of the shortest path between root and target node

Answer 12

from collections import deque

def bfs(root, target):
queue = deque()
step = 0
queue.append(root)
while queue:
size = len(queue)
for _ in range(size):
cur = queue[0]
if cur == target:
return step
for next_node in cur.neighbours:
queue.append(next_node)
queue.popleft()
step += 1
return -1

Question 13

template II for bfs

when you don’t want to visit a node twice (think graphs with cycle)

Answer 13

from collections import deque

def bfs(root, target):
queue = deque()
visited = set()
step = 0

queue.append(root)
visited.add(root)

while queue:
    size = len(queue)
    for _ in range(size):
        cur = queue[0]
        if cur == target:
            return step
        for next_node in cur.neighbours:
            if next_node not in visited:
                queue.append(next_node)
                visited.add(next_node)
        queue.popleft()
    step += 1
return -1