Language 자료구조 Part3. "스택"의 모든 것.

자료구조가 무엇인지는 본 블로그의 "자료구조알고리즘" 항목의
 
첫번째 글에 자료구조에 대한 설명이 대략 있음을 알린다.
 
 
Part3 스택
--------------------------------------
 
스택. 바구니.
 
큐가 FIFO(First In First Out) 이라면,
 
스택은 LIFO(Last In First Out)의 원리로 동작하는 선형적인 자료 구조이다.
 
스택은 큐에 바닥을 막아논 것으로 생각해 두면 쉬운데,
 
 |　　|
 |자료|　<-이렇게 생겨먹은 놈이다.
 |자료|
└- -┘
 
같은 타입의 자료 집합을 관리한다는 면에서는 동적배열이나 큐와 동일하지만 자료를 관리하는 방식이 미리 정해져 있다는 점이 다르다.
 
스택은 데이터가 들어가고 나오는 입구가 하나뿐이므로 입구로 들어간 데이터가 스택에 차곡차곡 쌓여 있다가 들어간 반대 순서로 나온다.
 
주로 계산중에 잠시 기억해야 하는 임시적인 자료를 관리하는 용도로 사용된다.
 
스택도 연결리스트로 구현이 가능하며, 이 장에선 배열로 구현하 스택을 다뤄보자.
 
---------------------
CPU도 여러 가지 정보를 저장하기 위해 스택을 사용하는데 이를 시스템 스택이라 한다.
시스템 스택에는 함수로 전달되는 인수, 지역변수 등의 임시 변수들이 저장되고 함수 실행 후 돌아갈 복귀 번지도 저장된다. 이 내용은 스택 프레임을 공부할 때 이미 살펴본 적이 있다. 또한 함수 실행중에 필요한 임시 정보들도 스택에 저장되는데 주로 레지스터값을 대피시키는 용도로 사용한다. CPU의 레지스터 개수가 많지 않기 때문에 이미 사용중인 레지스터를 다른 용도로 쓰고 싶을 때는 스택에 잠시 저장해 두고 사용한 후 다시 원래값을 꺼내 복구한다.
시스템 스택은 CPU가 직접 사용하는 장소이므로 응용 프로그램은 여기에 자신의 데이터를 저장할 수 없다. 꼭 시스템 스택을 쓰고자 한다면 불가능한 것은 아니지만 어셈블리 코드로만 스택을 사용할 수 있고 규칙을 반드시 지켜야 하므로 무척 부담스럽다. 별도의 스택이 필요하다면 하드웨어 스택과 똑같이 동작하는 소프트웨어 스택을 만들 수 있다.
---------------------(WinAPI 제공)
 
이처럼 스택은 컴퓨터가 제공하기도 하고, 함수의 지역변수의 관리도 스택이 한다.
 
즉, 우리는 여태 스택을 많이 사용해 왔다는 것이다.
 
큐와 마찬가지로 스택에서도 여러 전문용어를 사용하는데,
 
top 은 스택의 현재위치를 가리키는 값이며, 스택의 차있는 정도를 나타내기도 한다.
 
top은 가리키는 값으로써 포인터를 사용하지만, 배열에서 인자로 나타낼 수 도 있기 때문에
 
정수형 변수로 쓰기도 한다. ex) top = 4 -> stack[4] -> 5개의 자료가 차 있다.
 
또, push 와 pop이 있는데, push는 자료를 집어넣는 행위(큐에서 put),
 
pop은 자료를 빼 내는 행위(큐에서 get)가 있다.
 
그 외 init는 큐와 마찬가지로 스택에서도 초기화의 뜻을 가지고 있다.
 
그럼, 이 것 들에 대해 하나씩 알아보자.
 
먼저, 큐와 마찬가지로 init로 스택을 초기화 해야 한다.
 
그 후에야 스택을 사용할 수 있게 된다.
 
init에선 top을 -1 로 지정한다.
 
그 이유는, top을 1 증가시키며, 그 자리에 데이타를 넣기 때문이다.
 
