数据结构课件_03Stacks-Queues.pdf
Data Structures Stacks Teacher : Wang Wei 1 1. Ellis Horowitz,etc., Fundamentals of Data Structures in C++ 2. 金远平, 数据结构 3. http://inside.mines.edu/~dmehta/ 4. 殷人昆, 数据结构 王伟, 计算机工程系, 东南大学 Stack • • • • • Linear list A LIFO (Last-In-First-Out) list One end is called top Other end is called bottom From the top only – – Insertions / Additions / Puts / Pushes Deletions / Removals / Pops 2 王伟, 计算机工程系, 东南大学 inserting and deleting elements in a stack: D C B A top top top B top C C B B A A A A add add add del 王伟, 计算机工程系, 东南大学 top 3 Stack Presentment and Implement • Use private: T* stack; int top; int capacity; //maxSize • an array • a variable top • Initially, top = –1 0 1 2 3 4 5 6 7 8 9 maxSize-1 elements top (empty) Stack elements are stored in stack[0] through stack[top] 王伟, 计算机工程系, 东南大学 4 The Class : Stack template class Stack { public: Stack(int stackCapacity = 10); ~Stack() {delete [] stack;} bool IsEmpty() const; T& Top() const; void Push(const T& item); void Pop(); private: // array for stack elements T *stack; int top; // position of top element int capacity; // capacity of stack array }; 王伟, 计算机工程系, 东南大学 5 template Stack::Stack(int stackCapacity): capacity(stackCapacity) { if (capacity < 1) throw “Stack capacity must be > 0”; stack = new T[capacity]; top = -1; } template Inline bool Stack::IsEmpty() const // check whether top >= 0 { return(top == -1); } template inline T& Stack::Top() // if not empty return stack[top] { if (IsEmpty()) throw “Stack is Empty”; return stack[top]; } 王伟, 计算机工程系, 东南大学 6 template void Stack::Push(const T& x) // Add an element to the top of the stack { if (top == capacity - 1) // if array full { ChangeSize1D(stack, capacity, 2*capacity); capacity *= 2; } a b c d e stack[++top] = x; 0 1 2 3 4 } top template void Stack::Pop() // Delete top element of stack { if (IsEmpty()) throw “Stack is empty, cannot delete.”; stack[top--]; } a b c d e 0 1王伟, 计算机工程系, 2 3东南大学 4 top 7 Function ChangeSize • use a 1D array to represent a stack • 1-Dimensional array • changes the size from oldSize to newSize template void ChangeSize(T* a, const int oldSize, const int newSize) { if (newSize < 0) throw “New length must be >= 0”; T* temp = new T[newSize]; int number = min(oldSize, newSize); copy(a, a + number, temp); delete [] a; a = temp; } 王伟, 计算机工程系, 东南大学 8 Application • Recursion • Try-Throw-Catch • Parentheses Matching • Expressions • Maze • Chess • Switch Box Routing 王伟, 计算机工程系, 东南大学 9 System Stack and Recursion • Be used by a program at runtime to process function calls • A function is invoked – creates a structure : stack frame and activation-record – places it on the top of the system stack Stack frame previous frame pointer return address local variables Activation-record 王伟, 计算机工程系, 东南大学 10 1, 当n 0时 n! n ( n 1)!, 当 n 1时 long Factorial(long n) { if (n == 0) return 1; else return n*Factorial(n-1); } 王伟, 计算机工程系, 东南大学 11 Activation-record Invoking block Function block ………………. <下一条指令>Function(<参数表>) ………………. 王伟, 计算机工程系, 东南大学 12 void main() { int n; n = Factorial(4); RetLoc1 } long Factorial(long n) { int temp; if (n == 0) return 1; else temp = n * Factorial(n-1); RetLoc2 return temp; } 王伟, 计算机工程系, 东南大学 13 Data Structures Application of Stacks : Mazing Teacher : Wang Wei 14 1. Ellis Horowitz,etc., Fundamentals of Data Structures in C++ 2. 金远平, 数据结构 3. http://inside.mines.edu/~dmehta/ 4. 殷人昆, 数据结构 王伟, 计算机工程系, 东南大学 Rat In A Maze • Move order is: right, down, left, up • Block positions to avoid revisit. 王伟, 计算机工程系, 东南大学 15 Rat In A Maze • Path from maze entry to current position operates as a stack. 16 王伟, 计算机工程系, 东南大学 Standing… Wondering… • Move forward whenever possible – no wall & not visited • Move back ---- HOW ? – remember the footprints – or …… Better ? – NEXT possible move from previous position • Storage ? – STACK 17 王伟, 计算机工程系, 东南大学 A Mazing Problem Find a path from the entrance to the exit of a maze entrance 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 0 0 1 1 0 0 0 王伟, 计算机工程系, 东南大学 exit 18 Representation • maze[i][j] 1 i m, 1 j p – 1 --- blocked – 0 --- open – the entrance : maze[1][1] – the exit : maze[m][p] – current point : [i][j] – boarder of 1’s, • so a maze[m+2][p+2] – 8 possible moves • N, NE, E, SE, S, SW, W, NW 19 王伟, 计算机工程系, 东南大学 To predefine the 8 moves NW N NE [i-1][j-1] [i-1][j] [i-1][j+1] ⊙ [i][j+1] W [i][j-1] E [i] [j] [i+1][j-1] [i+1][j] [i+1][j+1] SW S SE struct offsets { int a; int b; }; enum directions {N, NE, E, SE, S, SW, W, NW}; offsets move[8]; 王伟, 计算机工程系, 东南大学 20 The basic idea : Given current position [i][j] and 8 directions to go Pick one direction d Get the new position [g][h] If [g][h] is the goal, success If [g][h] is a legal position, save [i][j] and d+1 in a stack in case, take a false path and need to try another direction [g][h] becomes the new current position Repeat until either success or every possibility is tried 王伟, 计算机工程系, 东南大学 21 In order to prevent us from going down the same path twice : mark[m+2][p+2] : use another array which is initially 0 mark[i][j] : is set to 1 once the position is visited Need a stack of items: struct Items { int x, y, dir; }; Set the size of stack to m*p to avoid doubling array capacity during stack pushing 王伟, 计算机工程系, 东南大学 22 void path(const int m, const int p) { //Output a path (if any) in the maze //maze[0][i]=maze[m+1][i]=maze[j][0]=maze[j][p+1]=1,0 i p+1, 0 j m+1 // start at (1,1) mark[1][1]=1; Stack stack(m*p); Items temp(1, 1, E); stack.Push(temp); while ( !stack.IsEmpty() ) { temp= stack.Top(); Stack.Pop(); int i=temp.x; int j=temp.y; int d=temp.dir; 王伟, 计算机工程系, 东南大学 23 while (d<8) { int g=i+move[d].a; int h=j+move[d].b; if ((g==m) && (h==p)) { // reached exit // output path cout < priority(+) = priority(-) • When an operand lies between two operators, the operand associates with the operator that has higher priority 王伟, 计算机工程系, 东南大学 31 • When an operand lies between two operators that have the same priority, the operand associates with the operator on the left a+b-c a*b/c/d • Sub-expression within delimiters is treated as a single operand, independent from the remainder of the expression – Such as parentheses (括号) (a + b) * (c – d) / (e – f) 王伟, 计算机工程系, 东南大学 32 • Postfix and Prefix expression forms – it is easier for a computer to evaluate expressions that are in these forms – do not rely on operator priorities, a tie breaker, or delimiters 王伟, 计算机工程系, 东南大学 33 Postfix Form • The postfix form of a variable or constant is the same as its infix form – a, b, 3.25 • The relative order of operands is the same in infix and postfix forms • Operators come immediately after the postfix form of their operands – Infix : a + b – Postfix : ab+ 王伟, 计算机工程系, 东南大学 34 Unary Operators • Replace with new symbols +a +a+b -a - a-b => a @ => a @ b + => a ? => a ? b - 王伟, 计算机工程系, 东南大学 35 Problem: how to evaluate an expression? 王伟, 计算机工程系, 东南大学 36 postfix: AB /C –D E *+ AC *– Read the postfix left to right to evaluate it operation postfix T1= A/B T1 C – D E * + A C * – T 2 = T1 - C T2 D E * + A C * – T3= D*E T2 T3 + A C * – T 4 = T2 + T 3 T4 A C * – T5= A*C T 4 T5 – T6= T4–T5 T6 王伟, 计算机工程系, 东南大学 37 Virtues of postfix: • no need for parentheses (括号) • the priority of the operators is no longer relevant Idea: What data structure should be used? make a left to right scan store operands evaluate operators whenever occurred 王伟, 计算机工程系, 东南大学 38 void Eval(Expression e) // Evaluate the postfix expression e { // It is assumed that the last token in e is ‘#’ // A function NextToken is used to get the next token from e // Use stack Stack stack; //initialize stack for (Token x = NextToken(e); x!=‘#’; x=NextToken(e)) { if (x is an operand) stack.Push(x); else { // operator } } } 王伟, 计算机工程系, 东南大学 39 Infix to Postfix Idea: note the order of the operands in both infix and postfix infix: A/B–C+D*E–A*C postfix: A B / C – D E * + A C * – immediately passing any operands to the output store the operators somewhere until the right time A*(B+C)*D ABC+*D* 40 王伟, 计算机工程系, 东南大学 A*(B+C)*D ABC+*D* Next token stack output A * ( B + C ) * D # A A A AB AB ABC ABC+ ABC+ * ABC+ *D ABC+ *D* # #* #*( #*( #*(+ #*(+ #* #* #* # 王伟, 计算机工程系, 东南大学 41 isp : in-stack priority (栈内优先级) icp : in-coming priority (入栈/栈外优先级) Such as, assume : Operator x # isp 8 icp ( - *, /, % +, 8 1 2 3 0 1 2 3 ) Rule : when operators are taken out of stack their isp less than icp of the new operator in-stack priority is number their isp equal to icp of the new operator 王伟, 计算机工程系, 东南大学 42 // output the postfix of the infix expression e. It is assumed // that the last token in e is ‘#’. Also, ‘#’ is used at the bottom // of the stack. // void Postfix (Expression e) { Stack stack; //initialize stack stack.Push(‘#’); 王伟, 计算机工程系, 东南大学 43 for (Token x=NextToken(e); x!=‘#’; x=NextToken(e)) if (x is an operand) cout< class Queue { public: Queue(int stackCapacity = 10); ~Queue() {delete[] Queue;} bool IsEmpty() const; T& Front() const; T& Rear() const; void Push(const T& item); void Pop(); private: // array for stack elements T *queue; int front; // position of front element int reae; // position of rear element int capacity; // capacity of stack array 王伟, 计算机工程系, 东南大学 }; 56 template Queue::Queue(int queueCapacity):capacity(queueCapacity) { if (capacity < 1) throw “Queue capacity must > 0”; queue = new T[capacity]; front = rear = 0; } template inline bool Queue::IsEmpty() { return front==rear }; 王伟, 计算机工程系, 东南大学 57 template inline T& Queue::Front() { if (IsEmpty()) throw “Queue is empty. No front element”; return queue[(front+1)%capacity]; } template inline T& Queue::Rear() { if (IsEmpty()) throw “Queue is empty. No rear element”; return queue[rear]; } 王伟, 计算机工程系, 东南大学 58 template void Queue::Pop() { // Delete front element from queue if (IsEmpty()) throw “Queue is empty. Cannot delete”; front = (front+1)%capacity; queue[front]; } For the circular representation the worst-case add and delete times are O(1) assuming no array resizing is needed 王伟, 计算机工程系, 东南大学 59 template void Queue::Push(const T& x) { // add x at rear of queue if ((rear+1)%capacity == front) // queue full, double capacity { // code to double queue capacity comes here } rear = (rear+1)%capacity; queue[rear] = x; } 王伟, 计算机工程系, 东南大学 60
数据结构课件_03Stacks-Queues.pdf
