19-3.½ºÅÃ

19-3-°¡.½ºÅÃ

½ºÅÃÀº LIFO(Last In First Out)ÀÇ ¿ø¸®·Î µ¿ÀÛÇÏ´Â ¼±ÇüÀûÀÎ ÀÚ·á ±¸Á¶ÀÌ´Ù. °°Àº ŸÀÔÀÇ ÀÚ·á ÁýÇÕÀ» °ü¸®ÇÑ´Ù´Â ¸é¿¡¼­´Â ¹è¿­À̳ª ¿¬°á ¸®½ºÆ®¿Í µ¿ÀÏÇÏÁö¸¸ ÀڷḦ °ü¸®ÇÏ´Â ¹æ½ÄÀÌ ¹Ì¸® Á¤ÇØÁ® ÀÖ´Ù´Â Á¡ÀÌ ´Ù¸£´Ù. ½ºÅÃÀº µ¥ÀÌÅÍ°¡ µé¾î°¡°í ³ª¿À´Â ÀÔ±¸°¡ Çϳª»ÓÀ̹ǷΠÀÔ±¸·Î µé¾î°£ µ¥ÀÌÅÍ°¡ ½ºÅÿ¡ Â÷°îÂ÷°î ½×¿© ÀÖ´Ù°¡ µé¾î°£ ¹Ý´ë ¼ø¼­·Î ³ª¿Â´Ù. ÁÖ·Î °è»êÁß¿¡ Àá½Ã ±â¾ïÇØ¾ß ÇÏ´Â ÀÓ½ÃÀûÀÎ ÀڷḦ °ü¸®ÇÏ´Â ¿ëµµ·Î »ç¿ëµÈ´Ù.

CPUµµ ¿©·¯ °¡Áö Á¤º¸¸¦ ÀúÀåÇϱâ À§ÇØ ½ºÅÃÀ» »ç¿ëÇϴµ¥ À̸¦ ½Ã½ºÅÛ ½ºÅÃÀ̶ó ÇÑ´Ù. ½Ã½ºÅÛ ½ºÅÿ¡´Â ÇÔ¼ö·Î Àü´ÞµÇ´Â Àμö, Áö¿ªº¯¼ö µîÀÇ Àӽà º¯¼öµéÀÌ ÀúÀåµÇ°í ÇÔ¼ö ½ÇÇà ÈÄ µ¹¾Æ°¥ º¹±Í ¹øÁöµµ ÀúÀåµÈ´Ù. ÀÌ ³»¿ëÀº ½ºÅà ÇÁ·¹ÀÓÀ» °øºÎÇÒ ¶§ ÀÌ¹Ì »ìÆ캻 ÀûÀÌ ÀÖ´Ù. ¶ÇÇÑ ÇÔ¼ö ½ÇÇàÁß¿¡ ÇÊ¿äÇÑ Àӽà Á¤º¸µéµµ ½ºÅÿ¡ ÀúÀåµÇ´Âµ¥ ÁÖ·Î ·¹Áö½ºÅÍ°ªÀ» ´ëÇǽÃÅ°´Â ¿ëµµ·Î »ç¿ëÇÑ´Ù. CPUÀÇ ·¹Áö½ºÅÍ °³¼ö°¡ ¸¹Áö ¾Ê±â ¶§¹®¿¡ ÀÌ¹Ì »ç¿ëÁßÀÎ ·¹Áö½ºÅ͸¦ ´Ù¸¥ ¿ëµµ·Î ¾²°í ½ÍÀ» ¶§´Â ½ºÅÿ¡ Àá½Ã ÀúÀåÇØ µÎ°í »ç¿ëÇÑ ÈÄ ´Ù½Ã ¿ø·¡°ªÀ» ²¨³» º¹±¸ÇÑ´Ù.

