10.1 °³¿ä ¸¹Àº »ç¶÷µéÀÌ stack°ú queue µ¥ÀÌÅÍ Ãß»ó¿¡ ´ëÇؼ­´Â Àß ÀÌÇØÇÏ°í ÀÖ´Ù. Ã¥»óÀ§¿¡ ³õÀº ¼­·ùöÀ̳ª ÂùÀå¿¡ ³õÀÎ Á¢½ÃµéÀÌ stackÀÇ ÀüÇüÀûÀÎ ¿¹°¡ µÉ °ÍÀÌ´Ù. ÀÌµé ¸ðµÎ ¸Ç À§ÂÊ¿¡ ÀÖ´Â °ÍµéÀº Á¢±ÙÇϱⰡ °¡Àå ½±´Ù´Â Ư¡À» °¡Áø´Ù. ÄÝ·º¼Ç¿¡ »õ·Î¿î ¾ÆÀÌÅÛÀ» Ãß°¡ÇÏ´Â °¡Àå ½¬¿î ¹æ¹ýÀº ¸ÇÀ§¿¡ ¿Ã·Á ³õ´Â °ÍÀÌ´Ù. ÀÌ·±½ÄÀ¸·Î Çϸé, stack¿¡¼­ Á¦°ÅµÇ´Â ¾ÆÀÌÅÛÀº °¡Àå ÃÖ±Ù¿¡ stack¿¡ Ãß°¡µÈ ¾ÆÀÌÅÛÀÌ µÈ´Ù. [Image] LIFO¿Í FIFO ÇÑÆí, ÀÏ»ó»ýÈ°¿¡¼­ »ìÆ캼 ¼ö ÀÖ´Â queueÀÇ ¿¹·Î ÀºÇà¿¡ ¼± ÁÙÀ̳ª ¿µÈ­°ü ¾Õ¿¡ ¼± ÁÙµîÀ» µé ¼ö ÀÖ´Ù. ¿©±â¼­ »ç¶÷ÀÌ »õ·Î ÁÙÀ» ¼³ ¶§Ã³·³ »ðÀÔÀº queueÀÇ µÚ¿¡¼­ ÀÌ·ç¾îÁö°í, °ü°´ÀÌ ¿µÈ­°ü¿¡ µé¾î°¡´Â °Íó·³ ¾ÆÀÌÅÛÀÇ »èÁ¦´Â queueÀÇ ¾Õ¿¡¼­ ÀÌ·ç¾îÁø´Ù. queue¿¡¼­ÀÇ »èÁ¦¼ø¼­´Â stack°ú´Â ¹Ý´ëÀÌ´Ù. queue¿¡¼­´Â »èÁ¦µÈ ¾ÆÀÌÅÛÀÌ queue¿¡ °¡Àå ¿À·§µ¿¾È ÀÖ¾ú´ø ¿ø¼ÒÀÌ´Ù. Ç¥ÁØ ¶óÀ̺귯¸®¿¡¼­´Â stack°ú queue°¡ ¸ðµÎ ¾î´ðÅÍ(adaptor)ÀÌ°í, À̵éÀº ½ÇÁúÀûÀ¸·Î °ªÀ» ÀúÀåÇϴµ¥ »ç¿ëÇÏ´Â ÄÁÅ×À̳ʸ¦ ¹ÙÅÁÀ¸·Î ¸¸µé¾îÁø´Ù. stackÀº vector, list, dequeÀ¸·ÎºÎÅÍ ¸¸µé¾îÁö°í, queue´Â list³ª dequeÀ¸·ÎºÎÅÍ ¸¸µé¾îÁø´Ù. stackÀ̳ª queue°¡ ´ã°í ÀÖ´Â ¿ø¼ÒµéÀº '<'¿Í '=='¿¬»êÀÚ¸¦ ¸ðµÎ ÀνÄÇØ¾ß ÇÑ´Ù. stackÀ̳ª queue´Â ¹Ýº¹ÀÚ¸¦ Á¤ÀÇÇÏ°í ÀÖÁö ¾Ê±â ¶§¹®¿¡, Çϳª¾¿ °ªµéÀ» Á¦°ÅÇغ¸Áö ¾Ê°í¼­´Â ÄÝ·º¼ÇÀÇ ¿ø¼ÒµéÀ» »ìÆ캼 ¼ö ¾ø´Ù. À̵éÀÌ ¹Ýº¹ÀÚ¸¦ ±¸ÇöÇÏ°í ÀÖÁö ¾Ê´Ù´Â »ç½ÇÀº 12Àå°ú 13Àå¿¡ ¼³¸íµÈ generic ¾Ë°í¸®µëµé Áß ¸¹Àº °ÍµéÀ» »ç¿ëÇÒ ¼ö ¾ø´Ù´Â °ÍÀ» ÀǹÌÇÑ´Ù. 10.2 stack µ¥ÀÌÅÍ Ãß»ó(data abstraction) stackÀº ÀüÅëÀûÀ¸·Î ´ÙÀ½ ¿¬»êµéÀ» ±¸ÇöÇÑ °´Ã¼·Î Á¤ÀǵǾî ÀÖ´Ù. empty() stackÀÌ ºñ¾úÀ¸¸é Âü(true)À» ¹Ýȯ size() stack¿¡ ´ã±ä ¿ø¼ÒÀÇ °¹¼ö¸¦ ¹Ýȯ top() stackÀÇ ¸Ç À§¿¡ À§Ä¡ÇÑ ¿ø¼Ò¸¦ ¹Ýȯ(Áö¿ìÁö´Â ¾Ê´Â´Ù) push(newElement) stackÀÇ ¸Ç À§¿¡ ¿ø¼Ò¸¦ »õ·Î Ãß°¡ pop() stackÀÇ ¸Ç À§¿¡ À§Ä¡ÇÑ ¿ø¼Ò¸¦ »èÁ¦(¹ÝȯÇÏÁö´Â ¾Ê´Â´Ù) 10.2.1 Include È­ÀÏ front ¿ø¼Ò¸¦ Á¢±ÙÇÏ´Â ¿¬»ê°ú »èÁ¦ÇÏ´Â ¿¬»êÀº º°µµÀÇ ¿¬»êÀ¸·Î Á¦°øµÈ´Ù´Â Á¡À» ¸í½ÉÇØ¾ß ÇÑ´Ù. stackÀ» »ç¿ëÇÏ´Â ÇÁ·Î±×·¥Àº stackÀ» ¹Ø¹ÞħÇÏ°í ÀÖ´Â ÄÁÅ×ÀÌ³Ê Å¸ÀÔ(¿¹¸¦ µé¸é, vector)¿¡ ´ëÇÑ Çì´õ È­ÀϻӸ¸¾Æ´Ï¶ó stack Çì´õÈ­ÀÏÀ» Æ÷ÇÔÇØ¾ß ÇÑ´Ù. #include #include [Image] Right Angle Brackets 10.2.2 stackÀÇ ¼±¾ð°ú ÃʱâÈ­ stackÀÇ ¼±¾ðÀº µÎ°³ÀÇ ÀÎÀÚ¸¦ ¸í½ÃÇØ¾ß ÇÑ´Ù. Çϳª´Â stackÀÌ ´ã°ÔµÉ ¿ø¼ÒÀÇ Å¸ÀÔÀÌ°í, ³ª¸ÓÁö Çϳª´Â ¿ø¼ÒµéÀ» ´ã´Âµ¥ »ç¿ëÇÒ ÄÁÅ×À̳ÊÀÌ´Ù. stackÀº ÄÁÅ×À̳ʷΠvector³ª deque¸¦ °¡Àå ¸¹ÀÌ ¾²°í, listµµ ÄÁÅ×À̳ʷΠ»ç¿ëÇÒ ¼ö ÀÖ´Ù. deque¸¦ »ç¿ëÇϸé Á» ´õ ºü¸£°í, vector¸¦ »ç¿ëÇϸé Å©±â°¡ Á» ÀÛ¾ÆÁø´Ù. ´ÙÀ½ ¿¹´Â stack¿¡ ´ëÇÑ ¼±¾ðÀÌ´Ù. stack > stackOne; stack > stackTwo; stack > stackThree; stack > stackFour; ¸¶Áö¸· ¿¹´Â ÇÁ·Î±×·¡¸Ó°¡ Á¤ÀÇÇÑ Customer ŸÀÔÀÇ stackÀ» »ý¼ºÇÑ´Ù. 10.2.3 ¿¹Á¦ ÇÁ·Î±×·¥ - RPN °è»ê±â A classic application of a stack is in the implementation of calculator. Input to the calculator consists of a text string that represents an expression written in reverse polish notation (RPN). Operands, that is, integer constants, are pushed on a stack of values. As operators are encountered, the appropriate number of operands are popped off the stack, the operation is performed, and the result is pushed back on the stack. We can divide the development of our stack simulation into two parts, a calculator engine and a calculator program. A calculator engine is concerned with the actual work involved in the simulation, but does not perform any input or output operations. The name is intended to suggest an analogy to a car engine, or a computer processor - the mechanism performs the actual work, but the user of the mechanism does not normally directly interact with it. Wrapped around this is the calculator program, which interacts with the user, and passes appropriate instructions to the calculator engine. We can use the following class definition for our calculator engine. Inside the class declaration we define an enumerated list of values to represent each of the possible operators that the calculator is prepared to accept. We have made two simplifying assumptions: all operands will be integer values, and we will handle only binary operators. class calculatorEngine { public: enum binaryOperator {plus, minus, times, divide}; int currentMemory () // return current top of stack { return data.top(); } void pushOperand (int value) // push operand value on to stack { data.push (value); } void doOperator (binaryOperator); // pop stack and perform // operator protected: stack< int, vector > data; }; [Image] Defensive Programming The member function doOperator() performs the actual work. It pops values from the stack, performs the operation, then pushes the result back onto the stack. void calculatorEngine::doOperator (binaryOperator theOp) { int right = data.top(); // read top element data.pop(); // pop it from stack int left = data.top(); // read next top element data.pop(); // pop it from stack switch (theOp) { case plus: data.push(left + right); break; case minus: data.push(left - right); break; case times: data.push(left * right); break; case divide: data.push(left / right); break; } } The main program reads values in reverse polish notation, invoking the calculator engine to do the actual work: void main() { int intval; calculatorEngine calc; char c; while (cin >> c) switch (c) { case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': cin.putback(c); cin >> intval; calc.pushOperand(intval); break; case '+': calc.doOperator(calculatorEngine::plus); break; case '-': calc.doOperator(calculatorEngine::minus); break; case '*': calc.doOperator(calculatorEngine::times); break; case '/': calc.doOperator(calculatorEngine::divide); break; case 'p': cout << calc.currentMemory() << endl; break; case 'q': return; // quit program } } 10.3 queue µ¥ÀÌÅÍ Ãß»ó(data abstraction) queue´Â ÀϹÝÀûÀ¸·Î ´ÙÀ½ ¿¬»êµéÀ» ±¸ÇöÇÑ °´Ã¼·Î¼­ Á¤ÀǵȴÙ. empty() queue°¡ ºñ¾úÀ¸¸é Âü(true)À» ¹Ýȯ size() queue¿¡ ´ã±ä ¿ø¼ÒÀÇ °¹¼ö¸¦ ¹Ýȯ front() queueÀÇ ¸Ç ¾Õ¿¡ À§Ä¡ÇÑ ¿ø¼Ò¸¦ ¹Ýȯ(»èÁ¦´Â ¾Ê´Â´Ù) back() queueÀÇ ¸Ç µÚ¿¡ À§Ä¡ÇÑ ¿ø¼Ò¸¦ ¹Ýȯ push(newElement) queueÀÇ ¸Ç µÚ¿¡ ¿ø¼Ò¸¦ »õ·Î Ãß°¡ pop() queueÀÇ ¸Ç ¾Õ¿¡ À§Ä¡ÇÑ ¿ø¼Ò¸¦ »èÁ¦(¹ÝȯÇÏÁö´Â ¾Ê´Â´Ù) 10.3.1 Include È­ÀÏ queueÀÇ ¸Ç¾Õ¿¡ À§Ä¡ÇÑ ¿ø¼Ò¸¦ Á¢±ÙÇÏ´Â ¿¬»ê°ú »èÁ¦ÇÏ´Â ¿¬»êÀº º°µµÀÇ ¿¬»êÀ¸·Î ¼öÇàµÈ´Ù´Â Á¡À» ÁÖ¸ñÇØ¾ß ÇÑ´Ù. queue¸¦ »ç¿ëÇÏ´Â ÇÁ·Î±×·¥Àº queueÀÇ ÄÁÅ×ÀÌ³Ê Å¸ÀÔ(¿¹¸¦ µé¾î, list)¿¡ ´ëÇÑ Çì´õÆÄÀϻӸ¸ ¾Æ´Ï¶ó, queue È­ÀÏÀ» Æ÷ÇÔÇØ¾ß ÇÑ´Ù. #include #include 10.3.2 queueÀÇ ¼±¾ð°ú ÃʱâÈ­ queue¿¡ ´ëÇÑ ¼±¾ðÀº °ªÀ» ´ã°í ÀÖ´Â ÄÁÅ×ÀÌ³Ê¿Í ¿ø¼Ò ŸÀÔÀ» ¸í½ÃÇØ¾ß ÇÑ´Ù. queue´Â ÄÁÅ×ÀÌ³Ê Å¸ÀÔÀ¸·Î list³ª deque¸¦ °¡Àå ¸¹ÀÌ »ç¿ëÇÑ´Ù. list¸¦ »ç¿ëÇϸé Äڵ尡 ÀÛ¾ÆÁö´Â ¹Ý¸é¿¡, deque¸¦ »ç¿ëÇϸé Äڵ尡 Á» »¡¶óÁø´Ù. ´ÙÀ½Àº queue¸¦ ¼±¾ðÇÏ´Â ¿¹ÀÌ´Ù. queue > queueOne; queue > queueTwo; queue > queueThree; queue > queueFour; ¸¶Áö¸· ¿¹´Â ÇÁ·Î±×·¡¸Ó°¡ Á¤ÀÇÇÑ CustomerÀÇ queue¸¦ »ý¼ºÇÑ´Ù. stack ÄÁÅ×À̳ʿ¡¼­ ó·³, queue¿¡ ÀúÀåµÈ ¸ðµç °´Ã¼´Â '<'¿Í '==' ¿¬»êÀÚ¸¦ ÀÌÇØÇØ¾ß ÇÑ´Ù. queue´Â ¹Ýº¹ÀÚ¸¦ ±¸ÇöÇÏÁö ¾Ê±â ¶§¹®¿¡, 13Àý°ú 14Àý¿¡¼­ ¼³¸íÇÏ´Â generic ¾Ë°í¸®µëµéÀº queue¿¡ Àû¿ëÇÒ ¼ö ¾ø´Ù. 10.3.3 ¿¹Á¦ ÇÁ·Î±×·¥ - Bank Teller ½Ã¹Ä·¹ÀÌ¼Ç Queues are often found in businesses, such as supermarkets or banks. Suppose you are the manager of a bank, and you need to determine how many tellers to have working during certain hours. You decide to create a computer simulation, basing your simulation on certain observed behavior. For example, you note that during peak hours there is a ninety percent chance that a customer will arrive every minute. We create a simulation by first defining objects to represent both customers and tellers. For customers, the information we wish to know is the average amount of time they spend waiting in line. Thus, customer objects simply maintain two integer data fields: the time they arrive in line, and the time they will spend at the counter. The latter is a value randomly selected between 2 and 8. (See Section 2.2.5 for a discussion of the randomInteger() function.) class Customer { public: Customer (int at = 0) : arrival_Time(at), processTime(2 + randomInteger(6)) {} int arrival_Time; int processTime; bool done() // are we done with our transaction? { return --processTime < 0; } operator < (const Customer & c) // order by arrival time { return arrival_Time < c.arrival_Time; } operator == (const Customer & c) // no two customers are alike { return false; } }; Because objects can only be stored in standard library containers if they can be compared for equality and ordering, it is necessary to define the < and == operators for customers. Customers can also tell us when they are done with their transactions. Tellers are either busy servicing customers, or they are free. Thus, each teller value holds two data fields; a customer, and a boolean flag. Tellers define a member function to answer whether they are free or not, as well as a member function that is invoked when they start servicing a customer. class Teller { public: Teller() { free = true; } bool isFree() // are we free to service new customer? { if (free) return true; if (customer.done()) free = true; return free; } void addCustomer(Customer c) // start serving new customer { customer = c; free = false; } private: bool free; Customer customer; }; The main program is then a large loop, cycling once each simulated minute. Each minute a new customer is, with probability 0.9, entered into the queue of waiting customers. Each teller is polled, and if any are free they take the next customer from the queue. Counts are maintained of the number of customers serviced and the total time they spent in queue. From these two values we can determine, following the simulation, the average time a customer spent waiting in the line. void main() { int numberOfTellers = 5; int numberOfMinutes = 60; double totalWait = 0; int numberOfCustomers = 0; vector teller(numberOfTellers); queue< Customer, deque > line; for (int time = 0; time < numberOfMinutes; time++) { if (randomInteger(10) < 9) line.push(Customer(time)); for (int i = 0; i < numberOfTellers; i++) { if (teller[i].isFree() & ! line.empty()) { Customer & frontCustomer = line.front(); numberOfCustomers++; totalWait += (time - frontCustomer.arrival_Time); teller[i].addCustomer(frontCustomer); line.pop(); } } } cout << "average wait:" << (totalWait / numberOfCustomers) << endl; } By executing the program several times, using various values for the number of tellers, the manager can determine the smallest number of tellers that can service the customers while maintaining the average waiting time at an acceptable amount.