배열이 0부터 시작하기 때문에 0은 자료가 없는 상태가 아니라 하나 들어 있는 상태이므로 비어 있는 것과는 다르다.
 
init 했다면, push와 pop으로 스택을 사용할 수 있게 되는데,
 
init를 했다곤 하지만, 들어있는 자료는 하나도 없기에 pop은 할 수 없겠다.
 
즉, push로 데이타를 넣으며, push 함수에선 top을 1 증가시키며, top을 인자로 가지는 배열에 입력 data를 넣으면 되겠다.
 
이 때, top과 할당된 스택의 크기를 비교하여 top이 스택의 마지막 요소보다 작을때만 push하며,
 
이 조건에 맞지 않으면 에러를 리턴한다.
 
이 상황을 스택이 가득 차 더이상 자료를 넣을 수 없는 상태, 즉 오버플로우 라고 한다.
 
 
pop의 동작도 매우 간단하다.
 
Top 위치의 값을 읽고 Top은 하나 감소시킨다.
 
스택이 텅 비어서 더 꺼낼 데이터가 없는 상태를 스택 언더플로우라고 하는데
 
이때는 -1이라는 에러값을 리턴하도록 한다.
 
스택은 푸시와 팝을 정확하게 맞춰야 하므로 스택 언더플로우는 절대로 발생해서는 안되는 에러이다.
 
스택의 소스는 다음과 같다.
//시작--------------------이 줄은 소스에 포함되지 않습니다.

·미리보기 | 소스복사·

1. #include <stdio.h>   
2. #define MAX  10   
3. int  stack[ MAX ];   
4. int  top;   
5. void init_stack( void );   
6. void push( int key );   
7. int pop( void );   
8. void print_stack( void );   
9. void main( void )   
10. {   
11.  int  i;   
12.  init_stack( );   
13.  push( 3 ); push( 4 ); push( 5 ); push( 6 ); push( 7 ); push( 8 );   
14.  print_stack( );   
15.     
16.  i = pop();   
17.  printf("pop한 값은 %dn",i);   
18.  print_stack( );   
19.  push( 1 ); push( 2 ); push( 3 ); push( 4 ); push( 5 );   
20.     
21.  print_stack( );   
22.     
23.  push( 6 );   
24.  print_stack( );   
25.   
26. }   
27. void init_stack( void )   
28. {   
29.  top = -1;   
30. }   
31. void push( int key )   
32. {   
33.  if( top == MAX - 1 )   
34.  {   
35.   printf("오버플로우n");   
36.   return;   
37.  }   
38.  stack[ ++top ] = key;   
39. }   
40. int pop( void )   
41. {   
42.  if( top == -1 )   
43.  {   
44.   printf("언더플로우n");   
45.   return -1;   
46.  }   
47.  return stack[ top-- ];   
48. }   
49. void print_stack( void )   
50. {   
51.  int  i;   
52.  for( i = top ; i >= 0 ; i-- )   
53.   printf("%3d",stack[i]);   
54.  printf("n");   
55. }  

 
//끝----------------이 줄은 소스에 포함되지 않습니다.
 
위의 소스를 그림으로 표현 해 보겠다.
 
│　│ push 3 4 5 6 7 8
│　│
│　│
│　│
│8 │
│7 │  -> print_stack = 3 4 5 6 7 8
│6 │
│5 │
│4 │
│3 │
└─┘
  ↓　　pop();
│　│
│　│
│　│
│　│
│　│
│7 │  -> pop한 값 = 8
│6 │
│5 │
│4 │
│3 │
└─┘
  ↓　　push 1 2 3 4 5
│5 │
│4 │
│3 │
│2 │
│1  │
│7 │  -> print_stack = 3 4 5 6 7 1 2 3 4 5
│6 │
│5 │
│4 │
│3 │
└─┘
  ↓　　push 6
│5 │
│4 │
│3 │
│2 │
│1 │
│7 │  -> 스택이 꽉 찼는데 push(6)을 하려 하므로 오버플로우 (overflow!)
│6 │
│5 │
│4 │
│3 │
└─┘
------------------------------------------
위와 같다.
 
