STACK & QUEUE

STACK DATA STRUCTURE

Stack is a linear data structure which follows a particular order in which the operations are
performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
Mainly the following basic operations are performed in the stack:
• Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition.
• Pop: Removes an item from the stack. The items are popped in the reversed order in which they
are pushed. If the stack is empty, then it is said to be an Underflow condition.
• Peek or Top: Returns top element of stack.
• isEmpty: Returns true if stack is empty, else false.
• Isfull: Returns true if stack is full, else false.
STACK DATA STRUCTURE
How to understand a stack practically?
There are many real life examples of stack. Consider the simple example of plates stacked over one
another in canteen. The plate which is at the top is the first one to be removed, i.e. the plate which
has been placed at the bottom most position remains in the stack for the longest period of time. So,
it can be simply seen to follow LIFO/FILO order.
Time Complexities of operations on stack:
push(), pop(), isEmpty() and peek() all take O(1) time. We do not run any loop in any of these
operations.
STACK DATA STRUCTURE
Real life examples of stack are:
• To reverse a word. You push a given word to stack - letter by letter - and then pop letters from
the stack.
• An "undo" mechanism in text editors; this operation is accomplished by keeping all text
changes in a stack.
– Undo/Redo stacks in Excel or Word.
• Language processing :
– space for parameters and local variables is created internally using a stack.
– compiler's syntax check for matching braces is implemented by using stack.
• A stack of plates/books in a cupboard.
• Wearing/Removing Bangles.
• Support for recursion
– Activation records of method calls.
 Push Operation
• The push operation is used to insert an element in to the stack.
• The new element is added at the topmost position of the stack.
• First check if TOP==MAX-1.
If true, then it means the stack is full and no more insertions can
further be added, an OVERFLOW message is printed.
• If not true, increase TOP by 1, then add the element at TOP position

A B C D E

0 1 2 3 TOP = 4 5 6 7 8 9

A B C D E F

0 1 2 3 4 TOP =5 6 7 8 9

5
 Pop Operation
• The pop operation is used to delete the topmost element from the
stack.
• First check if TOP == -1.
If true then it means the stack is empty so no more deletions can
further be done, an UNDERFLOW message is printed.
If not true, get the value of the top element, decrease TOP by one.

A B C D E

0 1 2 3 TOP = 4 5 6 7 8 9

A B C D

0 1 2 TOP = 3 4 5 6 7 8 9

6
7
8
9
10
11
12
13
14
STACK IMPLEMENTATION USING ARRAY

• Refer Program here stackA.c

STACK IMPLEMENTATION USING LINKED LIST

• Stack is an area of memory that holds all local variables and parameters used by any function,
and remembers the order in which functions are called so that function returns occur correctly.
• Each time a function is called, its local variables and parameters are “pushed onto” the stack.
When the function returns these locals and parameters are “popped.” Because of this, the size of
a program’s stack fluctuates constantly as the program is running, but it has some maximum
size.
• A list with the restriction that insertion and deletion can be performed only from one end.
• stack is as a last in, first out (LIFO) abstract data type and linear data structure.
• Linked list is a data structure consisting of a group of nodes which together represent a
sequence.
• Here we need to apply the application of linked list to perform basic operations of stack.

• Refer Program here

