Lecture Data structures and algorithms in Java (6th edition): Chapter 6(continue) - Goodrich, Tamassia, Goldwasser

This chapter provides knowledge of stacks. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Stacks 3/16/14 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Stacks © 2014 Goodrich, Tamassia, Goldwasser Stacks 1 Abstract Data Types (ADTs) q   q   An abstract data type (ADT) is an abstraction of a data structure An ADT specifies: n   n   n   Data stored Operations on the data Error conditions associated with operations © 2014 Goodrich, Tamassia, Goldwasser q   Example: ADT modeling a simple stock trading system n   n   The data stored are buy/sell orders The operations supported are w   order buy(stock, shares, price) w   order sell(stock, shares, price) w   void cancel(order) n   Error conditions: w   Buy/sell a nonexistent stock w   Cancel a nonexistent order Stacks 2 1 Stacks 3/16/14 The Stack ADT q   q   q   q   The Stack ADT stores arbitrary objects Insertions and deletions follow the last-in first-out scheme Think of a spring-loaded plate dispenser Main stack operations: n   n   q   n   n   n   push(object): inserts an element object pop(): removes and returns the last inserted element © 2014 Goodrich, Tamassia, Goldwasser Auxiliary stack operations: object top(): returns the last inserted element without removing it integer size(): returns the number of elements stored boolean isEmpty(): indicates whether no elements are stored Stacks 3 Stack Interface in Java q   q   q   Java interface corresponding to our Stack ADT Assumes null is returned from top() and pop() when stack is empty Different from the built-in Java class © 2014 Goodrich, Tamassia, Goldwasser public interface Stack { int size(); boolean isEmpty(); E top(); void push(E element); E pop(); } Stacks 4 2 Stacks 3/16/14 Example © 2014 Goodrich, Tamassia, Goldwasser Stacks 5 Exceptions vs. Returning Null q   q   q   Attempting the execution of an operation of an ADT may sometimes cause an error condition Java .