½Ã½ºÅÛ ½ºÅÃÀº CPU°¡ Á÷Á¢ »ç¿ëÇÏ´Â Àå¼ÒÀ̹ǷΠÀÀ¿ë ÇÁ·Î±×·¥Àº ¿©±â¿¡ ÀÚ½ÅÀÇ µ¥ÀÌÅ͸¦ ÀúÀåÇÒ ¼ö ¾ø´Ù. ²À ½Ã½ºÅÛ ½ºÅÃÀ» ¾²°íÀÚ ÇÑ´Ù¸é ºÒ°¡´ÉÇÑ °ÍÀº ¾Æ´ÏÁö¸¸ ¾î¼Àºí¸® ÄÚµå·Î¸¸ ½ºÅÃÀ» »ç¿ëÇÒ ¼ö ÀÖ°í ±ÔÄ¢À» ¹Ýµå½Ã ÁöÄÑ¾ß ÇϹǷΠ¹«Ã´ ºÎ´ã½º·´´Ù. º°µµÀÇ ½ºÅÃÀÌ ÇÊ¿äÇÏ´Ù¸é Çϵå¿þ¾î ½ºÅðú ¶È°°ÀÌ µ¿ÀÛÇÏ´Â ¼ÒÇÁÆ®¿þ¾î ½ºÅÃÀ» ¸¸µé ¼ö ÀÖ´Ù. ´ÙÀ½ ¿¹Á¦´Â ¹è¿­·Î Á¤¼öÇü ½ºÅÃÀ» ±¸ÇöÇÑ °ÍÀÌ´Ù.

 

¿¹ Á¦ : Stack

#include <Turboc.h>

 

int *Stack;

int Size;

int Top;

 

void InitStack(int aSize)

{

     Size=aSize;

     Stack=(int *)malloc(Size*sizeof(int));

     Top=-1;

}

 

void FreeStack()

{

     free(Stack);

}

 

BOOL Push(int data)

{

     if (Top < Size-1) {

          Top++;

          Stack[Top]=data;

          return TRUE;

     } else {

          return FALSE;

     }

}

 

int Pop()

{

     if (Top >= 0) {

          return Stack[Top--];

     } else {

          return -1;

     }

}

 

void main()

{

     InitStack(256);

     Push(7);

     Push(0);

     Push(6);

     Push(2);

     Push(9);

     printf("%d\n",Pop());

     printf("%d\n",Pop());

     printf("%d\n",Pop());

     printf("%d\n",Pop());

     printf("%d\n",Pop());

     FreeStack();

}

 

½ºÅÃÀ» ±¸ÇöÇϱâ À§Çؼ­´Â ¼¼ °³ÀÇ º¯¼ö°¡ ÇÊ¿äÇÏ´Ù. StackÀº µ¥ÀÌÅ͸¦ ÀúÀåÇÒ ÀúÀå¼ÒÀε¥ ÇÊ¿äÇѸ¸Å­ µ¿ÀûÀ¸·Î ÇÒ´çÇϱâ À§ÇØ Æ÷ÀÎÅÍ·Î ¼±¾ðÇß´Ù. ½ºÅÿ¡ ÀúÀåÇÒ µ¥ÀÌÅÍ¿Í °°Àº ŸÀÔÀÇ Æ÷ÀÎÅ͸¦ ¼±¾ðÇϸé ÀÌ Æ÷ÀÎÅÍ°¡ °ð ½ºÅÃÀÌ µÈ´Ù. ¿¹Á¦¿¡¼­´Â Á¤¼öÇü Æ÷ÀÎÅ͸¦ ¼±¾ðÇßÀ¸¹Ç·Î ÀÌ ½ºÅÃÀº Á¤¼ö¸¦ ÀúÀåÇÏ´Â ½ºÅÃÀÌ µÇ´Âµ¥ ÀÓÀÇÀÇ ¸ðµç ŸÀÔ¿¡ ´ëÇÑ ½ºÅÃÀ» ¸¸µé ¼ö ÀÖ´Ù. ¹®ÀÚ, ½Ç¼ö´Â ¹°·ÐÀÌ°í ±¸Á¶Ã¼°°Àº Å« ŸÀÔµµ ¹°·Ð °¡´ÉÇÏ´Ù. Size´Â ½ºÅÃÀÇ ÇÒ´ç Å©±âÀÌ´Ù. TopÀº ½ºÅÃÀÇ ÇöÀç À§Ä¡¸¦ °¡¸®Å°´Â °ªÀÌ¸ç ½ºÅÃÀÇ ¾îµð±îÁö Â÷ ÀÖ´ÂÁö¸¦ ±â¾ïÇÑ´Ù.

