CS-2001 Data Structures

Stack and Queues

Week8 | Lecture 22-25
 Topics
• Stack
• Queues
– Types of Queues
• Stack Application
 Stack
• Stacks in Data Structures is a linear type of
data structure that follows the LIFO
(Last-In-First-Out) of FILO (First in last out)
principle and allows insertion and deletion
operations from one end of the stack data
structure, that is top.
• Implementation of the stack can be done by
contiguous memory which is an array, and
non-contiguous memory which is a linked list.
 Stack
• Stacks are based on the LIFO principle, i.e., the
element inserted at the last, is the first element to
come out of the list.
• Insertion and deletion in stacks take place only from
one end of the list called the top.
• Stack has a dynamic and fixed size.
• The stack can contain elements of the different data
types.
• Stack has only one type.
• It contains only one pointer known as a top pointer.
The top pointer holds the address of the last inserted
or the topmost element of the stack.
 Stack Operations
• Operation on Stack
– push()
– pop()
– peek() /top()
– count()
– isEmpty()
– isFull()
– display()
 Time Complexity
• Push Operation : O(1)
• Pop Operation : O(1)
• Top Operation : O(1)
• Search Operation : O(n)
 Queue
• Queue is an abstract data structure,
somewhat similar to Stacks. Unlike stacks, a
queue is open at both its ends. One end is
always used to insert data (enqueue) and the
other is used to remove data (dequeue).
• Queue follows First-In-First-Out methodology.
 Queue
• Queues are based on the FIFO principle, i.e.,
the element inserted at the first, is the first
element to come out of the list.
• Insertion and deletion in Queues takes place
only from rear and front respectively.
• Queue has a dynamic and fixed size.
• Queue can contain elements of different data
type.
 Time Complexity
• Enqueue: O(1)
• Dequeue: O(1)
• Size: O(1)
 Queue Operation
• Enqueue()
• Dequeue()
• isFull()
• isEmpty()
• count()
 Circular Queue
• Circular Queue is a linear data structure in which the
operations are performed based on FIFO (First In First
Out) principle and the last position is connected back
to the first position to make a circle.
• It is also called ‘Ring Buffer’. It is a type of Queue data
structure which overcomes some drawback of the
simple queue data structure.
• The circular queue solves the major limitation of
the normal queue. In a normal queue, after a bit of
insertion and deletion, there will be non-usable
empty space.
 Circular Queue Operations
• Enqueue()
• Dequeue()
• isFull()
• isEmpty()
• count()
 Time Complexity
• Enqueue: O(1)
• Dequeue: O(1)
• Size: O(1)
 Difference between Queue and
Circular Queue

It follows the FIFO principle in order to It has no specific order for execution.
perform the tasks.
The usage of memory is inefficient. The memory can be more efficiently
utilized.
The memory space occupied by the linear It requires less memory as compared to
queue is more than the circular queue. linear queue.
In linear queue, insertion is done from the In circular queue, the insertion and
rear end, and deletion is done from the deletion can take place from any end.
front end.
In a linear queue, we can easily fetch out In a circular queue, we cannot fetch out
the peek value. the peek value easily.
 Stack - Real Life Application
• Movie Websites
• Recursion Stack, Program Stack
• Call logs, E-mails, Google photos’ any gallery,
YouTube downloads, Notifications ( latest
appears first ).
• Message logs and all messages you get are
arranged in a stack.
• History of visited websites.
 Queue - Real Life Application
• Handle website traffic
• Most internet requests and processes use
queue.
• Complaint Systems
• Data packets in communication are arranged
in queue format.
• Operating System uses queues for job
scheduling.
Circular Queue - Real Life Application
• Memory management: circular queue is used in
memory management.
• Process Scheduling: A CPU uses a queue to
schedule processes.
• Traffic Systems: Queues are also used in traffic
systems.
• Assigning turns to play for multiplayer gaming
systems
• Browsing through the open windows
applications using alt+tab(Microsoft Windows)
 Exercise
• To reverse a word. (Stack or Queue?)
• An "undo " / " redo" mechanism in text
editors. (Stack or Queue?)
• Write a program to check palindrome string
Prefix, Infix & Postfix
Expressions
 Stack Implementation
• An Expression is a combination of symbols that can be numbers
(constants), variables, operations, symbols of grouping and other
punctuation written is a specific format/way.
• Infix
An expression is called the infix expression if the operator appears
in the expression in between the operands. Simply of the form
(operand1 operator operand2). E.g. A+B
• Prefix
An expression is called the prefix expression if the operator
appears in the expression before the operands. Simply of the form
(operator operand1 operand2). E.g. +AB
• Postfix
An expression is called the postfix expression if the operator
appears in the expression after the operands. Simply of the form
(operand1 operand2 operator). E.g. AB+
 Expressions
• Order of Operations(Operator Precedence) –
1) Parentheses – {}, [], ()
2) Exponents(Right to Left) – A^B, 2^3^4
3) Multiplication & Division(Left to Right) – A*B/C
4) Addition & Subtraction(Left to Right) – A + B – C
• Associativity –
Associativity describes the rule where operators with the
same precedence appear in an expression. For example,
in expression a + b − c, both + and – have the same
precedence, then which part of the expression will be
evaluated first, is determined by associativity of those
operators.
 Why 3 expressions
