[DATA STRUCTURE & Other Objects Using JAVA] Chapter 6 Stacks

6.1 Introduction to Stacks

  • Stack is sometimes called a push down store.
  • A stack is a data structure of ordered items such that items can be inserted and removed only at one end.
  • Stack items must be removed in the reverse order of that in which they are placed on the stack.
  • LIFO: Last-in/first-out
  • Only the top item is accessible.
  • Adding an item to a stack is called a push operation and removing an item form a stack is called a pop operation.

6.1.1 The Stack Class — Specification

  • Ge the top item of this stack without removing the item.

  • Stack underflow: If a program attempts to pop an item off an empty stack, it is asking for the impossible; this error is called stack underflow, which will throw an EmptyStackException.

6.1.2 Programming Example: Reversing a Word

  • Stack is surprisingly useful:

    • Most compilers use stacks to analyze the syntax of a program.
    • Stacks are used to keep track of local variables when a program is run.
    • Stacks can be used to search a maze or a family tree or other types of breaching structures.

6.2 Stack Application

6.2.1 Programming Example: Balanced Parenthesis

  • Every time a left parenthesis occurs, it is pushed onto the stack.
  • Every time a right parenthesis occurs, a matching left parenthesis is popped off the stack.
  • If all goes smoothly and the stack is empty at the end of the expression, then the parenthesis match.

6.2.2 Evaluation Arithmetic Expression

Evaluation Arithmetic Expression — Design

(((6 + 9) / 3) * (6 – 4))

  • Evaluate the leftmost of the innermost expression repeatedly
  • The end of the expression to be evaluated is always a right parenthesis ‘)’, and moreover it is always the first right parenthesis.
  • The next right parenthesis will indicate the end of the next expression to be evaluated.
  • Whenever we reach a right parenthesis, we combine the top two numbers (on the number stack) using the topmost operation (on the character stack).

Something About Java Scanner

  • The expression input.hasNext(UNSIGNED_DOUBLE) is true if the next part of the input expresso is a double number.
  • The expression next = input.findInLine(UNSIGNED_DOUBLE) sets the stringnext equal to the next part of the input expression, which must a double number.
  • The expression next = input.findInLine(CHARACTER) sets next equal to the next single character (skipping spaces) in the input expression.

Evaluation Arithmetic Expression — Implementation

Evaluation Arithmetic Expression — Testing and Analysis

The algorithm for the program is O(n).

Evaluation Arithmetic Expression — Enhancements

  • Permit expression that are not fully parenthesized
  • Use the Java precedence rules to decide the order of operations when parentheses are missing

6.3 Implementations of the Stack ADT

6.3.1 Array Implementation of a Stack

Invariant of the ArrayStack Class

  1. The number of items in the stack is stored in the instance variable manyItems.
  2. The items in the stack are stored in a partially filled array called data, with the bottom of the stack at data[0], the next item at data[1], and so on, to the top of the stack at data[manyItems-1].

Specification

6.3.2 Linked List Implementation of a Stack

Invariant

  1. The items in the stack are stored in a linked list, who the top of the stack stored at the head node, down to the bottom of the stack at the final node.
  2. The instance variable top is the head reference of the linked list of items.
  3. Because we are using a linked list, there are no capacity worries.

Specification

Since we are using linked list here, we do not need method to maintain correct size.

6.4 More Complex Stack Applications

6.4.1 Evaluating Postfix Expressions

  • Infix Notation: 2 + 3
  • Prefix Notation (Polish Prefix Notation): * + 2 3 7 = (2 + 3) * 7
  • Postfix Notation (Polish Postfix Notation) (Reverse Polish Notation): Write the operations after the two numbers being combines. 2 3 + 7 *
  • In Reverse Polish Notation, an operation is applied to the two numbers that are immediately before it. 7 3 5 * + 4 = 7 + (3 * 5)
  • Do not intermix prefix and postfix notation.
  • Postfix notation is handy because it does not require parentheses and because it is particularly easy to evaluate.
  • Each operation is used as soon as it is read.
  • Each time an operation appears in the input, the operands for the operation are the two most recently seen numbers.
  • Sometimes the “most recently seen number” is not actually an input number; instead, it is a number that we computed and pushed back onto the stack.
  • When the input is exhausted, the number remaining in the stack is the value of the entire expression.

6.4.2 Translating Infix to Postfix Notation

  • One strategy for evaluating an ordinary infix expression is to first convert it to postfix notation and then evaluate the postfix expression.
  • If the infix expression is fully parenthesized, all that’s needed to convert from infix to postfix is to move each operation symbol to the location of the right parenthesis corresponding to that operation and then remove all parenthesis.
  • The operands in the equivalent postfix expression are in the same order as the operands in the corresponding infix expression we start out with.

6.4.3 Using Precedence Rules in the Infix Expression

  • In practice, infix expressions are usually not fully parenthesized, and the computer must rely on precedence rules to determine the order of operations for the missing parentheses.
  • Operations of equal precedence are performed in left-to-right order.