南开大学数据结构.pdf

我笃定一生砥砺奋进的担当， 就算不谙世事，也有光芒。 开讲啦! The Third Course Stack Queue Stacks LIFO: Last In, First Out Restricted form of list  Insert and remove only at front of list A stack is a data structure in which all insertions and deletions of entries are made at one end, called the top of the stack. Stacks The last entry which is inserted is the first one that will be removed. Notation: Insert: PUSH Remove: POP The accessible element is called TOP DEFINITION  DEFINITION: A stack of elements of type T is a finite sequence of elements of T , together with the following operations: Create the stack, leaving it empty. Test whether the stack is Empty. Push a new entry onto the top of the stack, provided the stack is not full. Pop the entry off the top of the stack, provided the stack is not empty. Retrieve the Top entry from the stack, provided the stack is not empty. Specification for Methods  Error_code Stack ::pop( ); Pre: None. Post: If the Stack is not empty, the top of the Stack is removed. If the Stack is empty, an Error_code of underflow is returned and the Stack is left unchanged.  Error_code Stack ::push(const Stack entry item); Pre: None. Post: If the Stack is not full, item is added to the top of the Stack. If the Stack is full, an Error_code of overflow is returned and the Stack is left unchanged. Specification for Methods  Error_code Stack ::top(Stack entry item) const; Pre: None. Post: The top of a nonempty Stack is copied to item. A code of fail is returned if the Stack is empty.  bool Stack ::empty( ) const; Pre: None. Post: A result of true is returned if the Stack is empty, otherwise false is returned. 入栈