《数据结构与算法》Chap3 stack

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,College of Electronic and Information Engineering,Chongqing University of Science and Technology,Instructor: Xiong Qian,Spring 2013,Data Structures and Algorithms Chapter 3:,Stacks,Chapter 3,Objectives,Upon completion you will be able to,Explain the design, use, and operation of a stack,Implement a stack using a linked list structure,Understand the operation of the stack ADT,Write application programs using the stack ADT,Discuss reversing data, parsing, postponing and backtracking,Stacks,highlights,3.1 Basic Stack Operations,3.2 Stack Linked List Implementation,3.3 C Language Implementations,3.4 Stack ADT,3.5 Stack Applications,Stack definition,Stack of books,The questions are:,1.How to add a book to the stack?,2.How to take the third book from top?,Understand stack,You can imagine stack as this barrel,A stack is a last in-first out,(LIFO) data structure in which all insertion and deletion are restrict to one end, called top.,Push stack,Pop stack,Stack top,3-1,Basic Stack Operations,Push stack,DATA,PUSH,DATA,DATA,Push,operation adds an item at the top of the stack.,Before adding the item, the stack space must be checked to ensure that there is enough room to hold the item.,POP Stack,POP,DATA,POP,removes the item at the top of the stack and return the item to the user(the application that calls this operation).,Be careful the empty state or,underflow,state of the stack, when you implement,pop,operation.,Stack top,Stack Top,DATA,Stack Top,copies the item at the top of the stack and return the item to the user(the application that calls this operation), but does not remove the item.,Be careful the empty state or,underflow,state of the stack, when you implement,stack top,operation.,Example of basic stack operations,Blue,Red,Green,Push,“Green”,Blue,Red,Green,Push,“Blue”,Red,Green,Blue,POP,Red,Green,Blue,PUSH,Red,Green,Blue,Red,STACK,TOP,Green,Red,Red,POP,Green,Red,POP,Green,Several data structure implement stack.,Linked list has some advantages to implement stack.,dynamic memory allocation technology to save memory space.,easily identify the Top of the stack.,the head of linked list,3-2 Stack Linked List Implementation,Conceptual and physical stack implementations,The Structure of Stack Head and Stack node,Meta data,Top,Stack Data,Next,Stack Head structure,Stack Data structure,Pointer to node,stack,count,top,end stack,node,data,next,end node,Stack Algorithms and Pseudocode implementation,Create stack,Push stack,Pop stack,Stack top,Empty stack,Full stack,Stack count,Destroy stack,Create stack,Create stack just initialize the metadata for the stack structure.,?,count,?,Top,0,count,Top,algorithm,createStack,Initialize metadata for a stack.,Pre,Stack is structure for metadata.,Post,metadata initialized,stack.count=0,stack.top=null,Return,end,createStack,Push Stack,0,count,Top,PUSH Green,1,count,Top,Green,data,next,PUSH Green,Inserts an element into the stack,1. Find memory for the new node,2. Assign the data to the stack node,3. Change the pointers,4. Count + 1,Insert a node to stack needs to know that:,Into an empty stack?,Into a stack with data,(logical is the same,),Has no memory (,overflow,),Push Stack (Continue),PUSH Blue,1,count,Top,Green,data,next,2,count,Top,blue,data,next,Green,data,next,PUSH Blue,Push Stack (Pseudocode),algorithm,pushStack( stack, data ),Insert (push) one item into the stack.,Pre,stack is metadata structure to a valid stack, data contains data to be pushed in stack,Post,data have been pushed in stack.,Return,true if successful; false if memory overflow.,1,if (stack is full),1 success=false,else,1 allocate(newPtr),2 newPtr-data=data,3 newPtr-next=stack.top,4 stack.top=newPtr,5 stack.count=stack.count+1,6 success=true,endif,return success,end,pushStack,Pop Stack,2,count,Top,blue,data,next,Green,data,next,1,count,Top,Green,data,next,POP Stack,POP Stack,Pop Stack (Continue),1,count,Top,Green,data,next,POP Stack,0,count,Top,POP Stack,Pop Stack (pseudocode),Algorithm,popStack(stack,dataOut ),This algorithm pops the item on the top of the stack and returns it to the user.,Pre,stack is metadata structure to a valid stack,dataOut is a reference variable to receive the data.,Post,Data have been returned to calling algorithm.,Return,true if successful; false if underflow.,1,If (stack empty),1 success=false,2 Else,1 dltPtr=stack.top,2 dataOut=stack.top-data,3 stack.top=stack.top-next,4 stack.count=stack.count-1,5 recycle (dltPtr),6 success=true,3 end if,4 return success,end pop stack,Stack Top,The stack top algorithm sends the data at the top of the stack back to the calling module without deleting the top node.,The logic for the stack top is simple, but one thing should be taken care, that is the state of stack empty.,Stack top (pseudocode),algorithm,stackTop(stack, dataOut ),This algorithm retrieves the data from the top of the stack without changing the stack,Pre,stack is metadata structure to a valid stack,dataOut is a reference variable to receive the data,Post,data have been returned to calling algorithm,Return,data have been returned, false if underflow.,1 if (stack empty),1 success=false,2 else,1 DataOut=stack.top-data,2 Success=true,3 end if,4 return success,end,stackTop,Destroy stack (Original state),3,count,Top,blue,data,next,Green,data,next,Red,data,next,Temp,Red,data,next,3,count,Top,blue,data,next,Green,data,next,Destroy stack (Delete item 1),Destroy stack (Delete item 2),3,count,Top,Green,data,next,Temp,blue,data,next,Destroy stack (Delete item 3),0,count,Top,Temp,Green,data,next,Pseudocode for Destroy Stack,algorithm,destroystack(stack),This algorithm releases all nodes back to the dynamic memory.,Pre,stack is metadata structure to a valid stack,Post,stack empty and all nodes recycled,loop (stack.top not null),1 temp=stack.top,2 stack.top=temp.next,3 recycle( temp),end loop,stack.count=0,return,end,destroyStack,Other stack algorithms,Fundamental stack operations include,create stack, push stack, pop stack, stack top,and,destroy stack.,In order to totally encapsulate the data and the data structure of the stack. Three simple operations are introduced. They are,empty stack, stack count,and,full stack.,Empty stack operation is very simple. Based on linked list implementation. We can just check the head node of the list to determine whether the stack is empty or not. Therefore the pseudocode is very simple.,algorithm,emptyStack(stack),Determines whether stack is empty and returns a Boolean.,Pre,stack is metadata structure to a valid stack,Post,returns stack status,Return,Boolean, true:stack empty, false: stack contains data,if (stack.top not null),1 result=false,else,1 result=true,end if,return result,End,emptyStack,Empty stack,Other condition statement(s) that can be used here to replace this statement.,Full stack,algorithm,fullStack(stack),Determines whether stack is full or not and returns a Boolean.,Pre,stack is metadata structure to a valid stack.,Post,returns stack status.,Return,Boolean, true:stack full, false:memory available,If (memory available),1 result=false,else,1 result=true,end if,return false,end,fullStack,Stack Count,algorithm,stackCount(stack),Returns the number of elements currently in stack,Pre,stack is metadata structure to a valid stack,Post,returns stack count,Return,integer count of number of elements in stack.,return (stack.count),end,stackCount,There is only one executive statement in this algorithm. Of course, it can be placed in the upper functions and eliminate this algorithm. But do not forget the essence of ADThiding the data and the structure absolutely to the upper applications.,3-3 C Language Implementations,This section presents a simple non-ADT implementation of a stack.,We develop a simple program that inserts random characters into the stack and then prints them.,3-4 Stack ADT,We begin the discussion of the stack ADT with a discussion of the stack structure and its application interface. We then develop the required functions.,Data Structure,ADT Implemenation,Typical stack applications can be classified into four broad categories:,Reversing data,Reverse a List,Convert decimal to binary,Parsing data,Parse parentheses,Postponing data usage,Infix to postfix transformation,Evaluating Postfix expressions,Backtracking steps,goal seeking,Eight Queens Problem,3-5 Stack Applications,Reverse a List,algorithm,reverseNumber,This program reverses a list of integers read from the keyboard by pushing them into a stack and retrieving them one by one.,1 createStack( stack),2 prompt (Enter a number),3 read (number),Fill stack,4 loop(not end of data AND not fullStack(stack),1 pushStack(stack, number),2 prompt (Enter next number: to stop),3 read(number),5 end loop,Now print numbers in reverse,6 Loop (not emptyStack(stack),1 popStack(stack dataOut),2 print(dataOut),7 end loop,end,reverseNumber,The idea lies in reversing data is very easy to understand. First, push each item one by one into stack(statements 4-5), then pop them out successively (statements 6-7) . Because stack is a LIFO data structure, the order of the item has been reversed.,(continued),Convert decimal to binary,divide decimal number by 2 continuously,record the remainders until the quotient becomes 0,print the remainders in backward order.,Stack is an ideal structure to implement this process.,100,2,50,2,25,2,12,2,6,2,3,2,1,0,0,0,1,0,0,1,1,2,Algorithm,decimalToBinary,This algorithm reads an integer from keyboard and print its binary equivalent. It use a stack to reverse the order of 0s and 1s produce.,1 createStack(stack),2 prompt (Enter a decimal number to convert to binary),3 read(number),4 loop (number0),1 digit=number modulo 2,2 pushOK=push(stack, digit),3 if (pushOK false),1 print (Stack overflow alert),2 quit algorithm,4 end if,5 number=number/2,5 end loop,Binary number created in stack, now print it.,6 loop (not emptyStack(stack),1 popStack(stack, digit),2 print digit,7 end loop,8 return,end,decimalToBinary,Algorithm DecimaltoBinary,The quotient,The remainder: 0 or 1,Parsing,Parsing is any logic that breaks data into independent pieces for further processing.,For example: to translate a source program to machine language,Unmatched Parentheses Example,Parentheses must be matched in an algebraic expression.,Stack can hold the left parts of these segments while scanning an expression or a statement for the later comparing.,Parse parentheses,Algorithm,parseParens,This algorithm reads a source program and parses it to make sure all opening-closing parentheses are paired.,1 loop (more data),1 read (character),2 if (character is an opening parenthesis),1 pushStack (stack, character),3 else,1 if (character is closing parenthesis),1 if (emptyStack (stack),1 print (Closing parenthesis not matched alert),2 else,1 popStack(stack,token),3 end if,2 end if,4 end if,2 end loop,3 if (not emptyStack(stack),1 print (Opening parenthesis not matched alert),4 end if,end,parseParens,Postponement,data usage,Postponement,means deferring data usage until some later point(or something happens).,Infix to postfix transformation,Infix: a+b,Prefix: +ab,Postfix: ab+,High-level language use the infix,convert it to postfix,Manual transformation,Fully parenthesize the expression using any explicit parentheses,Changing all infix notations in each parenthesis to postfix notation, starting from the innermost expressions,Remove all parentheses.,Examples of manual transformation,A+B*C,(,A+(B*C),(,A+(BC *),(,A(BC *) +),ABC*+,(,A+B)*C+D+E*F-G,(,A+B)*C)+D)+(E*F)-G),(,AB+)C*)D+)(EF*)+)G-),AB+C*D+EF*+G-,Transform expression with stack,A*B,AB*,1.,Read and copy the first operand A to the result, we get “A”.,2.Read the operator “*” and push it into a stack for later use.,3.Read and copy the second operand B to the result, we can get “AB”.,4.Finish scanning the source expression, pop up the operator and concatenate it to the result, we get “AB*”,Precedence rule,the priority of an operator pushed into the stack is higher than the operator at the top of the stack,-push it into the stack.,the operator at the top of the stack has a higher priority than or equal to the current operator,-it is popped and placed in the output expression.,A+B*C,ABC*+,Copy operand A to output expression.,Push operator + into stack.,Copy operand B to output expression.,Push operator * into stack. (Priority of * is higher than +),Copy operand C to output expression.,Pop operator * and copy to output expression.,Pop operator + and copy to output expression.,Transform expression with stack(considering priority),A+B*C-D/E,ABC*+DE/-,A+B*C-D/E,Infix,stack,postfix,+,B*C-D/E,A,B*C-D/E,+,A,*,C-D/E,+,AB,C-D/E,*,+,AB,-,D/E,*,+,ABC,D/E,-,ABC*+,/,E,-,ABC*+D,E,/,-,ABC*+D,/,-,ABC*+DE,ABC*+DE/-,Transform expression with stack(considering parenthesis),A*(B+C/D)-E,ABCD/+*E-,Infix,Stack,Postfix,A*(B+C/D)-E,*(,B+C/D)-E,A,(,B+C/D)-E,*,A,B+C/D)-E,(,*,A,+,C/D)-E,(,*,AB,C/D)-E,+,(,*,AB,/,D)-E,+,(,*,ABC,D)-E,/,+,(,*,ABC,)-,E,/,+,(,*,ABCD,-,E,*,ABCD/+,E,-,ABCD/+*,-,ABCD/+*E,ABCD/+*E-,Summary of transforming an infix to a postfix expression,Read each item in an infix expression from left to right until to the end of the infix expression,1. If the item is an open parenthesis.,2. If the item is a close parenthesis,3. If the item is an operator,4. If the item is an operand.,5. After finishing scanning infix expression,Transforming Algorithm,algorithm,inToPostFix(formula),convert infix formula to postfix.,Pre,Formula is infix notation that has been edited to ensure that there are no syntactical errors.,Post,postfix formula has been formatted as a string as postfix.,Return,postfix formula.,1 createStack(stack),2 set postfix to null string,3 looper=0,4 loop (loopersizeof formula),1 token =formulalooper,/get a token,2 if (token is open parenthesis),1 pushStack(stack token),3 elseif (token is close parenthesis),1 popStack(stack, token),2 loop (token is not open parenthesis),1 concatenate token to postfix,2 popStack(stack, token),3 end loop,4,elseif (token is operator),1 stackTop(stack, topToken),2 loop ( not emptyStack(stack) AND,priority(token)=priority(topToken),1 popStack(stack, tokenOut),2 concatenate tokenOut to postfix,3 stackTop(stack,topToken),3 end loop,4,pushStack (stack, token),5 else,1 concatenate token to postfix,6 end if,7 looper=looper+1,5 end loop,6 loop (not emptyStack(stack),1 popStack(stack,token),2 concatenate token to postfix,7 end loop,8 return postFix,end,inToPostFix,Transforming Algorithm(cont.),Evaluating Postfix expressions,postfix expression easy to evaluate with help of stack.,While scanning a postfix expression,push all operands into a stack for later use,when we meet an operator, we can popup two operands and evaluate them with the operator,push the result into the same stack,the final result will be the last item in the stack.,2*(4+6),246+*,20,Posfix,Stack,246+*,46+*,2,6+*,4,2,6,4,2,+*,*,10,2,6+4=10,20,Example of postfix expression evaluation,Evaluating Algorithm,algorithm,postFixEvaluate(expr),This algorithm evaluates a postfix expression and returns it value.,Pre,a valid expression.,Post,Postfix value computed.,Return,value of expression,1 exprsize=size of expression string,2 createStack(stack),3 index=0,4 loop (indexnodeName),3 end if,3 end loop,4 print (end of path),7 end if,8 return,end,seekGoal,Eight Queens Problem,A classic chess problem,place eight queens on the chessboard,no queen can capture another queen.,Computer solution,place a queen on the board,analyze all of the attack positions to see if there is a queen that could capture the new queen,If there is, try another position.,solve,this problem using a stack and backtracking,logic,Generalizing the solution,place a queen in a position in a row and then examine all positions in the next row to see if a queen can be placed there.,If we cant place a queen in the next row, then we backtrack to the last-positioned queen and try to position her in the next column.,If there is no room in the next column, then we fall back again.,trial-and-error method,Eight queens problem,algorithm,queens8(boardSize),Position chess queens on a game board so that no queen can capture any other queen.,Pre,boardSize is number of rows & columns on board,Post,queens positions printed,1 createStack(stack),Set row to 1,3 Set col to 0,4 loop (row = boardSize),1 loop(col= boardSize AND row = boardSize),1 popStack(stack,row,col),2 remove queen at boardrowcol,5 end loop,2 end loop,5 end loop,printBoard(stack),return,end,queens8,3-6 Stack abstract data type -array implementation,Stack array implementation,Metadata:,Maximum number of elements in stack,Count,Top: Index rather than pointer,Next fields are not needed,Null stack has a top index of -1,homework,P,139,1-11 17 18,