# 6 stacks

38 %
62 %

Published on October 1, 2014

Author: emersonferr

Source: slideshare.net

## Description

Universidade Federal da Paraíba Centro de Informática Stacks Lecture 6 1107186 – Estrutura de Dados – Turma 02 Prof. Christian Azambuja Pagot CI / UFPB

What is a Stack? Gene Daniels, 1972. 2 Universidade Federal da Paraíba Centro de Informática

What is a Stack? ● A stack is an abstract data type where elements can be inserted (pushed) and removed (popped) according to the following policies: – Push inserts a new item into the top of the stack. – Pop removes the item at the top of the stack (except when the stack is empty). – The above insert/remove policy is also called LIFO (Last In-First Out). 3 Universidade Federal da Paraíba Centro de Informática View slide

What is a stack? ● Example: 1) push(5) 2) push(3) 3) push(9) Top Top 0 5 Top 1 3 0 5 4) push(1) 5) push(7) 4 7 3 1 2 9 1 3 0 5 6) pop() 3 1 2 9 1 3 0 5 Top 4 Universidade Federal da Paraíba Centro de Informática View slide

An Useful Operation ● Often we want just to check the value of the topmost item on the stack. One possible approach to that would be: x = pop() push(x) ● An easier way would be to have a function that returns the value at the top without actually popping the value: x = top() 5 Universidade Federal da Paraíba Centro de Informática

Stacks in Practice ● Two example applications: – Parenthesis matching. – Reverse Polish Notation (RPN) 6 Universidade Federal da Paraíba Centro de Informática

Parenthesis Matching ● An example arithmetic expression: ((a+b)×(c+d)×e)−(f +g ) ● We must check if the parenthesis are correctly grouped: – # of left parenthesis = # of right parenthesis. – All right parenthesis are preceded by a corresponding left parenthesis. 7 Universidade Federal da Paraíba Centro de Informática

Parenthesis Matching ● If each left parenthesis counts 1, and each right parenthesis counts -1, the overall sum must be 0 (zero). ● At any position in the expression, the partial sum must not be negative! How to keep track of the appropriate counting and ordering? Guess what! 8 Universidade Federal da Paraíba Centro de Informática

Parenthesis Matching ● Each time a left parenthesis is found, it is pushed into the stack. ● Each time a right parenthesis is found, one item is popped from the stack. ● At the end, if the expression is correct, the stack must be empty. 9 Universidade Federal da Paraíba Centro de Informática

