展开查看详情
2 .Abstract Stack An Abstract Stack (Stack ADT) is an abstract data type which emphasizes specific operations: Uses a explicit linear ordering Insertions and removals are performed individually Inserted objects are pushed onto the stack The top of the stack is the most recently object pushed onto the stack When an object is popped from the stack, the current top is erased 3.2.1
3 .Abstract Stack Also called a last-in–first-out (LIFO) behaviour Graphically, we may view these operations as follows: There are two exceptions associated with abstract stacks: It is an undefined operation to call either pop or top on an empty stack 3.2.1
4 .Applications Numerous applications: Parsing code: Matching parenthesis XML (e.g., XHTML) Tracking function calls Dealing with undo/redo operations Reverse-Polish calculators Assembly language The stack is a very simple data structure Given any problem, if it is possible to use a stack, this significantly simplifies the solution 3.2.2
5 .Implementations We will look at two implementations of stacks: The optimal asymptotic run time of any algorithm is Q (1) The run time of the algorithm is independent of the number of objects being stored in the container We will always attempt to achieve this lower bound We will look at Singly linked lists One-ended arrays 3.2.3
6 .Linked-List Implementation Operations at the front of a singly linked list are all Q (1) The desired behaviour of an Abstract Stack may be reproduced by performing all operations at the front Front/ 1 st Back/ n th Find Q (1) Q (1) Insert Q (1) Q (1) Erase Q (1) Q ( n ) 3.2.3.1
7 .Pop Removing an object simply involves reducing the size It is invalid to assign the last entry to “0” By decreasing the size, the previous top of the stack is now at the location stack_size pop() { if ( empty () ) { throw underflow(); } -- stack_size ; return array [ stack_size ]; } 3.2.3.2
8 .Push Pushing an object onto the stack can only be performed if the array is not full push( Type const & obj ) { if ( stack_size == array_capacity ) { throw overflow(); // Best solution????? } array [ stack_size ] = obj ; ++ stack_size ; } 3.2.3.2
9 .Exceptions The case where the array is full is not an exception defined in the Abstract Stack If the array is filled, we have five options: Increase the size of the array Throw an exception Ignore the element being pushed Replace the current top of the stack Put the pushing process to “sleep” until something else removes the top of the stack 3.2.3.2
10 .Function Calls This next example discusses function calls See how stacks are implemented in hardware on all CPUs to facilitate function calling The simple features of a stack indicate why almost all programming languages are based on function calls 3.2.5.3
11 .Function Calls Function calls are similar to problem solving presented earlier: you write a function to solve a problem the function may require sub-problems to be solved, hence, it may call another function once a function is finished, it returns to the function which called it 3.2.5.3
12 .Function Calls You will notice that the when a function returns, execution and the return value is passed back to the last function which was called This is again, the last-in—first-out property Today’s CPUs have hardware specifically designed to facilitate function calling 3.2.5.3
13 .References Donald E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms , 3 rd Ed., Addison Wesley, 1997, §2.2.1, p.238. Cormen , Leiserson , and Rivest , Introduction to Algorithms , McGraw Hill, 1990, §11.1, p.200. Weiss, Data Structures and Algorithm Analysis in C++ , 3 rd Ed., Addison Wesley, §3.6, p.94. Wikipedia, http://en.wikipedia.org/wiki/Stack_(abstract_data_type) Slides from: “These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.” from U of Waterloo
热门城市
