29 Pages
Unlock Document

Information Technology
All Professors

Abstract Data Type ADTSTACKSA stack is a linear data structure that is always accessed from the same extremity one element at a time and that element is called the top of the stackBasic operationsThe basic operation of a stack arePush add an element onto the top of the stackPop remove and returns the top elementEmpty tests if the stack is emptypublic interface StackE public abstract Boolean isEmptypublic abstract E pushE opublic abstract E popreturns the object at the top of this stack without removing itpublic abstract E peekHow would you implement this interfaceThere are two popular families of implementation techniquesArraybasedUsing linkednodesStack Token ss new ArrayStackTokens new DynamicArrayStackTokens new LinkedStackTokenImplementing a Stack using an array ArrayStackThe element of this stack are stored in the low part of the array the bottom element is always located at the position 0 convention an instance variable is used to indicate the position of the top element in the arrayEach time an element is pushed onto the stack the value of the index top is incremented by one the new element is added at that position Each time an element is removed from the stack the reference of the top element is stored in a temporary variable the position of the array designated by top is set to null the index is decremented by one the element saved is returned This is the preferred solution It avoids copying the elements up or down for each insertion or removal Copying elements would become progressively more expensive as the number of elements in the stack public Boolean isEmpty return top0public void push E element precondition the stack is not fullstores the element at position top then increments topElemstopelementpublic E peek preconditionsisEmptyReturn elemstop1public E pop preconditionsisEmpty decrements top then access the valueE savedelemtopelemstopnull scrubing the memoryReturn savedImplementing a Stack using an arrayThe current implementation has a major limitation its size is fixed Often the number of elements to process is not known in advance How would you circumvent this limitationAllocate an array that will be sufficiently large for the most applications What are the disadvantages of this approach Most of the time most of the allocated memory will not be used the capacity can be exceededSolution Dynamic arrayImplementing a stack using an array Dynamic arrayWhen the array is full a new bigger array is created the elements from the current array are moved copied into the new one finally the new array replaces the current oneThere are many strategies to increase the size of the array two of them are Let n and n be the size of the current and new array respectively nnc where c1 for instance or ncn where c2 Abstract Data Type ADTSTACKS Stackbased algorithmsInfixpostfix mentallySuccessively transform one by one all the subexpressions following the same order of evaluation that would normally follow to evaluate an infix expressionAn infix expression lr becomes lr where l and r are subexpressions andis an operator9 2 x 45 9 2 4 x5 92 4 x 59 2 4 x 5
More Less

Related notes for ITI1521

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.