Chapter 12: Stacks as an Abstract Data Type

Stack: A Useful List

• Stacks are a useful kind of list and an example of an Abstract Data Type (ADT).
• ADTs allow defining methods and behavior separately from any implementation.
• Multiple implementations exist, some better than others.
• Stacks can reverse a list faster but require more space, illustrating a space-time tradeoff.

Stack Overview

• Stack ADT
• Basic stack operations: pushing, popping, etc.
• Implementations of stacks using arrays and linked lists.

The Stack ADT

• A stack is a list where insertions and deletions occur only at the top.
• The opposite end is called the bottom.
• Fundamental operations:
  • Push: Adds an element to the top (equivalent to insert).
  • Pop: Removes the most recently inserted element.
  • Peek: Examines the most recently inserted element.

Linear and Non-Linear Collections

• (This section distinguishes stacks as linear collections.)

Stack - Conceptual View (Linear)

• Shows visually how elements are added to the top and removed from the top in a stack.

Stack Operations

• Collections use specific terms for operations; stack operations include:
  • push: Adds an element to the top of the stack.
  • pop: Removes an element from the top of the stack.
  • peek: Examines the element at the top of the stack.
  • isEmpty: Determines if the stack is empty.
  • size: Determines the number of elements on the stack.

Stack ADT

• Stacks are less flexible than linked lists but more efficient and easier to implement.
• Stacks are LIFO (Last In, First Out) lists, meaning the last element inserted is the first retrieved.

Push and Pop

• Primary operations: Push and Pop
  • Push: Add an element to the top of the stack.
  • Pop: Remove the element at the top of the stack.
• An empty stack is shown, elements are pushed onto it (A, then B), and then elements are popped (A).

Implementation of Stacks

• Any list implementation can be used to implement a stack:
  • Arrays: Static (size is predetermined).
  • Linked lists: Dynamic (never become full).

What can we do with stacks?

• push(anObject): Add a new object to the top of the stack.
• pop(): Remove the top object from the stack.
• peek(): Get the top object without removing it.
• size(): Return the size of the stack.

Implementing a stack with a linked list

• LinkedListStack.java (Indicates a Java implementation using a linked list).

Example Stack

• Example stack operations:
  • stack.push("This")
  • stack.push("is")
  • stack.push("a")
  • stack.push("test")
  • stack.size() returns 4
  • stack.peek() returns "test"
  • stack.pop() returns "test"
  • Subsequent pops return "a", "is", "This"
  • Another stack.pop() results in java.util.NoSuchElementException.
• Demonstrates LIFO order.

Tips

• Stacks can be implemented by linked lists or arrays.
• Use the Stack class in Java.util.
• Suggests searching "java Stack" for more information.

Applications

• Text studies two client programs using stacks:
  • Palindrome finder
  • Parentheses matcher
• A Palindrome is a string that reads the same in either direction (e.g., "madam", "deed", "rotator", "level", "radar").

Applications (continued)

• When analyzing arithmetic expressions, it's vital to ensure parentheses are balanced:
  • Example: (a+b*(c/(d-e)))+(d/e)
• The problem becomes complex with braces or brackets.
• Stacks provide a solution to this problem.