스택은 같은 타입의 집합이므로 연결 리스트로도 만들 수 있다.
 
연결 리스트를 쓸 경우 스택 크기가 처음부터 고정되지 않고 필요한만큼 얼마든지 늘릴 수 있다는 장점이 있다.
 
그러나 푸시, 팝 할 때마다 메모리를 할당하고 해제해야 하므로 속도가 느리고 메모리도 더 많이 소모한다.
 
임시적인 정보를 저장하는 용도상 스택은 굳이 길이가 가변적일 필요가 없으므로 연결 리스트로 스택을 구현하는 것은 합리적이지 않으며 배열이 더 잘 어울린다.
 
하지만, 연결리스트로 구현해 보는 것 또한 경험이며 지식!
 
연결리스트를 공부 후에 다음엔 연결리스트로 스택을 구현해보도록 하자!
 
 
-----------------
(**참고** 스택을 이용한 계산기)
 
//시작----------------이 줄은 소스에 포함되지 않습니다.

·미리보기 | 소스복사·

1. #include <stdio.h>   
2. #include <malloc.h>   
3. #include <math.h>   
4. #include <string.h>   
5. #include <ctype.h>   
6.     
7. char *cStack;   
8. int cSize;   
9. int cTop;   
10. void cInitStack(int aSize)   
11. {   
12.      cSize=aSize;   
13.      cStack=(char *)malloc(cSize*sizeof(char));   
14.      cTop=-1;   
15. }   
16. void cFreeStack()   
17. {   
18.      free(cStack);   
19. }   
20. bool cPush(char data)   
21. {   
22.      if (cTop < cSize-1)   
23.   {   
24.           cTop++;   
25.           cStack[cTop]=data;   
26.           return true;   
27.      }   
28.   else  
29.   {   
30.           return false;   
31.      }   
32. }   
33. char cPop()   
34. {   
35.      if (cTop >= 0)   
36.   {   
37.           return cStack[cTop--];   
38.      }   
39.   else  
40.   {   
41.           return -1;   
42.      }   
43. }   
44. double *dStack;   
45. int dSize;   
46. int dTop;   
47. void dInitStack(int aSize)   
48. {   
49.      dSize=aSize;   
50.      dStack=(double *)malloc(dSize*sizeof(double));   
51.      dTop=-1;   
52. }   
53. void dFreeStack()   
54. {   
55.      free(dStack);   
56. }   
57. bool dPush(double data)   
58. {   
59.      if (dTop < dSize-1)   
60.   {   
61.           dTop++;   
62.           dStack[dTop]=data;   
63.           return true;   
64.      }   
65.   else  
66.   {   
67.           return false;   
68.      }   
69. }   
70. double dPop()   
71. {   
72.      if (dTop >= 0)   
73.   {   
74.           return dStack[dTop--];   
75.      }   
76.   else  
77.   {   
78.           return -1;   
79.      }   
80. }   
81. int GetPriority(int op)   
82. {   
83.      switch (op)   
84.   {   
85.      case '(':   
86.           return 0;   
87.      case '+':   
88.      case '-':   
89.           return 1;   
90.      case '*':   
91.      case '/':   
92.           return 2;   
93.      case '^':   
94.           return 3;   
95.      }   
96.      return 100;   
97. }   
98. void MakePostfix(char *Post, const char *Mid)   
99. {   
100.      const char *m=Mid;   
101.      char *p=Post,c;   
102.      cInitStack(256);   
103.      while (*m)   
104.   {   
105.           // 숫자 - 그대로 출력하고 뒤에 공백 하나를 출력한다.   
106.           if (isdigit(*m))   
107.     {   
108.               while (isdigit(*m) || *m=='.') *p++=*m++;   
109.               *p++=' ';   
110.           }   
111.     else  
112.           // 연산자 - 스택에 있는 자기보다 높은 연산자를 모두 꺼내 출력하고 자신은 푸시한다.   
113.           if (strchr("^*/+-",*m))   
114.     {   
115.               while (cTop!=-1 && GetPriority(cStack[cTop]) >= GetPriority(*m))   
116.      {   
117.                    *p++=cPop();   
118.               }   
119.               cPush(*m++);   
120.           }   
121.     else    
122.           // 여는 괄호 - 푸시한다.   
123.           if (*m=='(')   
124.     {   
125.               cPush(*m++);   
126.           }   
127.     else  
128.           // 닫는 괄호 - 여는 괄호가 나올 때까지 팝해서 출력하고 여는 괄호는 버린다.   
129.           if (*m==')')   
130.     {   
131.               for (;;)   
132.      {   
133.                    c=cPop();   
134.                    if (c=='(') break;   
135.                    *p++=c;   
136.                }   
137.               m++;   
138.           }   
139.     else  
140.     {   
141.               m++;   
142.           }   
143.      }   
144.      // 스택에 남은 연산자들 모두 꺼낸다.   
145.      while (cTop != -1)   
146.   {   
147.           *p++=cPop();   
148.      }   
149.      *p=0;   
150.      cFreeStack();   
151. }   
152. double CalcPostfix(const char *Post)   
153. {   
154.      const char *p=Post;   
155.      double num;   
156.      double left,right;   
157.      dInitStack(256);   
158.      while (*p)   
159.   {   
160.           // 숫자는 스택에 넣는다.   
161.           if (isdigit(*p))   
162.     {   
163.               num=atof(p);   
164.               dPush(num);   
165.               for(;isdigit(*p) || *p=='.';p++) {;}   
166.           }   
167.     else  
168.     {   
169.               // 연산자는 스택에서 두 수를 꺼내 연산하고 다시 푸시한다.   
170.               if (strchr("^*/+-",*p))   
171.      {   
172.                    right=dPop();   
173.                    left=dPop();   
174.                    switch (*p)   
175.        {   
176.                    case '+':   
177.                         dPush(left+right);   
178.                         break;   
179.                    case '-':   
180.                         dPush(left-right);   
181.                         break;   
182.                    case '*':   
183.                         dPush(left*right);   
184.                         break;   
185.                    case '/':   
186.                         if (right == 0.0)   
187.       {   
188.                              dPush(0.0);   
189.                         }   
190.       else  
191.       {   
192.                              dPush(left/right);   
193.                         }   
194.                         break;   
195.                    case '^':   
196.                         dPush(pow(left,right));   
197.                         break;   
198.                    }   
199.               }   
200.               // 연산 후 또는 연산자가 아닌 경우 다음 문자로   
201.               p++;   
202.           }   
203.      }   
204.      if (dTop != -1)   
205.   {   
206.           num=dPop();   
207.      }   
208.   else  
209.   {   
210.           num=0.0;   
211.      }   
212.      dFreeStack();   
213.      return num;   
214. }   
215. double CalcExp(const char *exp,bool *bError=NULL)   
216. {   
217.      char Post[256];   
218.      const char *p;   
219.      int count;   
220.      if (bError!=NULL)   
221.   {   
222.           for (p=exp,count=0;*p;p++)   
223.     {   
224.               if (*p=='(') count++;   
225.               if (*p==')') count--;   
226.           }   
227.           *bError=(count != 0);   
228.      }   
229.     
230.      MakePostfix(Post,exp);   
231.      return CalcPostfix(Post);   
232. }   
233. void main()   
234. {   
235.      char exp[256];   
236.      bool bError;   
237.      double result;   
238.   char *p=strchr("^*/+-",NULL);   
239.      strcpy(exp,"2.2+3.5*4.1");printf("%s = %.2fn",exp,CalcExp(exp));   
240.      strcpy(exp,"(34+93)*2-(43/2)");printf("%s = %.2fn",exp,CalcExp(exp));   
241.      strcpy(exp,"1+(2+3)/4*5+2^10+(6/7)*8");printf("%s = %.2fn",exp,CalcExp(exp));   
242.      for (;;)   
243.   {   
244.           printf("수식을 입력하세요(끝낼 때 0) : ");   
245.           gets(exp);   
246.           if (strcmp(exp,"0")==0) break;   
247.           result=CalcExp(exp,&bError);   
248.           if (bError)   
249.     {   
250.               puts("수식의 괄호짝이 틀립니다.");   
251.           }   
252.     else  
253.     {   
254.               printf("%s = %.2fn",exp,result);   
255.           }   
256.      }   
257. }  

 
//끝------------------이 줄은 소스에 포함되지 않습니다.
 