THE POLISH NOTATION
INFIX NOTATION
• To add A, B, we write
A+B
• To multiply A, B, we write
A*B
• The operators ('+' and '*') go in between the operands ('A' and 'B')
• This is "Infix" notation.
PREFIX NOTATION
• Instead of saying "A plus B", we could say "add A,B " and write
+AB
• "Multiply A,B" would be written
*AB
• This is Prefix notation.
POSTFIX NOTATION
• Another alternative is to put the operators after the operands as in
AB+
and
AB*
• This is Postfix notation.
PARENTHESES
• Evaluate 2+3*5.
• + First:
(2+3)*5 = 5*5 = 25
• * First:
2+(3*5) = 2+15 = 17
• Infix notation requires Parentheses.
WHAT ABOUT PREFIX NOTATION?
• +2*35=
=+2*35
= + 2 15 = 17
• *+235=
=*+235
= * 5 5 = 25
• No parentheses needed!
POSTFIX NOTATION
• 235*+=
=235*+
= 2 15 + = 17
• 23+5*=
=23+5*
= 5 5 * = 25
• No parentheses needed here either!
CONCLUSION:
• Infix is the only notation that requires parentheses in order to change the order in which the
operations are done.
FULLY PARENTHESIZED EXPRESSION
• A fully parenthesized infix arithmetic expression is an infix arithmetic expression where every
operator and its arguments are contained in parentheses.
• Which is fully parenthesized?
(A+B)*C
( ( A + B) * C )
( ( A + B) * ( C ) )
(2+3)
(1+((2+3)∗(4∗5)))
 Infix Notation
• Infix, Postfix and Prefix notations are three different but equivalent
notations of writing algebraic expressions.
• While writing an arithmetic expression using infix notation, the
operator is placed between the operands. For example, A+B; here,
plus operator is placed between the two operands A and B.
• Although it is easy to write expressions using infix notation,
computers find it difficult to parse as they need a lot of information
to evaluate the expression.
• Information is needed about operator precedence, associativity
rules, and brackets which overrides these rules.
• So, computers work more efficiently with expressions written using
prefix and postfix notations.
 Postfix Notation
• Postfix notation was given by Jan Łukasiewicz who was a Polish
logician, mathematician, and philosopher. His aim was to develop
a parenthesis-free prefix notation (also known as Polish notation)
and a postfix notation which is better known as Reverse Polish
Notation or RPN.
• In postfix notation, the operator is placed after the operands. For
example, if an expression is written as A+B in infix notation, the
same expression can be written as AB+ in postfix notation.
• The order of evaluation of a postfix expression is always from left
to right.
 Postfix Notation
• The expression (A + B) * C is written as:

AB+C* in the postfix notation.

• A postfix operation does not even follow the rules of operator

precedence. The operator which occurs first in the expression is

operated first on the operands.

• No parenthese

• For example, given a postfix notation AB+C*. While evaluation,

addition will be performed prior to multiplication.

 Prefix Notation
• In a prefix notation, the operator is placed before the operands.
• For example, if A+B is an expression in infix notation, then the
corresponding expression in prefix notation is given by +AB.
• While evaluating a prefix expression, the operators are applied to
the operands that are present immediately on the right of the
operator.
• Prefix expressions also do not follow the rules of operator
precedence, associativity, and even brackets cannot alter the
order of evaluation.
• The expression (A + B) * C is written as:
*+ABC in the prefix notation
INFIX TO POSTFIX CONVERSION
Infix expression: The expression of the form a op b. When an operator is in-between every pair
of operands.
Postfix expression: The expression of the form a b op. When an operator is followed for every
pair of operands.
Why postfix representation of the expression?
The compiler scans the expression either from left to right or from right to left.
• Consider the below expression: a + b * c + d
If op1 = +, op2 = *, op3 = +
• The compiler first scans the expression to evaluate the expression b * c, then again scan the
expression to add a to it. The result is then added to d after another scan.
• The repeated scanning makes it very in-efficient. It is better to convert the expression to
postfix(or prefix) form before evaluation.
• The corresponding expression in postfix form is: abc*+d+. The postfix expressions can be
evaluated easily using a stack.
OPERATOR PRECEDENCE TABLE
INFIX TO POSTFIX CONVERSION AND
POSTFIX EXPRESSION EVALUATION

1. infix: (A + B) * C + D / (E + F * G) - H
postfix: A B + C * D E F G * + / + H -
2. infix: A + ((B - C * D) / E ) + F - G / H
postfix: A B C D * - E / + F + G H / -
3. (A * B + C) / D - E / (F + G)
postfix: A B * C + D / E F G + / -
4. What is the value of the following postfix expression?
54 6 + 7 4 - * 9 / 35 15 + +

