Applications of Stack and Queue

In this module, we will see the applications of stack and queue
  • When to use stack ?
  • Evaluation of postfix expressions
  • Conversion of infix to postfix
  • Backtracking
  • Function calls
  • CPU scheduling
  • Queuing theory
  • The level traversing of tree
Src: google

When to use stack ?

The stack is the most suitable data structure if you only need to implement recursion in a programming language. When you make a recursive call, you need to save the function you are currently in and the values of its parameters in some data structure, so that when you go out of the recursion you can restore the state. When you go out of the recursive call, you will always need to extract the last element that was put in the stack.

Evaluation of postfix expressions

  1. We read the tokens in one at a time
  2. If it is an integer, push it on the stack
  3. If it is a binary operator, pop the two elements from the stack, apply the operator, and push the result back on the stack 




Conversion of Infix to Postfix

  1. Read in the tokens one at a time
  2. If a token is an integer, write it into the output
  3. If a token is an operator, push it to the stack, if the stack is empty. If the stack is not empty, you pop entries with higher or equal priority and only then you push that token to the stack
  4. If a token is a left parentheses ' ( ', push it to the stack
  5. If a token is a right parentheses ' ) ', you pop entries until you meet ' ( '
  6. When you finish reading the string, you pop up all tokens which are left there
  7. Arithmetic precedence is in increasing order: (i) addition and subtraction (ii) multiplication and division (iii) exponentiation 









Backtracking


src : google

Think of a maze, how will you find away from an entrance to an exit?
Once you reach a dead end, you must backtrack. But backtrack to where? to the previous choice point. Therefore, at each choice point you store on a stack all possible choices. Then backtracking simply means popping a next choice from the stack.

Function calls

The stack is used to keep information about the active functions or subroutines.

CPU scheduling

  • Whenever the CPU becomes idle, it is the job of the CPU scheduler to select another process from the ready queue to run next.
  • The storage structure for the ready queue and the algorithm used to select the next process can be a FIFO queue.

Queuing theory

It is a branch of mathematics that deals with computing, probabilistically, how long users expect to wait on a line, how long the line gets, and other such questions.

Level order traversing in trees


LevelTraversal(tree)
     if tree == NULL:
          return
     queue q
     q.enqueue(tree)
     while not q.empty():
          node ← q.dequeue()
          print(node)
          if node.left != NULL:
               q.enqueue(node.left)
          if node.left != NULL:
               q.enqueue(node.left)

Let's say we call function LevelTraversal(root), the empty queue is created and root in enqueued.

Practice Problems

  1. Infix to postfix ( HackerEarth )
  2. Vidhur's job scheduling ( HackerEarth )
  3. Walk on a tree  ( Codechef )
If you find any difficulty in level order traversal for trees, NO WORRIES, we will discuss it again while covering trees.
If you have any doubt or any content related to the above-discussed topics, feel free to drop in the comment section

Thank You for Reading

Comments