數(shù)據(jù)結(jié)構(gòu)英文教學(xué)課件：chapter4 Stacks and Queues

1、Chapter 4 Stacks and Queues 2022/7/18Software College Northeastern UniversityOverviewStack Model Implementation of Stacks Applications of stacks Queue Models Array Implementation of Queues Applications of Queues2022/7/18Software College Northeastern UniversityStack ADTA stack is a list in which inse

2、rtion and deletion take place at the same endThis end is called topThe other end is called bottomStacks are known as LIFO (Last In, First Out) lists.The last element inserted will be the first to be retrieved18742topbottom2022/7/18Software College Northeastern UniversityData Structure - StacksReal l

3、ife analogy:ElevatorDish holders (stacks)Typical uses of stacks:Balancing symbols for syntax checks (see notes)Prefix-/Postfix- calculators2022/7/18Software College Northeastern UniversityData Structures - StacksOperations of StackIsEmpty: return true if stack is empty, return false otherwiseIsFull:

4、 return true if stack is full, return false otherwisetop: return the element at the top of stackPush: add an element to the top of stackPop: delete the element at the top of stackdisplayStack: print all the data in the stack2022/7/18Software College Northeastern UniversityData Structure - StacksStac

5、ks are known as LIFO (Last In, First Out) lists:The last element inserted will be the first to be retrieved, using Push and PopPushAdd an element to the top of the stackPopRemove the element at the top of the stacktopempty stackAtoppush an elementtoppush anotherABtoppopA2022/7/18Software College Nor

6、theastern Universitytemplate class Stack /對象：零個或多個元素的有限序列。public: Stack ( int=10 ); /構(gòu)造函數(shù) void Push ( const Type & item); /進(jìn)棧 Type Pop ( ); /出棧 Type GetTop ( ); /取棧頂元素 void MakeEmpty ( ); /置空棧 int IsEmpty ( ) const; /判?？辗?int IsFull ( ) const; /判棧滿否Stack ADTHow to store the stck?How to realize push

7、and pop？2022/7/18Software College Northeastern UniversityImplementation of StacksAny list implementation could be used to implement a stackArrays - static: the size of stack is given initiallyLinked lists - dynamic: never become fullWe will explore implementations based on array and linked list2022/

8、7/18Software College Northeastern UniversityAttributes of Stackstacksize: the max size of stacktop: the Address of the top element of stackbase: points to structure storing elements of stackArray Implementation of Stacks2022/7/18Software College Northeastern University#include template class Stack p

9、rivate: int top; /棧頂數(shù)組指針 Type *elements; /棧數(shù)組，棧不空時elements0是 棧中第一個元素 int maxSize; /棧最大可容納元素個數(shù)public: Stack ( int=10 ); /構(gòu)造函數(shù) Stack ( ) delete elements; /析構(gòu)函數(shù)Array Implementation of Stacks2022/7/18Software College Northeastern University void Push ( const Type & item ); /進(jìn)棧 Type Pop ( ); /出棧 Type Get

10、Top ( ); /取棧頂 void MakeEmpty ( ) top = -1; /置空棧 int IsEmpty ( ) const return top = -1; int IsFull ( ) const return top = maxSize -1; Array Implementation of Stacks2022/7/18Software College Northeastern Universitytemplate Stack:Stack ( int s ) : top (-1), maxSize (s) /建立一個最大尺寸為s的空棧，若分配不成功則錯誤處理 elemen

11、ts = new TypemaxSize; assert ( elements != 0 ); /斷言Allocate a stack array of maxSize.Initially top is set to -1. It means the stack is empty. Array Implementation - Init a Stack2022/7/18Software College Northeastern University Array Implementation - Push2022/7/18Software College Northeastern Univers

12、ity1、NOTE：Is there spare space?2、Push an element onto the stack3、Note top always represents the indexof the top element. After pushing an element, increase top.template void Stack:Push ( const Type & item ) assert ( !IsFull ( ) ); /先決條件斷言 elements+top = item; /加入新元素2022/7/18Software College Northeas