분석---
TextCalc 예제는 상기 분석한 알고리즘대로 중위식을 후위식으로 바꾸고 후위식을 연산하여 결과를 출력한다.
 
범용적인 연산이 가능하도록 하기 위해 실수를 사용했는데 double형이면 웬만큼 정밀한 연산을 모두 할 수 있다.
 
만약 정수 연산만 하고 싶다면 dStack을 정수형으로 바꾸고 숫자를 읽어들이는 함수 atof 대신 atoi를 사용하면 된다.
 
또는 최종 결과 출력문인 printf의 서식을 %.0f로만 바꾸어도 비슷한 효과를 낼 수 있다.
 
중위식을 후위식으로 바꾸고 연산까지 하려면 번거롭기 때문에 중위식을 전달하면 후위식으로 바꾼 후 연산하는 랩퍼 함수 CalcExp를 작성했다.
 
이 함수는 연산하기 전에 기본적인 에러 점검을 하는데 괄호의 짝이 맞지 않을 경우 실패를 리턴한다.
 
실패 리턴값을 받고 싶으면 CalcExp에 BOOL형 변수의 포인터를 전달하여 그 결과를 받을 수 있되 실패 여부에 관심이 없으면 NULL을 전달해도 상관없다.
 
이 예제는 후위식 변환을 위해 그리고 변환된 후위식 계산을 위해 두 개의 스택을 사용한다.
 
