6 stacks

38 %
62 %
Information about 6 stacks

Published on October 1, 2014

Author: emersonferr

Source: slideshare.net

Description

Slide da cadeira de Estrutura de Dados, ministrado pelo Prof. Dr. Christian Pagot, na Universidade Federal da Paraíba.

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

Add a 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!
Read more

6 Stacks - YouTube

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

Download BlueStacks Offline Installer

Thanks for downloading BlueStacks. This is the Offline Installer for BlueStacks. Play Bigger.
Read more

6" Stacks: Parts & Accessories | eBay

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

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, ...
Read more

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
Read more

Bluestacks App Player Download – GIGA

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.
Read more

6" stacks | eBay

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

BlueStacks App Player - Download - CHIP

BlueStacks App Player 2.5.70 Deutsch: Mit dem kostenlosen "BlueStacks App Player" nutzen Sie Android-Apps nun ganz einfach auf Ihrem Windows-PC.
Read more

Bluestacks - Play and Stream Any Android Game and App on PC

BlueStacks Editor's Choice. Every week we pick our favorite Android apps that look and play beautifully on your PC. Download BlueStacks
Read more