Topics |
|---|
Prefix expression is known as polish notation and postfix expression is meant by reverse polish notation.
While evaluating an infix expression, there is an evaluation order according to which take place in the below mentioned specified order.
♦ Brackets or Parenthesis
♦ Exponentiation
♦ Multiplication or division
♦ Addition or Subtraction
The operators with the same priority (example: * and /) are evaluated from left to right.
The steps to convert an infix expression into a postfix expression are given below:
a)Determine the actual evaluation order by inserting braces.
b)Convert the expression in the innermost braces into postfix notation by putting the operator after the operands.
c)Repeat step b until entire expression is converted into postfix notation.
An infix expression is difficult for the machine to know and keep track of precedence of operators. On the other hand, a postfix expression itself determines the precedence of operators. Therefore, for the machine it is easier to carry out a postfix expression than an infix expression.
Evaluation of a postfix expression states:
♦ While reading the expression from left to right, push the element in the stack if it is an operand.
♦ Pop the two operands from the stack, pop one operand from the stack and then evaluate it (two operands and an operator)
♦ Push back the result of the evaluation. Repeat it till the end of the expression.
A queue is a FIFO structure and it can be implemented either as an array or as a linked list. In its implementation, insertions take place at the "rear" end and deletions at the "front" end.
When a queue is created as a array, its space required (no. of elements) is declared before processing. The beginning of the array becomes its "front" end and the end of the array becomes its "rear" end. "Front" stores the number of first element in the queue and "rear" stores the number of last element in the queue.
A queue is stored in the memory using an array QUEUE with N elements. New elements will be added to the rear end of the queue. With every insertion, the value of "rear" is increased by 1. This means that after N insertions, the rear element will occupy QUEUE [N] and after it, the queue becomes FULL and no more elements can be added to it. The working of insertions in an array queue is shown detail in the below figure:
Deletions can occur at the "front" end only, with every deletion, the "front" gets modified. Whenever an element is deleted from the queue, the value of "front" is increased by 1.
Linked queues are the queues having links among its elements. Two pointers are maintained to store the "front" position and the "rear" position.
Insertions in a linked queue take place only at the "rear" end i.e., the "rear" gets modified with every insert.
Deletions in a linked queue take place from the "front" end. Therefore, the "front" gets modified with every delete.
The two popular variations of queues are
♦ Circular queue
♦ Dequeue(double-ended queue)
Circular queues are the queues implemented in circle form rather than a straight line. It overcomes the problem of utilized space in linear queues implemented as arrays
Dequeue or double - ended queues are the refined queues in which elements can be added or removed at either end but not in the middle.
There are two variations of a deque -
An input restricted deque is a deque which allows insertions at only one end but allows deletions at both ends of the list.
An output restricted deque is a deque which allows deletions at only one end of the list but allows insertions at both ends of the list.