연산자의 경우 뒤쪽을 더 읽어 봐야 정확한 연산 순위를 알 수 있으므로 자기 차례가 될 때까지 잠시 대기해야 하며 계산식의 경우 부분식의 계산 결과가 이어지는 연산자의 피연산자로 사용되기 위해 임시적으로 저장되어야 한다. 그리고 연산자와 부분식 모두 들어간 역순으로 꺼내야 하므로 스택이 가장 적절한 자료 구조이다.
 
스택의 크기는 두 경우 모두 256으로 설정했는데 이 크기는 계산을 위해서 아주 충분한 크기라고 할 수 있다.
 
연산자와 부분식은 나오는 족족 푸시되기만 하는 것이 아니라 차례가 되면 팝되어 빠져 나오므로 256이라는 스택 크기는 처리할 수 있는 최대 연산자 개수가 아니라 최대 중첩 가능 회수가 된다.
 
아무리 식이 복잡해 봐야 10단계 이상 중첩되는 경우는 거의 없으므로 256정도면 펑펑 남아돌 정도의 크기이다.
 
이상으로 스택을 이용한 간단한 계산기 예제 제작을 마친다.
 
알고리즘이 나름대로 복잡해서 되도록 간단하게 만들기 위해 노력했는데 그러다 보니 몇 가지 한계점이 있다.
 
우선 이항 연산자만을 다룸으로써 - 부호 연산자를 인식하지 않는다. 3 + -2는 1로 계산되어야 하지만 -을 이항 연산자로 인식하므로 틀린 결과가 나올 것이다.
 
또한 누승 연산자의 경우 우측 우선의 결합 순서를 가지지만 이 예제는 편의상 좌측 우선으로 처리했다.
 
그래서 두 번 연거푸 누승 연산을 할 경우 수학적인 계산과는 틀린 결과가 나온다.
 
2^3^4는 왼쪽 우선일 때 8^4으로 4096이지만 오른쪽 우선이면 2^81으로 엄청난 수가 된다.
 
(계산기 예제 및 설명 --- winapi 제공)
 
----------------------------
선린인고 20420 전호근