CSC 1052 STACKS 10/3/2015 1 Outline Stacks Basic operations Examples of use Queues Basic operations Examples of use Implementations Array-based and linked list-based 10/3/2015 2 Static vs. Dynamic Structures Recall that a static data structure has a fixed size Arrays are static; once you define the number of elements it can hold, it doesn’t change. 3 Objects A dynamic data structure grows and shrinks as required by the information it contains. We have examined a data structure where two objects can be instantiated and chained together The next reference of one Node object refers to the other node. This will create a linked list of Node objects. 10/3/2015 4 Stacks A stack ADT is also linear, like a list or queue, It maintains its information in a straight line. Items are added and removed from only one end of a stack. It is therefore LIFO: Last-In, First-Out. 5 Stacks Stacks are often drawn vertically: PUSH POP add remove 6 A conceptual view of a stack 10/3/2015 7 Stacks Some stack operations: - push -add an item to the top of the stack. - pop - remove an item from the top of the stack. - peek - retrieves top item without removing it. - empty - returns true if the stack is empty. 8 Stacks A stack is a structure of ordered items such that items can be inserted and removed only at one end - called the top. A stack is a LIFO or Last-in/First-Out structure. Items are taken out of the stack in reverse order from their insertion. 10/3/2015 9 Non-Computer Examples Stack of papers Stack of bills Stack of plates Expect O ( 1 ) time per stack operation. (In other words, constant time per operation, no matter how many items are actually in the stack). 10/3/2015 10 Stack The stack specification lists a stack constructor and five methods. One of the simplest stack implementations is to reverse a word. Most compilers use stacks to analyze the syntax of a program. 10/3/2015 11 Input NAT Push N N Pop T Push A Push TUsing a Stack to reverse a word N T A N Pop A POP N A Output TAN A N N 10/3/2015 12 STACKS applications At all times in the execution of the reverse word program, Only item can accessed from the stack, This is the item on the TOP. 10/3/2015 13 Peek() We will use a method called peek() to view the top item It looks at the top item but does not remove it. Stacks are also used frequently to evaluate expressions 10/3/2015 14 Applications – Evaluate expressions Stacks can be used to check a program for balanced symbols (such as {}, (), []). Example: {()} is legal, {(}) is not (so simply counting symbols does not work). 10/3/2015 15 Evaluate expressions When a closing symbol is seen, it must match the most recently seen unclosed opening symbol. Therefore, a stack will be appropriate. 10/3/2015 16 Balanced Symbol Algorithm Make an empty stack. Repeatedly read tokens(parenthesis); if the token is: an opening symbol, push it onto the stack If it is a closing symbol and the stack is empty, then report an error; otherwise pop the stack and determine if the popped symbol is a match (if not report an error) At the end of the file, if the stack is not empty, report an error. 10/3/2015 17 Example Input: { ( ) } Push { Push ( stack now has { ( ( { Pop - Next comes a ) , pop an item, it is ( which matches ). Stack now has { { Pop – Next comes a } , pop an item, it is { which matches }. End of file; stack is empty, so all is good. 10/3/2015 18 Input: ( { } { } ) Empty Stack Read and Push ( Read Read first and } , pop Push { matching { ( Read ) and Pop ( { { ( Read and Push 2nd { Read 2nd }, pop matching { ( ( ( 10/3/2015 19 Input: [ { } { } ]{} Initial Empty Stack Read and Push [ Read and Push { Read first }, pop matching { { [ 1 [ 3 2 Read and Push 2nd { [ 4 Read 2nd }, pop matching { { [ [ 5 6 And so on.. 10/3/2015 20 Performance Running time is O( N ), where N is amount of data (that is, number of tokens). Algorithm is online: it processes the input sequentially, never needing to backtrack. 10/3/2015 21 Balancing an expression In the method IsBalanced(String exp) an expression is checked to see if all the parentheses match. A charStack is set up whose legal characters are: “() {} [} “ A switch is used 10/3/2015 22 Method Stack Matching symbols is similar to method call and method return, because when a method returns, it returns to the most recently active method. A method stack can be used to keep track of this. 10/3/2015 23 Method call and return Abstract idea: when a method call is made, save current state of the method on a stack. On return, restore the state by popping the stack. 10/3/2015 24 Stack Frames or Activation Records Programs compiled from modern high level languages make use of a stack frame for the working memory of each method invocation. When any method is called, a number of words - the stack frame - is pushed onto a program stack. When the method returns, this frame of data is popped off the stack. 10/3/2015 25 Stack frame or Activation Record The Stack Frame or Record contains the : Method arguments Return address And local variables of the method to be stored 10/3/2015 26 method f( int x, int y) { int a; if ( end_cond ) return …; a = ….; return g( a ); } method g( int p, p = …. return } int z ) { q; ; q = …. ; f(p,q); Context for execution of f: Each frame contains : parameters, return address and local variables 10/3/2015 27 Activation Records As a method calls another method, first its arguments, then the return address and finally space for local variables is pushed onto the stack. 10/3/2015 28 current method environment. The top of stack stores the current method environment. When the method is called, the new environment(parameters etc.) is pushed onto stack. When the method ends and returns, the old environment is restored by popping the method environment. 10/3/2015 29 Stack Frames Since each function runs in its own "environment" or context, it becomes possible for a function to call itself - a technique known as recursion. This capability is extremely useful and extensively used - because many problems are elegantly specified or solved in a recursive way. 10/3/2015 30 Stack Frames The most common applications for stacks have a space restraint so that using an array implementation for a Stack is a natural and efficient one. In most operating systems, allocation and de-allocation of memory costs time and space , e.g. there is a penalty for the flexibility of linked list implementations.. 10/3/2015 31 Array Implementations Stacks can be implemented with an array and an integer top that stores the array index of the top of the stack. Empty stack has top equal to -1. 10/3/2015 32 Operations of a Stack To push an object on the stack , increment the top counter, and write in the array position. To pop an item from the stack: decrement the top counter. 10/3/2015 33 Stages B top(-1) A top(0) top(1) A 10/3/2015 34 Array Doubling If stack is full (because array size has been reached), we can extend the array, using array doubling. We allocate a new, double-sized array and copy contents over: array =[T] new Object[ OldArray.length * 2 ]; for( int j = 0; j < OldArray.length; j++ ) Array[ j ] = OldArray[ j ]; OldArray = array; 10/3/2015 35 Running Time Without array doubling, all operations are constant time, and They do not depend on number of items in the stack. With array doubling, A push could occasionally be O( N ). 10/3/2015 36 Big O of Stack However, if the array doubling occurs infrequently, it is essentially O( 1 ) because each array doubling that costs N assignments is preceded by N/2 non-doubling pushes. 10/3/2015 37 EXPRESSION EVALUATION 10/3/2015 38 Infix Expressions Example: 1 + 2 * ( 3 + 4 ) Operands appear both before and after operator. When there are several operators, precedence and associativity determine how operators are processed. 10/3/2015 39 Precedence and Associativity Precedence: used to decide which of two operators should be processed. Associativity: used to decide which of two operators should be processed when both operators have the same precedence. Exponentiation: Right to Left Multiplication/Division: Left to Right Addition/Subtraction: Left to Right 10/3/2015 40 Examples 4-4-4 evaluates to -4 2^2^3 evaluates to 256 Parenthesis override precedence and associativity. 10/3/2015 41 Evaluating Infix expressions In developing an application to use a stack to evaluate an infix expression, several items must be considered. 10/3/2015 42 A fully parenthized expression can be evaluated using the Stack data structure. The implementation is complicated because of necessity for two stacks: 1. Operator stack to store unprocessed operators. 2. Operand stack to store unprocessed operands The time analysis is: 2n reads/peeks + n operations + 3n pushed + 3n popped = 9n 10/3/2015 43 Difficulty of Infix Evaluation Infix evaluation is difficult because of precedence rules: when an operator is seen, it may or may not need to be deferred. if it has a lower precedence than an operator further along in the expression. Even if operator needs to be used, the second operand has still not been processed. 1+2*… 10/3/2015 44 Postfix Expressions An alternate form is the postfix expression Let's examine a program that uses a stack to evaluate postfix expressions In a postfix expression, the operator comes after its two operands 10/3/2015 45 Infix to Postfix We generally use infix notation, with parentheses to force precedence: (3 + 4) * 2 In postfix notation, this would be written 3 4 + 2 * In postfix, when you come to an operator, you already have it operands 10/3/2015 46 Postfix Example – Let’s solve it 123*+ Push 1, Push 2, Push 3. When * is seen, Pop 3, Pop 2, evaluate 2 * 3, and Push the result 6. When + is seen, Pop 6, Pop 1, evaluate 1 + 6, and Push the result 7. At end of expression, stack should have one item, which is the answer. 10/3/2015 47 To evaluate a postfix expression: scan from left to right, determining if the next token is an operator or operand if it is an operand, push it on the stack if it is an operator, pop the stack twice to get the two operands, perform the operation, and push the result onto the stack At the end, only the answer will be on the stack 10/3/2015 48 Postfix Example, Continued WHEN YOU THE FIRST OPERATOR IS MET, -- THE *, The following operations will store the expression on POP THE 3 AND THE 2 , MULTIPLY THEM the stack. As an operator is encountered the operators areAND popped appropriate operation STOREand THEthe PRODUCT - 6 – ON THE STACKperformed. 123*+ 1 Push 1 3 2 1 2 1 Push 2 Push 3 When the last operator (+) is met, pop 6 and 1 and add them, and push the result on the stack 6 1 7 Pop 3 Pop 6 Pop 2 Pop 1 Push 6 Push 7 10/3/2015 49 OLD COMPILERS translated infix expressions using two stacks into machine language. AN OPERATOR IS PLACED BETWEEN ITS OPERANDS c – d + (e * f – g * h) / i INFIX MACHINE LANGUAGE THIS GETS MESSY BECAUSE OF PARENTHESES AND NEED FOR TWO STACKS NEWER COMPILERS: INFIX POSTFIX MACHINE LANGUAGE IN POSTFIX NOTATION, AN OPERATOR IS PLACED IMMEDIATELY AFTER ITS OPERANDS. INFIX a+b POSTFIX ab+ a+b*c abc*+ a*b+c ab*c+ (a + b) * c ab+c* PARENTHESES NOT NEEDED – AND NOT USED – IN POSTFIX 10/3/2015 51 Infix to Postfix Conversion By converting infix expressions to postfix, an expression can be easily evaluated. This computer first changes infix to postfix and theN solves the postfix expression 10/3/2015 52 Infix to Postfix The basic algorithm is operator precedence parsing. When an operand is seen, it is immediately output. Below we write out the 1 What happens when an + operator is seen? 1 + 2 * ( 3 + 4 ) 10/3/2015 53 Infix to Postfix Conversion When an operator is seen, it can never be output immediately, because the second operand has not been seen yet. The operator must be saved, and eventually output. A stack is used to store operators that have been seen but not yet output. 10/3/2015 54 Operator Stack In an expression such as : infix expression - 1 + 2 * 3 ^ 4 + 5 postfix expression - 1 2 3 4 ^ * + 5 +. Infix expression - 1*2+3^4+5 postfix expression - 1 2 * 3 4 ^ + 5 +. In both cases, when the second operator is about to be processed, we have output 1 and 2, and there is one operand on the stack. 10/3/2015 55 Exiting the Operator Stack The question is: How do operators exit the stack? An operator exits the stack if the precedence and associativity rules indicate that it should be processed instead of the current operator. 10/3/2015 56 Precedence Rules Basic rule: If the current operator has a lower precedence than the operator on the top of the stack, then the top of stack operator exits the stack. 10/3/2015 57 Equal precedence Associativity rules decide what to do if current operator has same precedence as operator on the top of stack. If operators are left associative, stack operator is popped 4-4-4 = 4 4 - 4 – If operators are right associative, stack operator is not popped. 2^2^3 = 2 2 3 ^ ^ 10/3/2015 58 LET’S CONVERT AN INFIX STRING TO A POSTFIX STRING. x–y*z 10/3/2015 59 INFIX POSTFIX x–y*z x We write out the x to postfix and move to the operator - 10/3/2015 60 INFIX POSTFIX x–y*z x We do not yet have the operands for the “-” SO ‘-’ MUST BE TEMPORARILY SAVED SOMEWHERE. 10/3/2015 61 INFIX POSTFIX x–y*z xy We put ‘-’ on the stack and write the Y to postfix 10/3/2015 62 INFIX POSTFIX x–y*z xy * THE OPERANDS FOR ‘*’ ARE NOT YET IN POSTFIX, SO ‘*’ MUST BE TEMPORARILY saved on the stack , AND ‘*’ has a higher precedence than ‘-’., so it is pushed on the stack. 10/3/2015 63 Exiting the Stack The rule is that the an operator: does not exit the stack * - Unless it has a higher precedence than the operator being considered The minus sign has lower precedence than the * 10/3/2015 64 INFIX POSTFIX x–y*z xyz INFIX x–y*z * - POSTFIX xyz* – We Come to the end of the infix expression and so pop all the operators. 10/3/2015 65 INFIX POSTFIX x–y*z xyz* – 10/3/2015 66 THE TEMPORARY STORAGE FACILITY IS A STACK. FOR EACH OPERATOR IN THE INFIX EXPRESSION: LOOP UNTIL an OPERATOR IS TO BE PUSHED: IF OPERATOR STACK IS EMPTY, PUSH OPERATOR ON THE STACK ELSE IF INFIX OPERATOR HAS GREATER PRECEDENCE THAN TOP OPERATOR ON STACK, PUSH THE INFIX OPERATOR ON THE STACK ELSE POP OPERATOR ON STACK AND APPEND TO POSTFIX EXPRESION 10/3/2015 67 Infix expression - 1 * 2 + 3 ^ 4 + 5 postfix expression - 1 2 * 3 4 ^ + 5 +. 1. Write the 1 to output 2. Put * on the stack 3. Write the 2 to output 4. The + has lower precedence to the *, so pop the * , write it out and put the + on the stack 2. * 4. 5. + Write out the 3 and put the ^ on the stack 6. Write out the 4, the + has lowest precedence so pop ^ and the + (associativity) and push the + on the stack 7. Write out the 5, no more input so pop stack Output: 1 2 * 3 4 ^ + 5 + 10/3/2015 5. ^ + 6. + 68 WHAT ABOUT PARENTHESES? LEFT PARENTHESIS: HAS LOWEST PRECEDENCE SO PUSH ON THE STACK RIGHT PARENTHESIS: POP ALL OPERATORS AND APPEND THEM TO POSTFIX UNTIL THE ‘(‘ IS MET. DISCARD ‘(‘ 10/3/2015 69 STACK APPLICATION CONVERTING FROM INFIX TO POSTFIX 10/3/2015 70 Multiple Stack Exits In expression such as 1+2*3^4+5, with postfix equivalent: 1234^*+5+ when second + is seen, ^ * + are all popped. Thus, several exits can occur on one symbol. 10/3/2015 71 Infix to Postfix Example Infix: 1 – 2 ^ 3 ^ 3 - ( 4 + 5 * 6 ) * 7 Postfix: 1 2 3 3 ^ ^ - 4 5 6 * + 7 * 1 1 ^ 3 ^ 3 * + ( * 2 - 2 ^^- ( ( * + ( 6 6 *+ ) ^ ^ ^ 3 3 ^ ^ ^ ( 4 4 + ( + + ( 5 5 * * * 7 7 *- 10/3/2015 72 Parentheses The Left parenthesis is the higher precedence operator when it is an input symbol (meaning that it is always pushed on the stack). Left parenthesis is a lower precedence operator when it is on the stack. Only a right parenthesis can pop it Right parenthesis pops the stack until a left parenthesis is met and then pops the left parens Operators are written to output, but parenthesis are discarded. 10/3/2015 73 Algorithm Summary infix - postfix Operands: Immediately output. Left parenthesis: push on the stack Right parenthesis: Pop stack symbols until an open parenthesis is seen. Pop and discard left parens. Operator: Pop all stack symbols until (1) Stack is empty (2) Meet a left parenthesis (3) we see a symbol of lower precedence, or a right- associative symbol of equal precedence. (4) Then push the operator. End of input: Pop all remaining symbols. 10/3/2015 74 Precedence Table The Algorithm is implemented by use of a precedence table; associativity can be incorporated into precedences. Each symbol has two precedences: one as current symbol, one as top of operator stack. 10/3/2015 75 The LinkedStack Class Now let's examine a linked implementation of a stack We will reuse the LinearNode class that we used in LinkedList implementation to define the linked implementation of a set collection Internally, a stack is represented as a linked list of nodes, with a reference to the top of the stack and an integer count of the number of nodes in the stack 10/3/2015 76 A linked implementation of a stack 10/3/2015 77 LinkedStack - the push Operation Top is declared at the top of the class as: LinearNode top ( similar to head) What method is this similar to? 10/3/2015 78 The stack after pushing element T 10/3/2015 79 LinkedStack - the pop Operation What method is this similar to? 10/3/2015 80 The stack after a pop operation 10/3/2015 81 The ArrayStack Class Now let's examine an array-based implementation of a stack We'll make the following design decisions: maintain an array of T references the bottom of the stack is at index 0 the elements of the stack are in order and contiguous an integer variable top stores the index of the next available slot in the array This approach allows the stack to grow and shrink at the higher indexes 10/3/2015 82 An array implementation of a stack 10/3/2015 83 ArrayStack - the push Operation //----------------------------------------------------------------// Adds the specified element to the top of the stack, expanding // the capacity of the stack array if necessary. //----------------------------------------------------------------- public void push (T element) { if (size() == stack.length) expandCapacity(); // store the element in the array // increment top } 10/3/2015 84 The stack after pushing element E 10/3/2015 85 ArrayStack - the pop Operation //----------------------------------------------------------------- // Removes the element at the top of the stack and returns a // reference to it. Throws an EmptyStackException if the stack // is empty. //----------------------------------------------------------------- public T pop() throws EmptyStackException { if (isEmpty()) throw new EmptyStackException(); // decrement top; // store the element in top –in an object of type T to return it // set top of stack to null return result; } 10/3/2015 86 The stack after popping the top element 10/3/2015 87 The java.util.Stack Class The Java Collections framework defines a Stack with similar operations It is derived from the Vector class and thus has methods that are not appropriate for a Stack The java.util.Stack class has been around since the original version of Java, and has been retrofitted to meld with the Collections framework. 10/3/2015 88 Stacks The java.util package contains a Stack class that is implemented using a Vector. It contains methods that correspond to standard stack operations plus method that returns an integer corresponding to the position in the stack of the particular object. This type of searching is not usually considered to be part of the classic stack ADT. 10/3/2015 89 Analysis of Stack Operations Because stack operations all work on one end of the collection, they are generally efficient The push and pop operations, for both linked and array implementations, are O(1) Likewise, the other operations for all implementations are O(1) We'll see that other collections (which don't have that characteristic) aren't as efficient for all operations 10/3/2015 90 Collections Framework Let’s review more about the properties that all the collection classes have in common: Allow the collection size to increase dynamically All only hold items that are generic - T Provides at least two constructors – one to create an empty collection and one that accepts as a parameter any other collection object and creates a new collection object that holds the same information. 10/3/2015 91 Collections Framework The collections differ in: Logical structure of the elements they contain The underlying implementation’ The efficiency of the various operations The set of supported operations Whether they allow duplicates Whether they allow keys Whether the elements are sorted 10/3/2015 92 Collections Framework The Vector class has been replaced by the ArrayList class which provides the same methods in a single thread environment. The HashTable class also supports synchronization so for single thread programs you should use HashMap. The Stack class of the Collections Framework is implemented with a Vector. There are the expected problems with performance due to concurrency and a logical error. Vectors allow access anywhere in the array, stacks do not. 10/3/2015 93 Collections Framework The Collection Interface is used by classes that do not support a unique key value, e.g. unkeyed lists and sets. Some methods in the interface are: boolean Add(T obj) - adds obj to Collection boolean addAll(Collection c) –add c to Collection boolean contains(T obj) – return true if obj is in Collection boolean isEmpty() - returns true if collection is empty 10/3/2015 94 Collections Framework The MAP interface:: This interface is used by library collection classes that map unique keys to values. It defines a method to retrieve an object based on its key value. Classes that implement the MAP interface are: AbstractMap, HashMap and HashTable. 10/3/2015 95 Collections Framework The AbstractCollection Class implements the Collection interface. The Collection interface defines 15 operations Some of these methods define fundamental operations which will vary with the particular collection. Others will be the same no matter what the implementation, e.g. The size method will depend upon the implementation so it is an abstract method but the isEmpty() method can be implemented as: public boolean isEmpty() { return (this.size() == 0) } 10/3/2015 96 Collections Framework By defining as many methods as possible in terms of the fundamental operations, the AbstractCollection class cuts down on the time to implement a new collection. In addition, two other abstract classes extend the AbstractCollection class – AbstractSet and AbstractList. Both these classes perform the same services as the AbstractCollection class Finally, concrete classes extend AbstractSet and AbstractList. 10/3/2015 97 Collection List Set AbstractList ArrayList interface LinkedList abstract class AbstractSet HashSet TreeSet fully-defined class 10/3/2015 98

Descargar
# COP-3530 Data Structures