InitStack ÇÔ¼ö´Â ½ºÅÃÀ» ÃʱâÈ­Çϴµ¥ Àμö·Î Àü´ÞµÈ aSize¸¦ Size¿¡ ´ëÀÔÇØ ³õ°í Size Å©±â¸¸Å­ ¸Þ¸ð¸®¸¦ ÇÒ´çÇÏ¿© Stack Æ÷ÀÎÅÍ¿¡ ´ëÀÔÇÑ´Ù. µû¶ó¼­ StackÀº Size Å©±âÀÇ Á¤¼öÇü ¹è¿­ÀÌ µÇ¸ç Size°³ÀÇ Á¤¼ö¸¦ ÀúÀåÇÒ ¼ö ÀÖ´Ù. Á¤Àû ¹è¿­·Îµµ ½ºÅÃÀ» ±¸ÇöÇÒ ¼ö ÀÖÁö¸¸ ÀÌ·¸°Ô Çϸé Å©±â°¡ °íÁ¤µÇ¾î ¹ö¸°´Ù. µ¿ÀûÀ¸·Î ÇÒ´çÇÏ¸é ½ºÅÃÀ» ¾²´Â ÂÊ¿¡¼­ ÇÊ¿äÇÑ Å©±â¸¦ °áÁ¤ÇÒ ¼ö Àִµ¥ ÇÊ¿äÇÑ ÃÖ´ë Å©±â·Î Àâ´Â °ÍÀÌ ÁÁ´Ù. ÃÖÃÊ ½ºÅÿ¡´Â ¾Æ¹«·± µ¥ÀÌÅÍ°¡ µé¾î ÀÖÁö ¾ÊÀ¸¹Ç·Î TopÀº ºñ¾î ÀÖ´Ù´Â ¶æÀÇ -1·Î ÃʱâÈ­ÇÑ´Ù. ¹è¿­ÀÌ 0ºÎÅÍ ½ÃÀÛÇϱ⠶§¹®¿¡ 0Àº ÀÚ·á°¡ ¾ø´Â »óÅ°¡ ¾Æ´Ï¶ó Çϳª µé¾î ÀÖ´Â »óÅÂÀ̹ǷΠºñ¾î ÀÖ´Â °Í°ú´Â ´Ù¸£´Ù. FreeStack ÇÔ¼ö´Â ½ºÅÃÀ» Æı«Çϴµ¥ µ¿ÀûÀ¸·Î ÇÒ´çµÈ ¸Þ¸ð¸®¸¸ ÇØÁ¦ÇÏ¸é µÈ´Ù.

½ºÅÿ¡ µ¥ÀÌÅ͸¦ ÀúÀåÇÏ´Â µ¿ÀÛÀ» Ǫ½Ã¶ó°í ÇÑ´Ù. PushÇÔ¼ö´Â µ¥ÀÌÅÍ°¡ µé¾î ÀÖ´Â TopÀ» 1Áõ°¡½ÃŲ ÈÄ ÀÌ ÀÚ¸®¿¡ Àμö·Î Àü´ÞµÈ data¸¦ Áý¾î ³Ö´Â´Ù. Ǫ½Ã µ¿ÀÛÀº Top Áõ°¡, ±×¸®°í Top¿¡ data ´ëÀÔ µÎ µ¿ÀÛ¸¸À¸·Î ±¸ÇöµÈ´Ù. ³ª¸ÓÁö ÄÚµå´Â ¿¡·¯ ó¸® ÄÚµåÀε¥ ½ºÅÃÀÇ Å©±â°¡ ¹«ÇÑÇÏÁö ¾Ê±â ¶§¹®¿¡ °¡µæÂ÷ ÀÖ´ÂÁö¸¦ Á¡°ËÇÏ´Â °ÍÀÌ´Ù.

