Đang chuẩn bị liên kết để tải về tài liệu:
Stacks & Queues

Không đóng trình duyệt đến khi xuất hiện nút TẢI XUỐNG Tải xuống

Stacks & Queues Abstract Data Types (ADTs), The Stack ADT, Applications of Stacks, C++ Run-time Stack main, Array-based Stack, Performance and Limitations, Growable Array-based Stack, Comparison of the Strategies. | Stacks & Queues Acknowledgement: These slides are adapted from slides provided with Data Structures and Algorithms in C++, Goodrich, Tamassia and Mount (Wiley 2004) Nguyen Viet Anh CS3329 –Spring 2011 2 Abstract Data Types (ADTs) An abstract data type (ADT) is an abstraction of a data structure An ADT specifies: Data stored Operations on the data Error conditions associated with operations Example: ADT modeling a simple stock trading system The data stored are buy/sell orders The operations supported are order buy(stock, shares, price) order sell(stock, shares, price) void cancel(order) Error conditions: Buy/sell a nonexistent stock Cancel a nonexistent order 3 The Stack ADT The Stack ADT stores arbitrary objects Insertions and deletions follow the last-in first-out (LIFO) scheme Think of a spring-loaded plate dispenser Main stack operations: push(Object o): inserts element o pop(): removes and returns the last inserted element Auxiliary stack operations: top(): returns the last inserted element without removing it size(): returns the number of elements stored isEmpty(): a Boolean value indicating whether no elements are stored 4 Exceptions Attempting the execution In the Stack ADT, of an operation of ADT operations pop and top may sometimes cause an cannot be performed if error condition, called an the stack is empty exception Attempting the Exceptions are said to be execution of pop or top “thrown” by an operation on an empty stack that cannot be executed throws .