40-2-¸¶.µ¥Å©

µ¥Å©(Deque)´Â ¾çÂÊ ³¡ÀÌ Àִ ťÀÌ¸ç ¾ç ³¡¿¡¼­ ÀڷḦ »ðÀÔ, »èÁ¦ÇÒ ¼ö ÀÖ´Ù. ÄÄÆÄÀÏ·¯¿¡ µû¶ó µ¥Å©ÀÇ ±¸Çö ¹æ½ÄÀÌ ´Ù¸£°ÚÁö¸¸ ÁÖ·Î ¸Þ¸ð¸® ºí·ÏÀ» ÇÒ´çÇÏ¿© ¿¬°áÇØ ³õ°í ¾çÂÊ ³¡À¸·Î Ãß°¡ ÇÒ´çÇØ ³ª°¡´Â ¹æ½ÄÀ¸·Î ±¸ÇöµÈ´Ù. ½ÇÁ¦ ±¸ÇöÀ» º¸°í ½Í´Ù¸é »ç¿ë ÄÄÆÄÀÏ·¯ÀÇ deque Çì´õ ÆÄÀÏÀ» ÀÐ¾î º¸¸é µÉ °ÍÀÌ´Ù. º¤ÅÍ¿Í ºñ½ÁÇÑ Æ¯¼ºÀ» °¡Áö´Âµ¥ ¾çÂÊ¿¡ ³¡ÀÌ ÀÖÀ¸¹Ç·Î ¾ÕÂÊ¿¡¼­µµ »ðÀÔ, »èÁ¦°¡ ºü¸£´Ù. ±×·¯³ª ÀÌ´Â ±â´É»óÀÇ Â÷ÀÌ´Â ¾Æ´Ï¸ç ¼Óµµ»óÀÇ Â÷ÀÌÀÏ »ÓÀε¥ º¤Å͵µ insert¸¦ »ç¿ëÇϸé Á» ´À¸®±â´Â ÇÏÁö¸¸ ¾ÕÂÊ¿¡¼­ »ðÀÔ, »èÁ¦°¡ °¡´ÉÇÏ´Ù.

¾ÕÂÊ¿¡¼­µµ ÀÚ·áÀÇ Ã·»èÀÌ °¡´ÉÇϹǷΠº¤ÅÍ¿¡ ºñÇØpush_front, pop_font ÇÔ¼ö°¡ Ãß°¡·Î Á¦°øµÈ´Ù. ´ë½Å ¼º´É Çâ»óÀ» À§ÇØ ¹Ì¸® ¸Þ¸ð¸®¸¦ Ãß°¡ È®º¸ÇØ ³õÀ» ÇÊ¿ä°¡ ¾øÀ¸¹Ç·Î reserve ÇÔ¼ö°¡ ºÒÇÊ¿äÇϸç È®º¸ÇØ ³õÀº ¿ë·®À» Á¶»çÇÏ´Â capacity ÇÔ¼öµµ ÇÊ¿ä°¡ ¾ø´Ù. ±×¸®°í ³»ºÎ ±¸Á¶°¡ ´Ù¸§À¸·Î ÀÎÇØ »ðÀÔ, »èÁ¦½ÃÀÇ ¹Ýº¹ÀÚ ¹«È¿È­ ±ÔÄ¢µµ Â÷ÀÌ°¡ ³­´Ù.

¾ÕÂÊ¿¡¼­ÀÇ »ðÀÔ, »èÁ¦°¡ º¤Åͺ¸´Ù ÈξÀ ºü¸£´Ù´Â ÀÌÁ¡ÀÌ ÀÖ´Â ´ë½Å ³ª¸ÓÁö ¿¬»êµéÀº º¤Åͺ¸´Ù ÀϹÝÀûÀ¸·Î ´À¸®´Ù. Á¶ÀÛ À§Ä¡¿¡ µû¶ó ¾à°£ÀÇ ¼ÓµµÂ÷¸¸ ÀÖÀ» »ÓÀ̹ǷΠ¹éÅÍ¿Í µ¥Å©´Â ±â´ÉÀûÀ¸·Î ¿ÏÀüÈ÷ ´ëü °¡´ÉÇÏ´Ù. ¾Õ Àý¿¡¼­ º¤ÅÍ·Î ¸¸µç ¿¹Á¦µéÀº °ÅÀÇ ´ëºÎºÐ º°´Ù¸¥ ¼öÁ¤¾øÀÌ µ¥Å©·Î ¹Ù²Ü ¼ö Àִµ¥ ¼Ò½ºÀÇ vector¸¸ deque·Î ¹Ù²Ù¸é µÈ´Ù. ÁÖ·Î µÚÂÊ¿¡ Ãß°¡¸¸ ÇÑ´Ù¸é º¤ÅÍ°¡ Ź¿ùÇÑ ¼±ÅÃÀÌ¸ç ¾çÂÊ¿¡¼­ Ãß°¡, »èÁ¦°¡ ¹ß»ýÇÏ¸é µ¥Å©°¡ ´õ ÀûÇÕÇÏ´Ù.

º¤ÅÍ¿Í ¸¶Âù°¡Áö·Î ÀÓÀÇ Á¢±Ù ¹Ýº¹ÀÚ¸¦ Áö¿øÇÏ¿© STLÀÇ ¸ðµç ¾Ë°í¸®Áò°úµµ °°ÀÌ »ç¿ëÇÒ ¼ö ÀÖÀ¸¸ç [ ] ¿¬»êÀÚ·Î ÀÓÀÇ À§Ä¡¸¦ ¾×¼¼½ºÇÏ´Â °Íµµ °¡´ÉÇÏ´Ù. Á¦°øÇÏ´Â ÇÔ¼öµéÀÇ ¸ñ·Ï°ú »ç¿ë ¹æ¹ýµµ º¤ÅÍ¿Í °ÅÀÇ µ¿ÀÏÇÏ´Ù. »ý¼ºÀÚ´Â ¿ÏÀüÈ÷ °°À¸¸ç ¿¬»êÀÚ¿Í insert, delete µîÀÇ ÇÔ¼öµéµµ µ¿ÀÏÇÏ´Ù. °£´ÜÇÑ ¿¹Á¦·Î µ¥Å©¸¦ Å×½ºÆ®ÇØ º¸ÀÚ.

 

¿¹ Á¦ : deque

#include <iostream>

#include <deque>

using namespace std;

 

void main()

{

     deque<int> dq;

     dq.push_back(8);

     dq.push_back(9);

     dq.push_front(2);

     dq.push_front(1);

     for (unsigned i=0;i<dq.size();i++) { cout << dq[i]; }

}

 

µ¥Å©¸¦ »ç¿ëÇϱâ À§ÇØ Çì´õ ÆÄÀÏ deque¸¦ ÀÎŬ·çµåÇß´Ù. ¾Õ¿¡¼­ ¸¸µé¾ú´ø ¸®½ºÆ® ¿¹Á¦¿Í µ¿ÀÏÇÏ¸ç ¾Õ µÚ¿¡¼­ ¸¶À½´ë·Î ¿ä¼Ò¸¦ ÷»èÇÒ ¼ö ÀÖ´Ù. ´Ù¸¸ ÀÓÀÇ Á¢±ÙÀÌ °¡´ÉÇϹǷΠ¹Ýº¹ÀÚ¸¦ ¾µ ÇÊ¿ä¾øÀÌ [ ] ¿¬»êÀÚ·Î ¿øÇÏ´Â ¿ä¼Ò¸¦ ¹Ù·Î ÀÐÀ» ¼ö ÀÖ´Ù.