13、tern UniversityArray Implementation - Pop2022/7/18Software College Northeastern University/若棧不空則函數(shù)返回該棧棧頂元素的值，然后棧頂指針退1template Type Stack:Pop ( ) assert ( !IsEmpty ( ) ); /先決條件斷言 return elementstop-; /退出棧頂元素Pop Stack:1、Note ：Is there any elements in the stack?2、Pop and return the element at the top o

14、f the stack. Dont forget to decrease top2022/7/18Software College Northeastern Universitytemplate Type stack:GetTop ( ) assert ( !IsEmpty ( ) ); /先決條件斷言 return elementstop; /取出棧頂元素Array Implementation GetTop2022/7/18Software College Northeastern University#include#includeusing namespace std;main()st

15、ack a;for(int i=0; i10; i+)a.push(i);for(i =0; i10; i+)couta.top();a.pop();Array Impln: Example2022/7/18Software College Northeastern University1、一個棧的入棧序列是a，b，c，d，e，則下列哪個是不可能的輸出序列？_。edcba B. decba C. dceab D. abcde 2、若棧的輸入序列是1，2，3，n，輸出序列的第一個元素是n，則第i個輸出的元素是_。A. n-i B. n-i+1 C. n-i-1 D. i 2022/7/18Sof

16、tware College Northeastern UniversityArray Impln: Bidirectional stackFull: t0 = t1 Empty: ti = bi2022/7/18Software College Northeastern Universitydata linkStopbottoman-1a1anImplementation based on Linked List2022/7/18Software College Northeastern UniversityImplementation based on Linked Listtemplate

17、 class Stack;template class StackNode friend class Stack;private: Type data; /結(jié)點(diǎn)數(shù)據(jù) StackNode *link; /結(jié)點(diǎn)鏈指針 StackNode ( Type d = 0, StackNode *l = NULL ) : data ( d ), link ( l ) ;2022/7/18Software College Northeastern Universitytemplate class Stack public: Stack ( ) : top ( NULL ) Stack ( ); void Pu

18、sh ( const Type & item); Type Pop ( ); Type GetTop ( ); void MakeEmpty ( ); /實(shí)現(xiàn)與Stack( )同 int IsEmpty ( ) const return top = NULL; private: StackNode *top; /棧頂指針I(yè)mplementation based on Linked List2022/7/18Software College Northeastern Universitytemplate Stack:Stack ( ) StackNode *p; while ( top != N

19、ULL ) /逐結(jié)點(diǎn)回收 p = top; top = toplink; delete p; Implementation based on Linked List2022/7/18Software College Northeastern Universitydata linktopbottoman-1a1itemImplementation based on Linked Listtemplate void Stack:Push ( const Type &item ) top = new StackNode ( item, top ); /新結(jié)點(diǎn)鏈入top之前, 并成為新棧頂2022/7

20、/18Software College Northeastern Universitytemplate Type Stack:Pop ( ) assert ( !IsEmpty ( ) ); StackNode *p = top; Type retvalue = pdata; /暫存棧頂數(shù)據(jù) top = toplink; /修改棧頂指針 delete p; return retvalue; /釋放,返回數(shù)據(jù)template Type Stack:GetTop ( ) assert ( !IsEmpty ( ) ); return topdata; Implementation based on

21、 Linked List2022/7/18Software College Northeastern UniversitySTL stack Adapter(deque)Member Description value_type 棧中存儲對象的類型size_type 無符號整數(shù)stack() 構(gòu)造函數(shù)，產(chǎn)生一個空棧 stack(const stack&) 拷貝構(gòu)造函數(shù)stack& operator=(const stack&) 賦值符號bool empty() const 如果沒有元素返回true，否則返回false。 相當(dāng)于 S.size() = 0. size_type size() co

22、nst 返回棧中元素的個數(shù) 2022/7/18Software College Northeastern Universityvalue_type& top() 返回棧頂元素的引用。前提:empty() is false. const value_type& top() const 返回棧頂元素的常引用。前提：empty() is false. void push(const value_type& x) 棧頂插入x。size() 增1, top()等于 x. STL stack Adapter2022/7/18Software College Northeastern Universityv

