Answers.Body: <p>We use the LIFO  queue, i.e. stack, for implementation of the depth-first search algorithm because depth-first search always expands the deepest node in the current frontier of the search tree.</p>
  <p>Norvig and Russell write in <a href="https://cs.calvin.edu/courses/cs/344/kvlinden/resources/AIMA-3rd-edition.pdf#page=104" rel="nofollow noreferrer">section 3.4.3</a></p>
  <blockquote>
  <p>The search proceeds immediately to the deepest level of the search tree, where the nodes have no successors. As those nodes are expanded, they are dropped from the frontier, so then the search &quot;backs up&quot; to the next deepest node that still has unexplored successors.</p>
  <p>A LIFO queue means that the most recently generated node is chosen for expansion. This must be the deepest unexpanded node because it is one deeper than its parent — which, in turn, was the deepest unexpanded node when it was selected.</p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-27T14:13:45.747Z
Answers.LastActivityDate: 2021-12-12T21:10:06.130Z
Answers.LastEditDate: 2021-12-12T21:10:06.130Z
Answers.UserDisplayName: Huma Qaseem
Body: <p>Why do we use a last-in-first-out (LIFO) queue in the depth-first search algorithm? </p>
  
  <p>In the breadth-first search algorithm, we use a first-in-first-out (FIFO) queue, so I am confused.</p>
  
Tags: <search><implementation><breadth-first-search><depth-first-search>
Title: Why do we use a last-in-first-out queue in depth-first search?
UserDisplayName: Samia Afzal
ThreadText: # Why do we use a last-in-first-out queue in depth-first search?
  
  (Asked by: username_0 on 2018-11-26)
  
  Why do we use a last-in-first-out (LIFO) queue in the depth-first search algorithm?
  
  In the breadth-first search algorithm, we use a first-in-first-out (FIFO) queue, so I am confused.
  
  **Tags:** search, implementation, breadth-first-search, depth-first-search
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-11-27. Score: 1 | Accepted answer
  
  We use the LIFO queue, i.e. stack, for implementation of the depth-first search algorithm because depth-first search always expands the deepest node in the current frontier of the search tree.
  
  Norvig and Russell write in [section 3.4.3](https://cs.calvin.edu/courses/cs/344/kvlinden/resources/AIMA-3rd-edition.pdf#page=104)
  
  > The search proceeds immediately to the deepest level of the search tree, where the nodes have no successors. As those nodes are expanded, they are dropped from the frontier, so then the search "backs up" to the next deepest node that still has unexplored successors.
  >
  > A LIFO queue means that the most recently generated node is chosen for expansion. This must be the deepest unexpanded node because it is one deeper than its parent — which, in turn, was the deepest unexpanded node when it was selected.
  
  
  ---
  
  