Download Presentation
## Stacks

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**Stacks**Chapter 5**Chapter Objectives**• To learn about the stack data type and how to use its four methods: push, pop, peek, and empty • To understand how Java implements a stack • To learn how to implement a stack using an underlying array or a linked list • To see how to use a stack to perform various applications, including finding palindromes, testing for balanced (properly nested) parentheses, and evaluating arithmetic expressions Azzam Mourad**Stack Abstract Data Type**• A stack can be compared to a Pez dispenser • Only the top item can be accessed • Can only extract one item at a time • A stack is a data structure with the property that only the top element of the stack is accessible • The stack’s storage policy is Last-In, First-Out Azzam Mourad**Specification of the Stack Abstract Data Type**• Only the top element of a stack is visible, therefore the number of operations performed by a stack are few • Need the ability to • Inspect the top element • Retrieve the top element • Push a new element on the stack • Test for an empty stack Azzam Mourad**Specification of the Stack Abstract Data Type (continued)**Azzam Mourad**Stack Applications**• Two client programs using stacks • Palindrome finder • Parentheses matcher • Palindrome: string that reads the same in either direction • Example: “Able was I ere I saw Elba” Azzam Mourad**Stack Applications (continued)**Exp. Page 263 p. 153 new version Azzam Mourad**Stack Applications (continued)**• When analyzing arithmetic expressions, it is important to determine whether an expression is balanced with respect to parentheses • (a+b*(c/(d-e)))+(d/e) • Problem is further complicated if braces or brackets are used in conjunction with parenthesis • Solution is to use stacks! Azzam Mourad**Stack Applications (continued)**Azzam Mourad**Stack Applications (continued)**Exp. Page 267-268 p. 157-160 (new version) Azzam Mourad**Additional Stack Applications**• Consider two case studies that relate to evaluating arithmetic expressions • Postfix and infix notation • Expressions normally written in infix form • Binary operators inserted between their operands • A computer normally scans an expression string in the order that it is input; easier to evaluate an expression in postfix form Azzam Mourad**Additional Stack Applications (continued)**Azzam Mourad**Additional Stack Applications (continued)**• Advantage of postfix form is that there is no need to group subexpressions in parentheses • No need to consider operator precedence Azzam Mourad**Evaluating Postfix Expressions**Azzam Mourad**Evaluating Postfix Expressions (continued)**Azzam Mourad**Evaluating Postfix Expressions (continued)**Stop here Exp. Page 281-283 p. 172-175 (new version) Azzam Mourad**Chapter Review**• A stack is a last-in, first-out (LIFO) data structure • A stack is a simple but powerful data structure; its four operations include empty, peek, pop, and push • Stacks are useful to process information in the reverse of the order that it is encountered • Java.util.Stack is implemented as an extension of the Vector class Azzam Mourad**Chapter Review (continued)**• Three ways to implement a stack: • Using an object of a class that implements the List interface as a container • Using an array as a container • Using a linked list as a container • Stacks can be applied in programs for evaluating arithmetic expressions Azzam Mourad