23、oid pop() 移出棧頂元素。前提： empty() is false. 結(jié)果: size()減1. bool operator=(const stack&, const stack&) 比較兩個棧是否相等。如果他們包含相同個數(shù)的元素，并且元素對應(yīng)相等，則兩個棧相等。該函數(shù)為全局函數(shù)，不是成員函數(shù)。 bool operator(const stack&, const stack&) 按字典序比較兩個棧大小，全局函數(shù)，不是成員函數(shù)STL stack Adapter2022/7/18Software College Northeastern University#include #includ

24、e #include #include using namespace std; int main(int argc, char* argv) stack s; s.push(1); s.pop(); s.push(10); s.push(11); cout s.top() endl; cout s.size() endl; cout s.empty() endl; return EXIT_SUCCESS; Example2022/7/18Software College Northeastern University#include #include #include #include #i

25、nclude using namespace std; void usage_fail(char *argv) cerr Usage: argv0 -n file endl; exit(EXIT_FAILURE); int main( int argc, char *argv) char *filename = NULL; if ( argc = 2 ) filename = argv1; else cerr Usage: argv0 -n file endl; return EXIT_FAILURE; Example2022/7/18Software College Northeastern

26、 University/*!Begin Snippet*/ open file specified by command-line argumentifstream inf(argv1); if ( !inf ) cerr cannot open filename for input endl; return EXIT_FAILURE; stack s; string line; / read file line by linewhile (getline(inf, line) s.push(line); inf.close(); 2022/7/18Software College North

27、eastern University/ print lines in reversewhile (!s.empty() cout s.top() endl; s.pop(); /*!End Snippet*/ return EXIT_SUCCESS; 2022/7/18Software College Northeastern UniversityApplication: Balancing SymbolsTo check that every right brace, bracket, and parentheses must correspond to its left counterpa

28、rt e.g. ( ) is legal but ( ) is illegal2022/7/18Software College Northeastern UniversityApplication: Balancing SymbolsAlgorithm(1) Make an empty stack.(2) Read characters until end of filei. If the character is an opening symbol, push it onto the stackii. If it is a closing symbol, then if the stack

29、 is empty, report an erroriii.Otherwise, pop the stack. If the symbol popped is not the corresponding opening symbol, then report an error(3) At end of file, if the stack is not empty, report an error2022/7/18Software College Northeastern UniversityArray implementation versus linked list implementat

30、ionsPush, Pop, GetTop are all constant-time operations in both array implementation and linked list implementationFor array implementation, the operations are performed in very fast constant timeApplication: Balancing Symbols2022/7/18Software College Northeastern Universityint matching(string &exp)

31、/exp is a pointer to a string to check int state = 1,i=0; char e; stack s; while ( iexp.length() & state ) switch (expi) case : case (: s.push(expi); /push the open character onto stack i+; break; Application: Balancing Symbols2022/7/18Software College Northeastern University case ): if ( !s.empty()

32、 & s.top() = () s.pop(); i+; else state = 0; /an error occurs break; case : if ( !s.empty() & s.top() = ) s.pop(); i+; else state = 0; / an error occurs break; default: i+; break; /end of while if ( state & s.empty() ) return 1; else return 0; 2022/7/18Software College Northeastern UniversityWays to

33、 write expressionsInfix (standard)PrefixPostfixcompiler, a parenthesis-free notationInfix Postfix2+3*4 2 3 4*+a*b+5 ab*5+(1+2)*7 1 2+7*a*b/c ab*c/(a/(b-c+d)*(e-a)*c abc-d+/ea-*c*a/b-c+d*e-a*c ab/c-de*+ac*-Evaluation of Expressions2022/7/18Software College Northeastern UniversityEvaluation of Postfix

34、 ExpressionsLeft-to-right scan Postfix expression,Stack operands until find an operator,Meet operator, remove correct operands for this operator,Perform the operation,Stack the resultRemove the answer from the top of stack2022/7/18Software College Northeastern UniversityTokenStackTop01266 0262 1/3 0

35、33 3 1-0 040 4 120 4 2 2*0 8 1+8 0Postfix evaluation of 6 2/3-4 2*+Evaluation of Postfix Expressions2022/7/18Software College Northeastern UniversityEnum Boolean False,True;#include #include #include class Calculator public: Calculator(int sz):s(sz) double Run(); / 執(zhí)行表達(dá)式計算 void Clear();private: void

36、 AddOperand(double value); Boolean Get2Operands(double &left,double &right); void DoOperator(char op); stack s;2022/7/18Software College Northeastern Universityvoid Calculator:AddOperand(double value) s.push(value);Boolean Calculator:Get2Operands(double &left,double &right) if(s. empty( ) cerr“Missi

37、ng Operand!”endl; return False; right = s.top( );s.pop(); if(s.empty( ) cerr“Missing Operand!”endl; return False; left = s.top( );s.pop(); return True; 2022/7/18Software College Northeastern Universityvoid Calculator:DoOperator(char op) double left,right;Boolean result; result = Get2Operand(left,rig

38、ht); if(result = TRUE) switch( op ) case+:s.push(left + right);break; case-:s.push(left - right);break; case*:s.push(left * right);break; case/: if(abs(right) = 1E-6) cerr “Divide by 0” ch, ch != =) swith( ch ) case+: case-: case*: case/: case: DoOperator(ch),break; default: cin.putback(ch); cin new

39、operand; AddOperand(newoperand); break; ret = s.top();s.pop();return ret;2022/7/18Software College Northeastern UniversityInfix to PostfixMethod IFully parenthesize the expressionMove all binary operators so that they replace their corresponding right parenthesesDelete all parenthesesExamples: a/b-c

40、+d*e-a*c(a/b)-c)+(d*e)-(a*c), fully parenthesesab/c-de*+ac*-, replace right parentheses and delete all parenthesesDisadvantageinefficient, two passes2022/7/18Software College Northeastern UniversityInfix to PostfixMethod IIscan the infix expression left-to-rightoutput operand encounteredoutput opera

41、tors depending on their precedence, i.e., higher precedence operators firstExample: a+b*c, simple expressionToken Stack TopOutput012a-1a+0ab+0ab*+*1abc+*1abceos-1abc*+2022/7/18Software College Northeastern UniversityExample 1：234 # s2: Postfix：Example 2：234 s2: Postfix： 2+3*4*+#2 3 4 234+#2 3 4 Infi

42、x to Postfix2022/7/18Software College Northeastern University各個算符的優(yōu)先級別各個算符的優(yōu)先級別操作符#（*,/,%+,-)isp017538icp086421否則，棧頂操作符和新讀入的操作符進(jìn)行優(yōu)先級比較，決定做什么操作； 棧內(nèi)優(yōu)先數(shù)高，棧頂操作符出棧 棧外優(yōu)先數(shù)高，新讀入的操作符入棧 新讀入的是括號，連續(xù)輸出棧中操作符號 直到遇到左括號為止 2022/7/18Software College Northeastern Universityvoid postfix(expression e) stack s; char ch,y;

43、 s.makeEmpty(); s.push(#); while(cin.get(ch),ch != #) if(isdigit(ch) cout ch; else if(ch = ) while(!s.empty() & (y=s.top() != () cout icp(ch) couty; s.pop();s.push(ch); 2022/7/18Software College Northeastern UniversityQueue ModelLike a stack, a queue is also a list. However, with a queue, insertion

44、is done at one end, while deletion is performed at the other endThe insertion end is called rearThe deletion end is called frontAccessing the elements of queues follows a First In, First Out (FIFO) order.Insert (Enqueue)Remove(Dequeue)rearfront2022/7/18Software College Northeastern UniversityQueue A

45、DTReal life analogy:Check-out lines in a store (queuing up)Typical uses of queues:Waiting lists of course registrationSimple scheduling in routersAny list implementation could be used to implement a queueArrays (static: the size of queue is given initially)Linked lists (dynamic: never becomes full)2

46、022/7/18Software College Northeastern UniversityEnqueue and DequeuePrimary queue operations: Enqueue and DequeueLike check-out lines in a store, a queue has a front and a rear. Enqueue insert an element at the rear of the queueDequeue remove an element from the front of the queueInsert (Enqueue)Remo

47、ve(Dequeue)rearfront2022/7/18Software College Northeastern UniversityQueue ADTAttributes of Queuefront/rear: front/rear indexcounter: number of elements in the queuemaxSize: capacity of the queuevalues: points to structure storing elements of the queueOperations of QueueIsEmpty: return true if queue

48、 is empty, return false otherwiseIsFull: return true if queue is full, return false otherwiseEnqueue: add an element to the rear of queueDequeue: delete the element at the front of queueDisplayQueue: print all the data2022/7/18Software College Northeastern UniversityImplementation of QueueJust as st

49、acks can be implemented as arrays or linked lists, so with queues.Dynamic queues have the same advantages over static queues as dynamic stacks have over static stacks2022/7/18Software College Northeastern UniversityQueue Implementation of ArrayThere are several different algorithms to implement Enqu

50、eue and DequeueNave wayWhen enqueuing, the front index is always fixed and the rear index moves forward in the array.frontrearEnqueue(3)3frontrearEnqueue(6)36frontrearEnqueue(9)3692022/7/18Software College Northeastern UniversityQueue Implementation of ArrayNave way (contd)When dequeuing, the front

51、index is fixed, and the element at the front the queue is removed. Move all the elements after it by one position. (Inefficient ! ! !)Dequeue()frontrear69Dequeue()Dequeue()frontrear9rear = -1 front2022/7/18Software College Northeastern UniversityQueue Implementation of ArrayA better wayWhen an item

52、is enqueued, the rear index moves forward.When an item is dequeued, the front index also moves forward by one element XXXXOOOOO (rear) OXXXXOOOO (after 1 dequeue, and 1 enqueue)OOXXXXXOO (after another dequeue, and 2 enqueues)OOOOXXXXX (after 2 more dequeues, and 2 enqueues)(front)The problem here i

53、s that the rear index cannot move beyond the last element in the array.2022/7/18Software College Northeastern UniversityImplementation using Circular ArrayUsing a circular arrayWhen an element moves past the end of a circular array, it wraps around to the beginning, e.g.OOO963 4OO963 (after Enqueue(

54、4)After Enqueue(3), the rear index moves from 5 to 0.By operator % rear3963 124 05front4rear2022/7/18Software College Northeastern Universityrear54 03 12frontJ2J3J4J5J6J1frontrear54 03 12Empty queue full queueHow to detect an empty or full queue, using a circular array algorithm? One way :- Use a co

55、unter of the number of elements in the queue.Implementation using Circular Array2022/7/18Software College Northeastern UniversityAnother way:A queue is considered full when one space is left.Full queue: front = (rear+1) % MAXQSIZEEmpty queue： front = rearfront54 03 12J2J3J4J5J1rearfrontrear54 03 12

56、empty fullImplementation using Circular Array2022/7/18Software College Northeastern University#include template class Queue private: int rear, front; Type *elements; int maxSize;public: Queue ( int=10 ); Queue ( ) delete elements; Implementation using Circular Array2022/7/18Software College Northeas

57、tern University void EnQueue ( const Type & item); Type DeQueue ( ); Type GetFront ( ); void MakeEmpty ( ) front = rear = 0; int IsEmpty ( ) const return front = rear; int IsFull ( ) const return (rear+1) % maxSize = front; int Length ( ) const return (rear-front+maxSize) % maxSize;Implementation us

58、ing Circular Array2022/7/18Software College Northeastern Universitytemplate Queue:Queue ( int sz ) : front (0), rear (0), maxSize (sz) elements = new TypemaxSize; assert ( elements != 0 );frontrear54 03 12Implementation using Circular Array2022/7/18Software College Northeastern UniversityImplementat

59、ion using Circular Array2022/7/18Software College Northeastern Universityfrontrear54 03 12J1J3J2xfrontrear54 03 12J1J3J2BeforeAftertemplate void Queue:EnQueue ( const Type & item ) assert ( !IsFull ( ) ); rear = (rear+1) % MaxSize; elementsrear = item;2022/7/18Software College Northeastern Universit

60、yfrontrear54 03 12J1J3J2Beforefrontrear54 03 12J3J2 After template Type Queue:DeQueue ( ) assert ( !IsEmpty ( ) ); front = ( front+1) % MaxSize; return elementsfront;2022/7/18Software College Northeastern Universitytemplate Type Queue:GetFront ( ) assert ( !IsEmpty ( ) ); return elements(front+1)%Ma