Parenthesis Matching ● Example: ((a+b)×(c+d)×e)−(f +g ) Push(')') 0 ( 10 Universidade Federal da Paraíba Centro de Informática

Parenthesis Matching ● Example: ((a+b)×(c+d)×e)−(f +g ) Push(')') 1 ( 0 ( 11 Universidade Federal da Paraíba Centro de Informática

Parenthesis Matching ● Example: ((a+b)×(c+d)×e)−(f +g ) Pop() 0 ( 12 Universidade Federal da Paraíba Centro de Informática

Parenthesis Matching ● Example: ((a+b)×(c+d)×e)−(f +g ) Push(')') 1 ( 0 ( 13 Universidade Federal da Paraíba Centro de Informática

Parenthesis Matching ● Example: ((a+b)×(c+d)×e)−(f +g ) Pop() 0 ( 14 Universidade Federal da Paraíba Centro de Informática

Parenthesis Matching ● Example: ((a+b)×(c+d)×e)−(f +g ) Pop() 15 Universidade Federal da Paraíba Centro de Informática

Parenthesis Matching ● Example: ((a+b)×(c+d)×e)−(f +g ) Push(')') 0 ( 16 Universidade Federal da Paraíba Centro de Informática

Parenthesis Matching ● Example: ((a+b)×(c+d)×e)−(f +g ) Pop() Results: ● Stack is empty. ● No underflows during process. Conclusion: Valid expression! 17 Universidade Federal da Paraíba Centro de Informática

Mathematical Notation ● One aspect of the mathematical notation is related to the position of the operator relative to its operands in an expression. ● There are three possibilities: – Infix (most common): 5 + 8 – Prefix: + 5 8 – Postfix: 5 8 + 18 Universidade Federal da Paraíba Centro de Informática

Reverse Polish Notation (RPN) ● RPN is a postfix, parenthesis free, mathematical notation where the operator follows their operands. (a+b)×(c+d ) – Usual arith. expression: – RPN version: ab+cd+× ● Example: 19 Universidade Federal da Paraíba Centro de Informática

Evaluating an Expression in RPN ● OBS: Each operator refers to the two previous operands. ● Algorithm: for each symbol in expression if (symbol == operand) stack.push(symbol); else if (symbol == operator) op1 = stack.pop(); op2 = stack.pop(); result = eval(op1 operator op2); stack.push(result); end if end if end for At the end, the stack will contain the final result! 20 Universidade Federal da Paraíba Centro de Informática

Evaluating an Expression in RPN ● Example: for each symbol in expression if (symbol == operand) stack.push(symbol); else if (symbol == operator) op1 = stack.pop(); op2 = stack.pop(); result = op1 operator op2; stack.push(result); end if end if end for Usual not.: (5+3)×(5+8) RPN not.: 53+5 8+× 0 5 curr. step 21 Universidade Federal da Paraíba Centro de Informática

Evaluating an Expression in RPN ● Example: for each symbol in expression if (symbol == operand) stack.push(symbol); else if (symbol == operator) op1 = stack.pop(); op2 = stack.pop(); result = op1 operator op2; stack.push(result); end if end if end for Usual not.: (5+3)×(5+8) RPN not.: 53+5 8+× 1 3 0 5 0 5 prev. step curr. step 22 Universidade Federal da Paraíba Centro de Informática

Evaluating an Expression in RPN ● Example: for each symbol in expression if (symbol == operand) stack.push(symbol); else if (symbol == operator) op1 = stack.pop(); op2 = stack.pop(); result = op1 operator op2; stack.push(result); end if end if end for Usual not.: (5+3)×(5+8) RPN not.: 53+5 8+× 1 3 0 5 0 8 prev. step curr. step 23 Universidade Federal da Paraíba Centro de Informática

Evaluating an Expression in RPN ● Example: for each symbol in expression if (symbol == operand) stack.push(symbol); else if (symbol == operator) op1 = stack.pop(); op2 = stack.pop(); result = op1 operator op2; stack.push(result); end if end if end for Usual not.: (5+3)×(5+8) RPN not.: 53+5 8+× 1 5 0 8 0 8 prev. step curr. step 24 Universidade Federal da Paraíba Centro de Informática

Evaluating an Expression in RPN ● Example: for each symbol in expression if (symbol == operand) stack.push(symbol); else if (symbol == operator) op1 = stack.pop(); op2 = stack.pop(); result = op1 operator op2; stack.push(result); end if end if end for Usual not.: (5+3)×(5+8) RPN not.: 53+5 8+× 2 8 1 5 0 8 1 5 0 8 prev. step curr. step 25 Universidade Federal da Paraíba Centro de Informática

Evaluating an Expression in RPN ● Example: for each symbol in expression if (symbol == operand) stack.push(symbol); else if (symbol == operator) op1 = stack.pop(); op2 = stack.pop(); result = op1 operator op2; stack.push(result); end if end if end for Usual not.: (5+3)×(5+8) RPN not.: 53+5 8+× 2 8 1 5 1 13 0 8 0 8 prev. step curr. step 26 Universidade Federal da Paraíba Centro de Informática

Evaluating an Expression in RPN ● Example: for each symbol in expression if (symbol == operand) stack.push(symbol); else if (symbol == operator) op1 = stack.pop(); op2 = stack.pop(); result = op1 operator op2; stack.push(result); end if end if end for Usual not.: (5+3)×(5+8) RPN not.: 53+5 8+× 1 13 0 8 0 104 prev. step curr. step 27 Universidade Federal da Paraíba Centro de Informática

Stack Implementation in C ● A stack is a ordered list of values. ● This approach implements the stack as an array. – There is no need to allocate space for each new item :) – We don't have to worry about deallocating space :) – Space that is not used is wasted :( – The stack will be limited in size :( 28 Universidade Federal da Paraíba Centro de Informática

Stack Implementation in C ● A struct will hold the array and the top indicator: C code excerpt: #define STACK_MAX_SIZE 100 struct Stack{ char v[STACK_MAX_SIZE]; int top; }; ... struct Stack s; 29 Universidade Federal da Paraíba Centro de Informática

Stack Implementation in C ● Push operation: void Push(struct Stack* s, char c) { if (s­> top < (STACK_MAX_SIZE­1)) { s­> top++; s­> v[s­> top] = c; } else { printf("Stack overflow!n"); exit(1); } }; C code excerpt: 30 Universidade Federal da Paraíba Centro de Informática

Stack Implementation in C ● Pop operation: char Pop(struct Stack* s) { if (s­> top >= 0) { char tmp = s­> v[s­> top]; s­> top­­; return tmp; } else { printf("Stack underflow!n"); exit(1); } }; C code excerpt: 31 Universidade Federal da Paraíba Centro de Informática

Stack Implementation in C ● Use example: C code excerpt: int main(void) { If not properly initialized, the stack may not work! struct Stack s = {.top = ­1}; // or s.top = ­1 Push(&s, 'U'); Push(&s, 'F'); Push(&s, 'P'); Push(&s, 'B'); Pop(&s); Pop(&s); return 0; } Stack creation and initialization. Pointers as arguments: we need to change the Stack state! 32 Universidade Federal da Paraíba Centro de Informática

Discussion ● Considering the presented implementation: – Initialization is completely manual and prone to errors. ● How to automate it? – Theoretically, stacks have no upper limits (one should be able to keep 'pushing' infinitely!). ● How we could improve our implementation with respect to the maximum size limit? – We may want to 'stack' anything (numbers, chars, etc.). ● Do we have to implement one different stack (with push(), pop()) for each data type? Think about it !!! 33 Universidade Federal da Paraíba Centro de Informática

 User name: Comment:

## Related pages

### Semi Truck Stacks: 6-Inch Stacks | Iowa80.com

Check out Iowa80.com today and browse through our fantastic collection of semi truck stacks, including these 6-inch stacks!

League of Legends + Informação + Cenário Competitivo do LoL + Humor + Zueira = 6 Stacks Se Inscreva e fique ligado na nossa programação!

### 6" Stacks: Parts & Accessories | eBay

Find great deals on eBay for 6" Stacks in Commercial Truck Parts. Shop with confidence.

### Sport Stacking – Wikipedia

3-6-3 (Overall-Weltrekord: 1,824 s, William Orrell, USA) ... Die Matte der Firma FlashCups ist etwas dicker als die „Stack Mat“ von Speed Stacks, ...

### 6'' OD CHROME STACKS - TruckPipeStore.com

Truckpipestore Is Selling High Quality Exhaust Pipes That Is A 6 Inch Od Truck Exhaust Stack Pipes For Semi Trucks And Tractors

ALDI-Notebook: 15,6 Zoller Medion Akoya P6670 für 599 Euro ab 5. November erhält... Windows 10: Kumulatives Update KB3197954 behebt viele Fehler.

### 6" stacks | eBay

Find great deals on eBay for 6" stacks 6 exhaust stack. Shop with confidence.