7.1 deque µ¥ÀÌÅÍ Ãß»ó(data abstraction) dequeÀº `double-ended queue'ÀÇ ¾àÀÚÀÌ°í, `µ¦(deck)'À̶ó°í ¹ßÀ½ÇÑ´Ù. ÀüÅëÀûÀ¸·Î, ÀÌ ¿ë¾î´Â ÄÝ·º¼ÇÀÇ ¾Õ°ú µÚ ¾î´À °÷¿¡¼­³ª »ðÀÔ°ú »èÁ¦°¡ °¡´ÉÇÑ µ¥ÀÌÅÍ ±¸Á¶µéÀ» ÁöĪÇϴµ¥ »ç¿ëµÇ¾ú´Ù. deque ÄÁÅ×ÀÌ³Ê Å¬·¡½º´Â À̰ͻӸ¸ ¾Æ´Ï¶ó ´õ ¸¹Àº °ÍÀ» ÇÒ ¼ö ÀÖ´Ù. ½ÇÁ¦·Î, deque µ¥ÀÌÅÍ ±¸Á¶ÀÇ ´É·ÂÀº vector Ŭ·¡½º¿Í list Ŭ·¡½º°¡ Á¦°øÇÏ´Â °ÍµéÀ» ¸ðµÎ Æ÷ÇÔÇÑ´Ù. * vector¿Í °°ÀÌ dequeÀº À妽ÌÀÌ °¡´ÉÇÏ´Ù. ÄÝ·º¼Ç ³»¿¡¼­ÀÇ À§Ä¡¸¦ Å°·Î »ç¿ëÇÔÀ¸·Î½á, ÷ÀÚ·Î °ªµéÀ» Á¢±ÙÇÒ ¼ö ÀÖ´Ù.(ÀÌ´Â list Ŭ·¡½º°¡ Á¦°øÇÏÁö ¾Ê´Â ±â´ÉÀÌ´Ù.) * list¿Í °°ÀÌ dequeÀÇ ¾Õ°ú µÚ¿¡ °ªÀ» È¿À²ÀûÀ¸·Î Ãß°¡ÇÒ ¼ö ÀÖ´Ù.(vector Ŭ·¡½º¿¡ ÀÇÇؼ­ ºÎºÐÀûÀ¸·Î¸¸ Á¦°øµÇ´Â ±â´ÉÀÌ´Ù.) * list¿Í vector Ŭ·¡½º¿¡¼­¿Í °°ÀÌ, deque°¡ °ü¸®ÇÏ´Â ½ÃÄö½ºÀÇ Áß°£¿¡¼­ °ªµéÀ» »ðÀÔÇÒ ¼ö ÀÖ´Ù. ÀÌ·¯ÇÑ »ðÀÔ ¿¬»êÀº list¸¸Å­ È¿À²ÀûÀÌÁö¸¸, vectorº¸´Ù´Â Á¶±Ý ´õ È¿À²ÀûÀÌ´Ù. °£´ÜÈ÷ ¸»Çؼ­, dequeÀº vector¿Í list¸¦ ÇÊ¿ä·Î ÇÏ´Â °÷¿¡¼­ ¸ðµÎ »ç¿ëÇÒ ¼ö ÀÖ´Ù. vector¿Í list ´ë½Å¿¡ deque¸¦ »ç¿ëÇÏ°Ô µÇ¸é, Á¾Á¾ ÇÁ·Î±×·¥ÀÌ ´õ »¡¶óÁø´Ù. ¾î´À µ¥ÀÌÅÍ ±¸Á¶¸¦ Á¤ÇÒÁö´Â 4.2ÀýÀ» Âü°íÇϱ⠹ٶõ´Ù. 7.1.1 Include È­ÀÏ deque µ¥ÀÌÅÍ Å¸ÀÔÀ» »ç¿ëÇÏ´Â ÇÁ·Î±×·¥Àº ¸ðµÎ deque Çì´õ È­ÀÏÀ» »ç¿ëÇØ¾ß ÇÑ´Ù. #include 7.2 deque ¿¬»ê deque´Â vector¿Í °°Àº ¹æ½ÄÀ¸·Î ¼±¾ðÇÏ°í, Ŭ·¡½º ³»ºÎ¿¡´Â vector¿Í µ¿ÀÏÇÑ Å¸ÀÔ Á¤ÀǸ¦ °¡Áö°í ÀÖ´Ù. begin()°ú end() ¸â¹ö ÇÔ¼ö´Â ¾ç¹æÇ⠹ݺ¹ÀÚ¸¦ Á¦°øÇÏ´Â ¸®½ºÆ®¿Í´Â ´Þ¸®, ÀÓÀÇÁ¢±Ù ¹Ýº¹ÀÚ¸¦ ¸®ÅÏÇÑ´Ù. »ðÀÔ(insert(), push_front(), push_back())Àº dequeÀÇ ¿ø¼Ò¸¦ °¡¸®Å°´Â ¹Ýº¹ÀÚ³ª ·¹ÆÛ·±½ºµéÀ» ¹«È¿È­½Ãų ¼öµµ ÀÖ´Ù. ÀÌ´Â vector µ¥ÀÌÅÍ Å¸ÀÔ°ú °°ÀÌ list¿¡¼­ÀÇ »ðÀÔº¸´Ù ´õ Á¦ÇÑÀûÀÌ´Ù. deque³»ÀÇ ¿ø¼Ò ŸÀÔ¿¡ ¼Ò¸êÀÚ°¡ Á¤ÀǵǾî ÀÖ´Ù¸é, deque·ÎºÎÅÍ ¿ø¼Ò¸¦ »èÁ¦ÇÒ ¶§, ÀÌ ¼Ò¸êÀÚ°¡ È£ÃâµÉ °ÍÀÌ´Ù. deque µ¥ÀÌÅÍ Å¸ÀÔÀÌ ÀÓÀÇÁ¢±Ù ¹Ýº¹ÀÚ¸¦ Á¦°øÇϱ⠶§¹®¿¡, vector¿¡ Àû¿ëµÇ´Â ¸ðµç generic ¾Ë°í¸®µëÀº deque¿¡µµ »ç¿ëµÉ ¼ö ÀÖ´Ù. vector´Â Ä¿´Ù¶õ ÇϳªÀÇ ¸Þ¸ð¸® ºí·°¿¡ ¿ø¼ÒµéÀ» °¡Áö°í ÀÖ´Â ¹Ý¸é, dequeÀº ¸¹Àº ¼öÀÇ Á»´õ ÀÛÀº ºí·°µéÀ» »ç¿ëÇÑ´Ù. ¸Þ¸ð¸® ºí·°ÀÇ »çÀÌÁî¿¡ Á¦ÇÑÀ» µÎ°í ÀÖ´Â ½Ã½ºÅÛ¿¡¼­ ÀÌ´Â ¸Å¿ì Áß¿äÇÑ »çÇ×À̸ç, ÀÌ·¯ÇÑ ÀÌÀ¯¶§¹®¿¡ dequeÀº vectorº¸´Ù ´õ ¸¹Àº ¿ø¼ÒµéÀ» Æ÷ÇÔÇÒ ¼ö ÀÖ´Ù. °ªµéÀ» »ðÀÔÇÒ ¶§´Â, ÄÝ·º¼Ç³»ÀÇ ¿ø¼Ò¿Í ¿¬°áµÇ¾î ÀÖ´ø À妽º°¡ ¹Ù²î°Ô µÈ´Ù. ¿¹¸¦ µé¾î, 3¹ø À§Ä¡¿¡ °ªÀ» »ðÀÔÇϸé, ¿ø·¡ 3¹ø ÀÚ¸®¿¡ ÀÖ´ø °ªÀº 4¹øÀÚ¸®¸¦ Â÷ÁöÇÏ°Ô µÇ°í, 4¹ø ÀÚ¸®¿¡ ÀÖ´ø °ªÀº 5¹øÀÚ¸®·Î Â÷·Ê·Î ¿Å°ÜÁö°Ô µÈ´Ù. .3 ¿¹Á¦ ÇÁ·Î±×·¥ - Radix Sort The radix sort algorithm is a good illustration of how lists and deques can be combined with other containers. In the case of radix sort, a vector of deques is manipulated, much like a hash table. Radix sorting is a technique for ordering a list of positive integer values. The values are successively ordered on digit positions, from right to left. This is accomplished by copying the values into "buckets," where the index for the bucket is given by the position of the digit being sorted. Once all digit positions have been examined, the list must be sorted. The following table shows the sequences of values found in each bucket during the four steps involved in sorting the list 624 852 426 987 269 146 415 301 730 78 593. During pass 1 the ones place digits are ordered. During pass 2 the tens place digits are ordered, retaining the relative positions of values set by the earlier pass. On pass 3 the hundreds place digits are ordered, again retaining the previous relative ordering. After three passes the result is an ordered list. bucket pass 1 pass 2 pass 3 0 730 301 78 1 301 415 146 2 852 624, 426 269 3 593 730 301 4 624 146 415, 426 5 415 852 593 6 426, 146 269 624 7 987 78 730 8 78 987 852 9 269 593 987 The radix sorting algorithm is simple. A while loop is used to cycle through the various passes. The value of the variable divisor indicates which digit is currently being examined. A boolean flag is used to determine when execution should halt. Each time the while loop is executed a vector of deques is declared. By placing the declaration of this structure inside the while loop, it is reinitialized to empty each step. Each time the loop is executed, the values in the list are copied into the appropriate bucket by executing the function copyIntoBuckets() on each value. Once distributed into the buckets, the values are gathered back into the list by means of an accumulation. void radixSort(list & values) { bool flag = true; int divisor = 1; while (flag) { vector< deque > buckets(10); flag = false; for_each(values.begin(), values.end(), copyIntoBuckets(...)); accumulate(buckets.begin(), buckets.end(), values.begin(), listCopy); divisor *= 10; } } The use of the function accumulate() here is slightly unusual. The "scalar" value being constructed is the list itself. The initial value for the accumulation is the iterator denoting the beginning of the list. Each bucket is processed by the following binary function: list::iterator listCopy(list::iterator c, deque & lst) { // copy list back into original list, returning end return copy(lst.begin(), lst.end(), c); } The only difficulty remaining is defining the function copyIntoBuckets(). The problem here is that the function must take as its argument only the element being inserted, but it must also have access to the three values buckets, divisor and flag. In languages that permit functions to be defined within other functions the solution would be to define copyIntoBuckets() as a local function within the while loop. But C++ has no such facilities. Instead, we must create a class definition, which can be initialized with references to the appropriate values. The parenthesis operator for this class is then used as the function for the for_each() invocation in the radix sort program. class copyIntoBuckets { public: copyIntoBuckets (int d, vector< deque > & b, bool & f) : divisor(d), buckets(b), flag(f) {} int divisor; vector > & buckets; bool & flag; void operator () (unsigned int v) { int index = (v / divisor) % 10; // flag is set to true if any bucket // other than zeroth is used if (index) flag = true; buckets[index].push_back(v); } };