UNIT 2
STACK AND QUEUE
The stack ADT and its applications
A stack is an ordered list of elements in which elements are always inserted and deleted at one
end, say the beginning. In the terminology of stacks, this end is called the top of the stack,
whereas the other end is called the bottom of the stack. Also the insertion operation is called
push and the deletion operation is called pop. The element at the top of a stack is frequently
referred, so we highlight this special form of getElement.
A stack ADT can be specified by the following basic operations. Once again we assume that we
are maintaining a stack of characters. In practice, the data type for each element of a stack can be
of any data type. Characters are chosen as place-holders for simplicity.
S = init(); - Initialize S to an empty stack.
isEmpty(S); - Returns "true" if and only if the stack S is empty, i.e., contains no elements.
isFull(S); - Returns "true" if and only if the stack S has a bounded size and holds the maximum
number of elements it can.
top(S); - Return the element at the top of the stack S, or error if the stack is empty.
S = push(S,ch); - Push the character ch at the top of the stack S.
S = pop(S); - Pop an element from the top of the stack S.
print(S); - Print the elements of the stack S from top to bottom.
An element popped out of the stack is always the last element to have been pushed in. Therefore,
a stack is often called a Last-In-First-Out or a LIFO list.
Applications of stacks
Stacks are used in a variety of applications. While some of these applications are "natural", most
other are essentially "pedantic". Here is a list anyway.
For processing nested structures, like checking for balanced parentheses, evaluation of
postfix expressions.
For handling function calls and, in particular, recursion.
For searching in special data structures (depth-first search in graphs and trees), for
example, for implementing backtracking.
1
The queue ADT and its applications
A queue is like a "natural" queue of elements. It is an ordered list in which all insertions occur at
one end called the back or rear of the queue, whereas all deletions occur at the other end called
the front or head of the queue. In the popular terminology, insertion and deletion in a queue are
respectively called the enqueue and the dequeue operations. The element dequeued from a queue
is always the first to have been enqueued among the elements currently present in the queue. In
view of this, a queue is often called a First-In-First-Out or a FIFO list.
The following functions specify the operations on the queue ADT. We are going to maintain a
queue of characters. In practice, each element of a queue can be of any well-defined data type.
Q = init(); - Initialize the queue Q to the empty queue.
isEmpty(Q); - Returns "true" if and only if the queue Q is empty.
isFull(Q); - Returns "true" if and only if the queue Q is full, provided that we impose a limit on
the maximum size of the queue.
front(Q); - Returns the element at the front of the queue Q or error if the queue is empty.
Q = enqueue(Q,ch); - Inserts the element ch at the back of the queue Q. Insertion request in a full
queue should lead to failure together with some appropriate error messages.
Q = dequeue(Q); - Delete one element from the front of the queue Q. A dequeue attempt from an
empty queue should lead to failure and appropriate error messages.
print(Q); - Print the elements of the queue Q from front to back.
Applications of queues
For implementing any "natural" FIFO service, like telephone enquiries, reservation
requests, traffic flow, etc.
For implementing any "computational" FIFO service, for instance, to access some
resources. Examples: printer queues, disk queues, etc.
For searching in special data structures (breadth-first search in graphs and trees).
For handling scheduling of processes in a multitasking operating system.
2
Applications of Stacks
1 Expression Evaluation
One of the prominent applications of stacks is to expression evaluation. Consider a table
calculator which evaluates arithmetic expressions involving addition, multiplication, subtraction,
and division. For example,2+3 * 5 - 7 is a valid expression. The result of the above expression is
10 as multiplication has precedence over addition and subtraction. To disambiguate, one also
uses parenthesis and write the same expression as 2+ (3*5) - 7.
However, it would be quite cumbersome to use parenthesis when especially, the precedence is
known. Hence, one needs to first convert a given expression into an non-ambiguous model so
that evaluation can be done easily. There are three ways to write an expression. The above way
of writing expressions is called the infix notation because the operators are placed in between the
two operators. There are other ways of writing an expression. In the prefix notation, operators
precede the operands. So the above expression would be written as -+*3 5 2 7. In the postfix
notation, the operators are written after the operands. The postfix equivalent way of writing the
above expression would be 3 5* 2 + 7 -.
It turns out that the postfix and prefix notations are free of ambiguity. We will how that is the
case first and then see how to convert a given expression in the infix form to its prefix form.
2 Evaluating a Postfix Expression
Consider an expression given in the postfix notation. We now see how to evaluate such an
expression. For example, ab * c + is a postfix expression. Since the operators follow the
operands, it is intuitive to see if the previously available two operands are the corresponding
operands for a given operator. This intuition serves well and is correct. So, when processing a
postfix expression from left to right, when we encounter an operator, we have to apply the
operation to the two most recent operands. This suggests that the operands should be placed on a
stack.
3
Infix to postfix conversion
In order to convert infix to postfix expression, we need to understand the precedence of operators
first.
Precedence of Operators
There are five binary operators, called addition, subtraction, multiplication, division and
exponentiation. We are aware of some other binary operators. For example, all relational
operators are binary ones. There are some unary operators as well. These require only one
operand e.g. – and +. There are rules or order of execution of operators in Mathematics called
precedence. Firstly, the exponentiation operation is executed, followed by multiplication/division
and at the end addition/subtraction is done. The order of precedence is
(highest to lowest):
Exponentiation
Multiplication/division *, /
Addition/subtraction +, -
For operators of same precedence, the left-to-right rule applies:
A+B+C means (A+B)+C.
For exponentiation, the right-to-left rule applies:
A B C means A (B C)
We want to understand these precedence of operators and infix and postfix forms of expressions.
A programmer can solve a problem where the program will be aware of the precedence rules and
convert the expression from infix to postfix based on the precedence rules.
Examples of Infix to Postfix
Let’s consider few examples to elaborate the infix and postfix forms of expressions based on their
precedence order:
Infix Postfix
A+ B AB+
12 + 60 – 23 12 60 + 23 –
4
(A + B)*(C – D ) AB+CD–*
A B * C – D + E/F A B C*D – E F/+
A programmer can write the operators either after the operands i.e. postfix notation or before the
operands i.e. prefix notation. Some of the examples are as under:
Infix Postfix
A+B AB+
12 + 60 – 23 12 60 + 23 –
(A + B)*(C – D ) AB+CD–*
A B * C – D + E/F A B C*D – E F/+
The last expression seems a bit confusing but may prove simple by following the rules in letter
and spirit. In the postfix form, parentheses are not used. Consider the infix expressions as
‘4+3*5’ and ‘(4+3)*5’. The parentheses are not needed in the first but are necessary in the
second expression. The postfix forms are:
4+3*5 435*+
(4+3)*5 43+5*
In case of not using the parenthesis in the infix form, you have to see the precedence rule before
evaluating the expression. In the above example, if we want to add first then we have to use the
parenthesis. In the postfix form, we do not need to use parenthesis. The position of operators and
operands in the expression makes it clear in which order we have to do the multiplication and
addition.
Now we will see how the infix expression can be evaluated. Suppose we have a postfix
expression. How can we evaluate it? Each operator in a postfix expression refers to the previous
two operands. As the operators are binary (we are not talking about unary operators here), so two
operands are needed for each operator. The nature of these operators is not affected in the postfix
form i.e. the plus operator (+) will apply on two operands. Each time we read an operand, we
5
will push it on the stack. We are going to evaluate the postfix expression with the help of stack.
After reaching an operator, we pop the two operands from the top of the stack, apply the operator
and push the result back on the stack. Now we will see an example to comprehend the working
of stack for the evaluation of the postfix form. Here is the algorithm in pseudo code form. After
reading this code, you will understand the algorithm.
Stack s; // declare a stack
while( not end of input ) { // not end of postfix expression
e = get next element of input
if( e is an operand )
[Link]( e );
else {
op2 = [Link]();
op1 = [Link]();
value = result of applying operator ‘e’ to op1 and op2;
[Link]( value );
}
}
finalresult = [Link]();
We have declared a Stack‘s’. There is a ‘while loop’ along with ‘not end of input’ condition.
Here the input is our postfix expression. You can get the expression from the keyboard and use
the enter key to finish the expression. In the next statement, we get the next element and store it
in ‘e’. This element can be operator or operand. The operand needs not to be single digit. It may
be of two digits or even more like 60 or 234 etc. The complete number is stored in the ‘e’. Then
we have an ‘if statement’ to check whether ‘e’ is an operand or not. If ‘e’ is an operand than we
wrote [Link](e) i.e. we pushed the ‘e’ onto the stack. If ‘e’ is not the operand, it may be an
operator. Therefore we will pop the two elements and apply that operator. We pop the stack and
store the operand in ‘op2’. We pop the stack again and store the element in ‘op1’. Then the
operator in ‘e’ is applied to ‘op1’ and ‘op2’ before storing the result in value. In the end, we push
the ‘value’ on the stack. After exiting the loop, a programmer may have only one element in the
stack. We pop this element which is the final result.
Consider the example of 4+3*2 having a postfix form of 432*+. Here 4, 3, and 2 are operands
whereas + and * are operators. We will push the numbers 4, 3 and 2 on the stack before getting
the operator *. Two operands will be popped from the stack and * is being applied on these. As
stack is a LIFO structure, so we get 2 first and then 3 as a result of pop. So 2 is store in ‘op1’ and
3 in ‘op2’. Let’s have a look on the program again. On applying * on these, we will push the
result (i.e. 6) on the stack. The ‘while loop’ will be executed again. In case of getting the next
input as operand, we will push it on the stack otherwise we will pop the two operands and apply
the operator on these. Here the next element is the operator +. So two operands will be popped
from the stack i.e. 6 and 4. We will apply the operator plus on these and push the result (i.e. 10)
on the stack. The input is finished. Now we will pop the stack to get the final result i.e. 10.
6
Multiple Stacks and Queues:
Multiple Stacks:
Following pictures are two ways to do two stacks in array:
1. None fixed size of the stacks:
Stack 1 expands from the 0th element to the right
Stack 2 expands from the 12th element to the left
As long as the value of Top1 and Top2 are not next to each other, it has free elements for input
the data in the array
When both Stacks are full, Top1 and Top 2 will be next to each other
There is no fixed boundary between Stack 1 and Stack 2
Elements –1 and –2 are using to store the information needed to manipulate the stack (subscript
for Top 1 and Top 2)
2. Fixed size of the stacks:
Stack 1 expands from the 0th element to the right
Stack 2 expands from the 6th element to the left
As long as the value of Top 1 is less than 6 and greater than 0, Stack 1 has free elements to input
the data in the array
As long as the value of Top 2 is less than 11 and greater than 5, Stack 2 has free elements to
input the data in the array
When the value of Top 1 is 5, Stack 1 is full
When the value of Top 2 is 10, stack 2 is full
Elements –1 and –2 are using to store the size of Stack 1 and the subscript of the array for Top 1
needed to manipulate Stack 1
Elements –3 and –4 are using to store the size of Stack 2 and the subscript of the array for Top 2
needed to manipulate Stack 2
7
Multiple Queues:
Following pictures are two ways to do two queues in array:
None fixed size of the queues:
Queue 1 expands from the 0th element to the right and circular back to the 0th element
Queue 2 expands from the 8th element to the left and circular back to the 8th element
Temporary boundary between the Queue 1 and the Queue 2; as long as there has free elements in
the array and boundary would be shift
Free elements could be any where in the Queue such as before the front, after the rear, and
between front and rear in the Queue
Queue 1’s and Queue 2 ‘s size could be change if it is necessary. When the Queue 1 is full and
the Queue 2 has free space; the Queue 1 can increase the size to use that free space from the
Queue 2. Same way for the Queue 2
Elements –1, –2, and –3 are using to store the size of the Queue 1, the front of the Queue 1, and
the data count for the Queue 1 needed to manipulate the Queue 1
Elements –4, –5, and –6 are using to store the size of the Queue 2, the front of the Queue 2, and
the data count for the Queue 2 needed to manipulate the Queue 2
Inserts data to the Queue 1, Q1Rear = (Q1Front + Q1count) % Q1Size
Inserts data to the Queue 2, Q2Rear = (Q2Front + Q2count) % Q2Size + Q1Size
Deletes data from the Queue 1, Q1Front = (Q1Front + 1) % Q1Size
Deletes data from the Queue 2, Q2Front = (Q2Front + 1) % Q2Size + Q1Size
Fixed size of the queue:
Queue 1 expands from the 0th element to the 4th element and circular back to 0th element
Queue 2 expands from the 8th element to the 5th element and circular back to 8th element
The boundary is fixed between the Queue 1 and the Queue 2
Free elements could be any where in the Queue such as before the front, after the rear, and
between front and rear in the Queue
Elements –1, –2, and –3 are using to store the size of the Queue 1, the front of the Queue 1, and
the data count for the Queue 1 needed to manipulate the Queue 1
8
Elements –4, –5, and –6 are using to store the size of the Queue 2, the front of the Queue 2, and
the data count for the Queue 2 needed to manipulate the Queue 2
Inserts data to the Queue 1, Q1Rear = (Q1Front + Q1count) % Q1Size
Inserts data to the Queue 2, Q2Rear = (Q2Front + Q2count) % Q2Size + Q1Size
Deletes data from the Queue 1, Q1Front = (Q1Front + 1) % Q1Size
Deletes data from the Queue 2, Q2Front = (Q2Front + 1) % Q2Size + Q1Size