The document discusses stacks and their implementation and use. Stacks follow LIFO order and can be implemented using arrays or linked lists. Pushing adds an element to the top of the stack while popping removes the top element. Postfix notation is used to evaluate arithmetic expressions by scanning the expression and operating on elements based on their position.
The document discusses stacks and their implementation and use. Stacks follow LIFO order and can be implemented using arrays or linked lists. Pushing adds an element to the top of the stack while popping removes the top element. Postfix notation is used to evaluate arithmetic expressions by scanning the expression and operating on elements based on their position.
The document discusses stacks and their implementation and use. Stacks follow LIFO order and can be implemented using arrays or linked lists. Pushing adds an element to the top of the stack while popping removes the top element. Postfix notation is used to evaluate arithmetic expressions by scanning the expression and operating on elements based on their position.
The document discusses stacks and their implementation and use. Stacks follow LIFO order and can be implemented using arrays or linked lists. Pushing adds an element to the top of the stack while popping removes the top element. Postfix notation is used to evaluate arithmetic expressions by scanning the expression and operating on elements based on their position.
STACK Linear Data Structures • There are certain frequent situations in computer science when one wants to restrict insertion and deletions so that they can take place only at the beginning or at the end not in the middle.
– Stack
2 Stack
3 Stack • A Stack is a list of elements in which an element may be inserted or deleted only at one end, call top of the Stack
• Two basic operations are associated
with Stack – Push : Insert an element into a stack – Pop : Delete an element from a stack
4 Stack • Stores a set of elements in a particular order
• Stack principle: LAST IN FIRST
OUT= LIFO
• It means: the last element inserted is
the first one to be removed
• Which is the first element to pick up?
5 Last In First Out
D top top C top C C B B top A B B A A A A Initial 1 2 3 4 5 6 Last In First Out
top top C B top A B A A 8 7 6 5 7 Representation of Stack
Stack can be represented in two
different ways :
[1] Linear ARRAY
[2] One-way Linked list
8 Array Representation of Stack
STACK A B C 0 1 2 3 4 5 6 7
TOP 2 MAXSTK 7 TOP = -1 or TOP = NULL will indicate that the stack is empty 9 PUSH Operation Perform the following steps to PUSH an ITEM onto a Stack [1] If TOP = MAXSTK, Then print: Overflow, Exit [ Stack already filled] [2] Set TOP = TOP + 1 [3] Set STACK[TOP] = ITEM [Insert Item into new TOP Position] [4] Exit
10 POP Operation Delete top element of STACK and assign it to the variable ITEM [1] If TOP = -1, Then print Underflow and Exit [2] Set ITEM = STACK[TOP] [3] Set TOP = TOP -1 [4] Exit
11 Linked List Representation of Stack
TOP Head CC BB AA X
Top Of Stack
12 PUSH Operation • Push operation into the stack is accomplished by inserting a node into the front of the list [Insert it as the first node in the list]
TOP CC BB AA X
PUSH DD into STACK DD
13 PUSH Operation STACK before PUSH Operation
TOP CC BB AA X
STACK After PUSH Operation
TOP DD CC BB AA X
14 PUSH Operation
[1] NEW->INFO = ITEM
[2] NEW->LINK = TOP [3] TOP = NEW [4] Exit
15 POP Operation
• POP operation is accomplished by
deleting the node pointed to by the TOP pointer [Delete the first node in the list]
16 POP Operation STACK before POP Operation TOP DD CC BB AA X
STACK After POP Operation
TOP CC BB AA X 17 POP Operation
[1] IF TOP == NULL Then Write
Underflow and Exit [2] Set ITEM = TOP->INFO [3] Set TOP = TOP->LINK [4] Exit
18 Arithmetic Expression; Polish Notation • Let Q be an arithmetic expression involving constant and operations
• Find the value of Q using reverse Polish
(Postfix) Notation
19 • Infix notation [Operator symbol is placed between two Operand] A + B , C – D , E * F , G /H (A + B) * C and A + (B*C) • Polish Notation [Operator symbol is placed before its operand] +AB, -CD, *EF , /GH Polish Notations are frequently called Prefix
21 • Infix expression to Polish Notation [ ] to indicate a partial translation
(A+B)*C = [+AB]*C = *+ABC
A+(B*C) = A+[*BC] = +A*BC
(A+B)/(C-D) = [+AB]/[-CD] = /+AB-CD
22 Polish Notation • The fundamental property of Polish notation is that the order in which the operations are to be performed is completely determined by the positions of the operators and operand in the expression. • One never needs parenthesis when writing expression in Polish notations
23 Reverse Polish Notation • Operator symbol is placed after its two operand AB+, CD-, EF*, GC/ (A+B)/(C-D) = [AB+]/[CD-] = AB+CD-/ • One never needs parenthesis to determine the order of the operation in any arithmetic expression written in reverse Polish notation. • Also known as Postfix notation 24 • Computer usually evaluates an arithmetic expression written in infix notation in two steps: • First Step: Converts the expression to Postfix notation • Second Step: Evaluates the Postfix expression.
25 Evaluation of Postfix Expression • Algorithm to find the Value of an arithmetic expression P Written in Postfix [1] Add a right parenthesis ‘)” at the end of P. [This act as delimiter] [2] Scan P from left to right and repeat Steps 3 and 4 for each element of P until the delimiter “)” is encountered
26 Evaluation of Postfix Expression [3] If an operand is encountered, put it on STACK [4] If an operator is encountered, then (a) Remove the two top elements of STACK, where A is the top element and B is the next-to-top element (b) Evaluate B A (c) Place the result of (b) on STACK
31 Infix to Postfix • Q is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix notation, P [1] Push “(“ onto STACK and “)” to the end of Q [2] Scan Q from Left to Right and Repeat Steps 3 to 6 for each element of Q until the STACK is empty
32 [3] If an operand is encountered, add it to P [4] If a left parenthesis is encountered, push it onto STACK [5] If an operator is encountered, then: (a)Push the operator into the stack, if the incoming operator is having higher precedence than the operator present in top of stack. (Or)Repeatedly pop from STACK and add to P each operator (on the top of STACK) which has precedence as or higher precedence than . (b) Add to STACK 33 [6] If a right parenthesis is encountered, then (a) Repeatedly pop from the STACK and add to P each operator (on top of STACK) until a left parenthesis is encountered. (b) Remove the left parenthesis. [Do not add it to P] [7] Exit
34 Example (Infix) •Q:A+(B*C–(D/E îF)*G)*H
A + ( B * C - ( D / E î F ) * G ) * H ) 1 2 3 4 5 6 7 8 9 20
35 A + ( B * C - ( D / E î F ) * G ) * H ) 1 2 3 4 5 6 7 8 9 20
Symbol STACK Expression P
Scanned ( 1 A ( A 2 + (+ A 3 ( (+( A 4 B (+( AB 5 * (+(* AB 6 C (+(* ABC 7 - (+(- ABC* 8 ( (+(-( ABC* 36 A + ( B * C - ( D / E î F ) * G ) * H ) 1 2 3 4 5 6 7 8 9 20
Symbol STACK Expression P
Scanned 8 ( (+(-( ABC* 9 D (+(-( ABC*D 10 / (+(-(/ ABC*D 11 E (+(-(/ ABC*DE 12 î (+(-(/î ABC*DE 13 F (+(-(/î ABC*DEF 14 ) (+(- ABC*DEFî/ 15 * (+(-* ABC*DEFî/ 37 A + ( B * C - ( D / E î F ) * G ) * H ) 1 2 3 4 5 6 7 8 9 20