[Link]
Evaluation of an Infix Expression
STEP 1: Convert the infix expression into its equivalent postfix expression
Algorithm to convert an Infix notation into postfix notation
Step 1: Add ‘)” to the end of the infix expression
Step 2: Push “(“ on to the stack
Step 3: Repeat until each character in the infix notation is scanned
IF a “(“ is encountered, push it on the stack
IF an operand (whether a digit or an alphabet) is encountered,
add it to the postfix expression.
IF a “)” is encountered, then;
a. Repeatedly pop from stack and add it to the postfix expression
until a “(” is encountered.
b. Discard the “(“. That is, remove the “(“ from stack and do not
add it to the postfix expression
IF an operator X is encountered, then;
a Repeatedly pop from stack and add each operator (popped from the
stack) to the postfix expression which has the same precedence or a
higher precedence than X
b. Push the operator X to the stack
Step 4: Repeatedly pop from the stack and add it to the postfix expression
until the stack is empty
Step 5: EXIT
Evaluation of an Infix Expression
STEP 2: Evaluate the postfix expression

Algorithm to evaluate a postfix expression

Step 1: Add a “)” at the end of the postfix expression

Step 2: Scan every character of the postfix expression and
repeat
steps 3 and 4 until “)”is encountered
Step 3: IF an operand is encountered, push it on the stack
IF an operator X is encountered, then
a. pop the top two elements from the stack as A and B
b. Evaluate B X A, where A was the topmost element
and B was
the element below A.
c. Push the result of evaluation on the stack
[END OF IF]
Step 4: SET RESULT equal to the topmost element of the stack
Step 5: EXIT
 Evaluation of an Infix Expression
• Example: evaluate “9 - (( 3 * 4) + 8) / 4”.
• Step 1 infix “(9 - (( 3 * 4) + 8) / 4)" => postfix “9 3 4 * 8 + 4 / -“
• Step 2 evaluate “9 3 4 * 8 + 4 / -“
infix Stack postfix Character
Stack
( ( scanned
9 ( 9
9 9
- (- 9
3 9, 3
( (-( 9
( (-(( 9 4 9, 3, 4

3 (-(( 93 * 9, 12
* (-((* 93
8 9, 12, 8
4 (-((* 934
+ 9, 20
) (-( 934*
+ (-(+ 934* 4 9, 20, 4
8 (-(+ 934*8 / 9, 5
) (- 934*8+
- 4
/ (-/ 934*8+
4 (-/ 934*8+4
) 934*8+4/-
Postfix expressions: Algorithm using stacks (cont.)
 Convert Infix Expression into Prefix Expression
Consider an infix expression: (A – B / C) * (A / K – L)
• Step 1: Reverse the infix string. Note that while reversing the string
you must interchange left and right parenthesis.
(L – K / A) * (C / B – A)
• Step 2: Obtain the corresponding postfix expression of the infix
expression obtained as a result of Step 1.
• The expression is: (L – K / A) * (C / B – A)
• Therefore, [L – (K A /)] * [ (C B /) - A ]
= [LKA/-] * [ CB/A-]
=LKA/-CB/A-*
• Step 3: Reverse the postfix expression to get the prefix expression
• Therefore, the prefix expression is * - A / B C - / A K L
INFIX TO PREFIX
• A*B+ C/D
Prefix: +*AB/CD
• (A*B)+C
Prefix: +*ABC
(A && B) || C || ! (E > F)
• Prefix: || && A B || C ! > E F
• Postfix: A B && C || E F > ! ||

! (A && ! ((B < C) || (C > D))) || (C < E)

• postfix: A B C < C D > || ! && ! C E < ||
• prefix: || ! && A ! || < B C > C D < C E
[Link]

Previous years GATE questions

[Link]
four-element-gate-cse-theory-of-computation-finite-automata-and-regular-language-sozflytewkqwhc7j