TAILIEUCHUNG - 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 .
đang nạp các trang xem trước
