© 2006 Pearson Addison-Wesley. All rights reserved 7-1Chapter 7StacksCS102 Sections 51 and 52Marc Smith and Jim Ten EyckSpring 2008© 2006 Pearson Addison-Wesley. All rights reserved 7-2The Abstract Data Type:Developing an ADT During theDesign of a Solution• Specifications of an abstract data type for aparticular problem– Can emerge during the design of the problem’s solution– Examples• readAndCorrect algorithm• displayBackward algorithm© 2006 Pearson Addison-Wesley. All rights reserved 7-3Developing an ADT During theDesign of a Solution• ADT stack operations– Create an empty stack– Determine whether a stack is empty– Add a new item to the stack– Remove from the stack the item that was added mostrecently– Remove all the items from the stack– Retrieve from the stack the item that was added mostrecently© 2006 Pearson Addison-Wesley. All rights reserved 7-4Developing an ADT During theDesign of a Solution• A stack– Last-in, first-out(LIFO) property• The last item placed onthe stack will be thefirst item removed– Analogy• A stack of dishes in acafeteriaFigure 7-1Figure 7-1Stack of cafeteria dishes© 2006 Pearson Addison-Wesley. All rights reserved 7-5Developing an ADT During theDesign of a Solution• A queue– First in, first out (FIFO) property• The first item added is the first item to be removed© 2006 Pearson Addison-Wesley. All rights reserved 7-6Refining the Definition of the ADTStack• Pseudocode for the ADT stack operationscreateStack()// Creates an empty stack.isEmpty()// Determines whether a stack is empty.push(newItem) throws StackException// Adds newItem to the top of the stack.// Throws StackException if the insertion is// not successful.© 2006 Pearson Addison-Wesley. All rights reserved 7-7Refining the Definition of the ADTStack• Pseudocode for the ADT stack operations(Continued)pop() throws StackException// Retrieves and then removes the top of the stack.// Throws StackException if the deletion is not// successful.popAll()// Removes all items from the stack.peek() throws StackException// Retrieves the top of the stack. Throws// StackException if the retrieval is notsuccessful© 2006 Pearson Addison-Wesley. All rights reserved 7-8Using the ADT Stack in aSolution• displayBackward and readAndCorrectalgorithms can be refined by using stackoperations• A program can use a stack independently of thestack’s implementation© 2006 Pearson Addison-Wesley. All rights reserved 7-9Axioms (Optional)• Axioms are used to define an ADT formally– Example• Axiom to specify that the last item inserted intostack is the first item to be removed(stack.push(newItem)).pop() = stack© 2006 Pearson Addison-Wesley. All rights reserved 7-10Simple Applications of the ADTStack: Checking for BalancedBraces• A stack can be used to verify whether a programcontains balanced braces– An example of balanced bracesabc{defg{ijk}{l{mn}}op}qr– An example of unbalanced bracesabc{def}}{ghij{kl}m© 2006 Pearson Addison-Wesley. All rights reserved 7-11Checking for Balanced Braces• Requirements for balanced braces– Each time you encounter a “}”, it matches an alreadyencountered “{”– When you reach the end of the string, you havematched each “{”© 2006 Pearson Addison-Wesley. All rights reserved 7-12Checking for Balanced BracesFigure 7-3Figure 7-3Traces of the algorithm that checks for balanced braces© 2006 Pearson Addison-Wesley. All rights reserved 7-13Checking for Balanced Braces• The exception StackException– A Java method that implements the balanced-bracesalgorithm should do one of the following• Take precautions to avoid an exception• Provide try and catch blocks to handle a possibleexception© 2006 Pearson Addison-Wesley. All rights reserved 7-14Recognizing Strings in aLanguage• Language LL = {w$w’ : w is a possible empty string of characters other than $, w’ = reverse(w) }– A stack can be used to determine whether a given stringis in L• Traverse the first half of the string, pushing each character ontoa stack• Once you reach the $, for each character in the second half ofthe string, pop a character off the stack– Match the popped character with the current character in thestring© 2006 Pearson Addison-Wesley. All rights reserved 7-15Implementations of the ADTStack• The ADT stack can be implemented using– An array– A linked list– The ADT list• StackInterface– Provides a common specification for the threeimplementations• StackException– Used by StackInterface– Extends java.lang.RuntimeException© 2006 Pearson Addison-Wesley. All rights reserved 7-16Implementations of the ADTStackFigure 7-4Figure 7-4Implementation of theADT stack that use a)an array; b) a linked list;c) an ADT list© 2006 Pearson Addison-Wesley. All rights reserved 7-17An Array-Based Implementationof the ADT Stack• StackArrayBased class– Implements StackInterface– Instances• Stacks– Private data fields• An array of Objects called items• The index topFigure 7-5Figure 7-5An array-based implementation© 2006 Pearson Addison-Wesley. All rights reserved 7-18A Reference-BasedImplementation of the ADT Stack• A reference-based implementation– Required when the stack needs to grow and shrinkdynamically• StackReferenceBased– Implements StackInterface– top is a reference to the head of a linked list of items© 2006 Pearson Addison-Wesley. All rights reserved 7-19A Reference-BasedImplementation of the ADT StackFigure 7-6Figure 7-6A reference-basedimplementation© 2006 Pearson Addison-Wesley. All rights reserved 7-20An Implementation That Uses theADT List• The ADT list can be used to represent the items ina stack• If the item in position 1 of a list represents the topof the stack– push(newItem) operation is implemented asadd(1, newItem)– pop() operation is implemented asget(1)remove(1)– peek() operation is implemented asget(1)© 2006 Pearson Addison-Wesley. All rights reserved 7-21An Implementation That Uses theADT ListFigure 7-7Figure 7-7An implementation that usesthe ADT list© 2006 Pearson Addison-Wesley. All rights reserved 7-22Comparing Implementations• All of the three implementations areultimately array based or reference based• Fixed size versus dynamic size– An array-based implementation• Uses fixed-sized arrays– Prevents the push operation from adding an item to thestack if the stack’s size limit has been reached– A reference-based implementation• Does not put a