基本数据结构StacksQueuesListsTrees.ppt

基本数据结构StacksQueuesListsTrees Elementary Data Structures2The Stack ADT (§2.1.1)The Stack ADT stores arbitrary objectsInsertions and deletions follow the last-in first-out schemeThink of a spring-loaded plate dispenserMain stack operations:push(object): inserts an elementobject pop(): removes and returns the last inserted elementAuxiliary stack operations:object top(): returns the last inserted element without removing itinteger size(): returns the number of elements storedboolean isEmpty(): indicates whether no elements are stored Elementary Data Structures3Applications of StacksDirect applicationsvisited history in a Web browserUndo sequence in a text editorChain of method calls in the Java Virtual Machine or C++ runtime environmentIndirect applicationsAuxiliary data structure for algorithmsComponent of other data structures Elementary Data Structures4Array-based Stack (§2.1.1)A simple way of implementing the Stack ADT uses an arrayWe add elements from left to rightA variable t keeps track of the index of the top element (size is t+1)S012t…Algorithm pop(): if isEmpty() then throw EmptyStackException else t ? t ? 1 return S[t + 1]Algorithm push(o) if t = S.length ? 1 then throw FullStackException else t ? t + 1 S[t] ? o Elementary Data Structures5Growable Array-based Stack (§1.5)In a push operation, when the array is full, instead of throwing an exception, we can replace the array with a larger oneHow large should the new array be?incremental strategy: increase the size by a constant cdoubling strategy: double the sizeAlgorithm push(o) if t = S.length ? 1 then A ? new array of size … for i ? 0 to t do A[i] ? S[i] S ? A t ? t + 1 S[t] ? o Elementary Data Structures6Comparison of the StrategiesWe compare the incremental strategy and the doubling strategy by analyzing the total time T(n) needed to perform a series of n push operationsWe assume that we start with an empty stack represented by an array of size 1We call amortized time of a push oper