Push´Â ÇÒ´çµÈ ½ºÅà ũ±â¿Í TopÀ» ºñ±³ÇÏ¿© TopÀÌ ½ºÅÃÀÇ ¸¶Áö¸· ¿ä¼Òº¸´Ù ÀÛÀ» ¶§¸¸ Ǫ½ÃÇÑ´Ù. ½ºÅÃÀÌ °¡µæ Â÷¼­ ´õ µ¥ÀÌÅ͸¦ »ðÀÔÇÒ ¼ö ¾ø´Â »óŸ¦ ½ºÅà ¿À¹öÇ÷οì¶ó°í Çϴµ¥ À̶§´Â »ðÀÔÀ» ÁßÁöÇÏ°í ¿¡·¯¸¦ ¸®ÅÏÇÑ´Ù. realloc ÇÔ¼ö·Î ÀçÇÒ´çÇϸé ÇÊ¿äÇѸ¸Å­ ½ºÅà ũ±â¸¦ ´õ ´ÃÀÌ´Â °Íµµ °¡´ÉÇÏÁö¸¸ ÀϹÝÀûÀ¸·Î ½ºÅÃÀº °íÁ¤µÈ Å©±â¸¦ °¡Áö´Â °ÍÀÌ º¸ÅëÀ̹ǷΠÀçÇÒ´çÇÏÁö´Â ¾Ê¾Ò´Ù. ±×·¡¼­ ½ºÅÃÀº ³Ë³ËÇÑ Å©±â·Î ÃæºÐÈ÷ ¿©À¯ÀÖ°Ô Àâ¾Æ¾ß ÇÑ´Ù. ½ºÅà ¿À¹öÇ÷οì´Â ±â¾ï Àå¼ÒÀÇ ºÎÁ·º¸´Ù´Â ¹«ÇÑ ·çÇÁ µîÀÇ ³í¸®ÀûÀÎ ¿À·ù·Î ÀÎÇØ ¹ß»ýÇÏ´Â °æ¿ì°¡ ´õ ¸¹À¸¹Ç·Î ¿¡·¯¸¦ ¸®ÅÏÇÏ´Â ÆíÀÌ ´õ ¾ÈÀüÇÏ´Ù.

½ºÅÿ¡ ÀúÀåÇÑ °ªÀ» »© ³»´Â °ÍÀ» ÆËÀ̶ó°í Çϴµ¥ ÀÌ µ¿ÀÛµµ ¾ÆÁÖ °£´ÜÇÏ´Ù. Top À§Ä¡ÀÇ °ªÀ» Àаí TopÀº Çϳª °¨¼Ò½ÃŲ´Ù. ½ºÅÃÀÌ ÅÖ ºñ¾î¼­ ´õ ²¨³¾ µ¥ÀÌÅÍ°¡ ¾ø´Â »óŸ¦ ½ºÅà ¾ð´õÇ÷οì¶ó°í Çϴµ¥ À̶§´Â -1À̶ó´Â ¿¡·¯°ªÀ» ¸®ÅÏÇϵµ·Ï Çß´Ù. ÀÌ·¸°Ô µÇ¸é ½ºÅÿ¡¼­ ²¨³½ °ªÀÌ ÁøÂ¥ -1ÀÎ °æ¿ì¿Í ±¸ºÐµÇÁö ¾Ê´Â ¸ðÈ£ÇÔÀÌ ÀÖÀ¸¹Ç·Î ¿¡·¯°ªÀ» Á» ´õ ƯÀÌÇÑ °ª(¿¹:-101092)À¸·Î ¼±ÅÃÇϰųª ¾Æ´Ï¸é º°µµÀÇ Ãâ·Â¿ë Àμö¸¦ »ç¿ëÇÒ ¼öµµ ÀÖ´Ù. ½ºÅÃÀº Ǫ½Ã¿Í ÆËÀ» Á¤È®ÇÏ°Ô ¸ÂÃç¾ß ÇϹǷΠ½ºÅà ¾ð´õÇ÷οì´Â Àý´ë·Î ¹ß»ýÇؼ­´Â ¾ÈµÇ´Â ¿¡·¯ÀÌ´Ù. µû¶ó¼­ ¿¡·¯ 󸮸¦ ÇÏ´Â °Íº¸´Ù´Â assert(Top >=0)·Î ó¸®ÇÏ´Â °ÍÀÌ ´õ ¹Ù¶÷Á÷ÇÏ´Ù.

