1.7.2 Application of queue

• BFS maze
  here=root of T; 
  here is end? 
  enqueue(Q,v); 
   
  while(!empty(Q)){ 
      dequeue(Q, here); 
      if(here is end) 
      for (each next position of here){ 
          if(next position is not end){ 
               mark next position 
               enqueue(Q, next position); 
          } 
      } 
  }
• For BFS, path is not save in stack. So you need a new kind of data type.
  struct position { 
          int x; 
          int y; 
          struct position* parent; 
  }
• Just like DFS, before you add a position to queue, mark it first.