• Infix expressions are human readable but not
efficient for machine reading
• Prefix and Postfix do not need the concept of
precedence & associativity hence it becomes
highly efficient to parse expressions in prefix
or postfix formats.
 Exercise – infix to prefix and postfix
Infix Prefix Postfix
( AX + ( B * C ) ) ? ?
( ( AX + ( B * CY ) ) / ( D E ) ) ? ?
((A+B)*(C+E)) ? ?
( AX * ( BX * ( ( ( CY + AY ) + BY ) * CX ) ) ) ? ?
((H*((((A+((B+C)*D))*F)*G)*E))+J) ? ?
 solution
Infix Prefix Postfix
( AX + ( B * C ) ) + AX * B C AX B C * +

( ( AX + ( B * CY ) ) / ( D E ) ) / + AX * B CY D E AX B CY * + D E /

((A+B)*(C+E)) *+AB+CE AB+CE+*

( AX * ( BX * ( ( ( CY + AY ) + BY ) * CX ) ) ) * AX * BX * + + CY AY BY CX AX BX CY AY + BY + CX * * *

((H*((((A+((B+C)*D))*F)*G)*E))+J) +*H***+A*+BCDFGEJ HABC+D*+F*G*E**J+

 Prefix to infix
Prefix Infix
*/-+ABC*ACB ?
/*+*ABC-*ABC*BC ?
+/*A+BC+AB^-*ABC2 ?
/+*A+BC*AB*–BC+*BCA ?
+ /+ 2 4 3 / * 4 + / 6 2 1 8 ?
 Solution
Prefix Infix
*/-+ABC*ACB ((((A + B) - C) / (A * C)) * B)
/*+*ABC-*ABC*BC ((((A * B) + C) * ((A * B) - C)) / (B * C))
+/*A+BC+AB^-*ABC2 (((A * (B + C)) / (A + B)) + (((A * B) - C) ^ 2))
/+*A+BC*AB*–BC+*BCA (((A * (B + C)) + (A * B)) / ((B - C) * ((B * C) + A)))
+ /+ 2 4 3 / * 4 + / 6 2 1 8 ((4 * ((6 / 2) + 1)) / 8)
 Postfix to infix
Prefix Infix
84/32*6431+*+-+ ?
ABC*+D+ ?

AB+CD+* ?
AB*CD*+ ?
AB+C+D+ ?
 Solution
Prefix Infix
84/32*6431+*+-+ ((8 / 4) + ((3 * 2) - (6 + (4 * (3 + 1)))))
ABC*+D+ A+B*C+D

AB+CD+* (A + B) * (C + D)
AB*CD*+ A*B+C*D
AB+C+D+ A+B+C+D
 Postfix to prefix
postfix prefix
84/32*6431+*+-+ ?
ABC*+D+ ?

AB+CD+* ?
AB*CD*+ ?
AB+C+D+ ?
 Solution
Prefix prefix
84/32*6431+*+-+ +/84-*32+6*4+31
ABC*+D+ ++A*BCD

AB+CD+* *+AB+CD
AB*CD*+ +*AB*CD
AB+C+D+ +++ABCD
 Prefix to postfix
Prefix postfix
*/-+ABC*ACB ?
/*+*ABC-*ABC*BC ?
+/*A+BC+AB^-*ABC2 ?
/+*A+BC*AB*–BC+*BCA ?
+ /+ 2 4 3 / * 4 + / 6 2 1 8 ?
 Solution
Prefix postfix
*/-+ABC*ACB AB+C-AC*/B*
/*+*ABC-*ABC*BC AB*C+AB*C-*BC*/
+/*A+BC+AB^-*ABC2 ABC+*AB+/AB*C-2^+
/+*A+BC*AB*–BC+*BCA ABC+*AB*+BC-BC*A+*/
+ /+ 2 4 3 / * 4 + / 6 2 1 8 462/1+*8/
 Infix to postfix Algorithm
• If operand
print
• If ' ( '
push to stack
• If ' ) '
pop from stack and print until ' ( ' is found
• If operator
pop from stack and print until an operator with
. less precedence is found
 Infix to Prefix
• Reverse infix expression & swap ‘(‘ to ”)’ & ‘)’ to ”(‘
• If operand
– print
• If ' ( '
– push to stack
• If ' ) '
– pop from stack and print until ' ( ' is found
• If operator
– pop from stack and print until an operator with less precedence is found
 Postfix to Infix
• if operand,
push it onto the stack
• if operator,
– pop 2 operands from the stack
– add this incoming operator in between the 2 operands
– add ‘(‘ & ‘)’ to the whole expression
– push this whole new expression string back into the
stack.
• pop and print the full infix expression from the stack.
 Prefix to Infix
• reverse the prefix expression
• if operand,
push it onto the stack
• if operator
– pop 2 operands from the stack,
– add this incoming operator in between the 2 operands,
– add ‘(‘ & ‘)’ to the whole expression
– push this whole new expression string back into the stack.
• pop and print the full infix expression from the stack.
 Postfix to Prefix
• if operand
– push it onto the stack
• if operator
– pop 2 operands from the stack
– add this incoming operator in before the 2
operands
– push this whole new expression string back into
the stack.
• pop and print the full prefix expression from the
stack.
 Prefix to Postfix
• scan prefix expression from right to left
• if operand
– push it onto the stack
• if operator
– pop 2 operands from the stack
– add this incoming operator in before the 2 operands
– push this whole new expression string back into the
stack.
• pop and print the full postfix expression from the stack.