Ǫ½Ã¿Í ÆË µ¿ÀÛ¿¡¼­ º¸´Ù½ÃÇÇ TopÀº ½ºÅÃÀÇ ÃÖ»ó´ÜÀ» °¡¸®Å°¸ç ÃÖÈÄ·Î »ðÀÔµÈ µ¥ÀÌÅ͸¦ °¡¸®Å°°í ÀÖ´Ù. ÀÌ ¹æ½Ä ¿Ü¿¡ TopÀÌ ´ÙÀ½ »ðÀ﵃ À§Ä¡¸¦ °¡¸®Å°µµ·Ï ±¸ÇöÇÒ ¼öµµ ÀÖÀ¸¸ç ÀÌ °æ¿ì TopÀÌ 0ÀÎ »óÅ°¡ ºó »óÅÂÀÌ´Ù. µÎ ¹æ½Ä ¸ðµÎ °¡´ÉÇϹǷΠ¾î¶² ¹æ½ÄÀ̵çÁö ¼±ÅÃÇÒ ¼ö ÀÖµÇ ÇÑ ¹ø Á¤ÇÑ Àǹ̸¦ Çò°¥¸®Áö¸¸ ¾ÊÀ¸¸é µÈ´Ù. ½Ã½ºÅÛ ½ºÅÃÀÇ TopÀÌ ÃÖÈÄ µ¥ÀÌÅÍ À§Ä¡¸¦ °¡¸®Å°µµ·Ï µÇ¾î ÀÖÀ¸¹Ç·Î º¸ÅëÀº ÀÌ ¹æ½ÄÀ» µû¸¥´Ù. ´ÙÀ½ ±×¸²Àº ½ºÅÿ¡ 1, 2, 3À» ¼ø¼­´ë·Î ³Ö¾ú´Ù »©´Â ¿¹ÀÌ´Ù.

ÃÖÃÊ TopÀÌ -1ÀÏ ¶§´Â ½ºÅÃÀÌ ºñ¾î ÀÖÀ¸¸ç µ¥ÀÌÅÍ°¡ »ðÀԵǸé TopÀÌ À§·Î À̵¿Çϸ鼭 Top À§Ä¡¿¡ µ¥ÀÌÅÍ°¡ ÀúÀåµÈ´Ù. Ǫ½ÃµÇ´Â ¼ø¼­´ë·Î ½ºÅÿ¡ µ¥ÀÌÅÍ°¡ Â÷°îÂ÷°î ½×À̸ç ÆËÇÒ ¶§´Â Ǫ½ÃµÈ ¿ª¼øÀ¸·Î ²¨³»Áø´Ù. ¿¹Á¦¿¡¼­´Â 7, 0, 6, 2, 9¸¦ Â÷·Ê´ë·Î ³Ö¾ú´Ù°¡ ¿ª¼øÀ¸·Î »©¼­ Ãâ·ÂÇØ º¸¾Ò´Ù. À§ ±×¸²¿¡¼­ ½ºÅÃÀÇ ¾Æ·¡ÂÊÀÌ ³·Àº ¹øÁö(¹è¿­ ¼±µÎ)ÀÌ°í À§ÂÊÀÌ ³ôÀº ¹øÁöÀÌ¸ç ½Ã½ºÅÛ ½ºÅÃÀº ÀÌ¿Í ¹Ý´ë·Î µÇ¾î ÀÖ´Ù.

½ºÅÃÀº °°Àº ŸÀÔÀÇ ÁýÇÕÀ̹ǷΠ¿¬°á ¸®½ºÆ®·Îµµ ¸¸µé ¼ö ÀÖ´Ù. ¿¬°á ¸®½ºÆ®¸¦ ¾µ °æ¿ì ½ºÅà ũ±â°¡ óÀ½ºÎÅÍ °íÁ¤µÇÁö ¾Ê°í ÇÊ¿äÇѸ¸Å­ ¾ó¸¶µçÁö ´Ã¸± ¼ö ÀÖ´Ù´Â ÀåÁ¡ÀÌ ÀÖ´Ù. ±×·¯³ª Ǫ½Ã, ÆË ÇÒ ¶§¸¶´Ù ¸Þ¸ð¸®¸¦ ÇÒ´çÇÏ°í ÇØÁ¦ÇØ¾ß ÇϹǷΠ¼Óµµ°¡ ´À¸®°í ¸Þ¸ð¸®µµ ´õ ¸¹ÀÌ ¼Ò¸ðÇÑ´Ù. ÀÓ½ÃÀûÀÎ Á¤º¸¸¦ ÀúÀåÇÏ´Â ¿ëµµ»ó ½ºÅÃÀº ±»ÀÌ ±æÀÌ°¡ °¡º¯ÀûÀÏ ÇÊ¿ä°¡ ¾øÀ¸¹Ç·Î ¿¬°á ¸®½ºÆ®·Î ½ºÅÃÀ» ±¸ÇöÇÏ´Â °ÍÀº ÇÕ¸®ÀûÀÌÁö ¾ÊÀ¸¸ç ¹è¿­ÀÌ ´õ Àß ¾î¿ï¸°´Ù.