자료구조 스택

스택의 개념

어떤 자료를 저장하는 자료구조를 정의하는데, 이 자료구조에 입력순서를 함께 저장하려고 한다면 어떤 방법을 사용해야 할까? 스택은 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 추상 자료형이다.

스택

• 스택은 자료가 추가되고 삭제되는 입구가 하나이고 이를 Top이라고 한다.
• push 연산자는 스택에 원소하나를 삽입하는 연산자이고 동시에 top포인터를 하나 증가시킨다.
• pop 연산자는 가장 위의 자료, 즉 최근에 삽입된 자료를 삭제를 의미하고 top포인터를 하나 감소시킨다.
• 스택의 크기는 무한하지 않고 top포인터를 통해 남은 장소를 표시하며 이것이 모두 찾을 때를 full이라고 한다. 이때 push 연산자를 사용하면 더 이상 들어갈 곧이 없어 /stackFull/메시지를 반환한다. 반대로 비어있을 때 pop연산자를 사용한다면 stackEmpty를 반환한다.

스택의 추상 자료형

Stack CreateStack(maxStackSize)
스택의 크기가 maxStackSize인 빈 스택을 생성하고 반환한다.
Boolean StackisFull(stack, maxStackSize)
if(stack의 elements의 개수)가 == maxStackSize
then ( 'TRUS' 값을 반환한다;)
else ('FALSE'를 반환한다.)
즉 스택의 원소 개수가 maxStackSize와 같다면 full상태이며 더 이상 저장할 수 없다 그래서 값을 반환한다. 
Stack push(stack, item)
if(Stackisfull(stack))
then('stackfull'을 출력한다.;)
else(스택의 가장 위에 item을 삽입하고 , 스택을 반환한다.)
스택이 풀이라면 stackfull을 출력하게 되고 아니라면 가장 위에 item을 삽입하고 스택을 반환한다.
Boolean GtackIsEmpty(stack)
if(stack == CreateStack(maxStackSize)
then ( 'TRUS' 값을 반환한다;)
else ('FALSE'를 반환한다.)
스택의 상태가 빈 상태인지를 확인하여 빈상태면 TRUE, 하나라도 있다면 FALSE를 반환한다.
Element Pop(stack)
if(StackIsEmpty(Stack))
then('stackEmpty'를 출력한다.
else(스택의 가장 위에 있는 원소를 삭제하고 반환한다.)
Pop연산자는 스택이 빈 상태라면 삭제할 원소가 없으므로 'stackEmpty'를 출력한다. 하지만 빈 상태가 아니라면 가장  위 원소를 삭제하고 반환한다.

1. CreateStack(3);
2. Push(stack, 'S');  
3. Push(stack, 'T');
4. Pop(stack);  Pop에서는 스택에 대한 변수나 포인터만 넘겨주면 된다.
5. Push(stack, 'R');
6. Push(stack, 'P'); 
7. Push(stack, 'Q'); Q는 풀이라서 입력되지 못함
8. Pop(stack)
SR 가 남게 된다.

스택의 응용

변수에 대한 메모리 할당과 수집을 위한 시스템스택. 시스템 스택은 변수들의 생명주기를 관리하기 위해사용한다. 운영체제가 시스템 스택을 이용한다.
두 번째로 서브루틴의 수행이 끝나고 되돌아갈 함수 주소를 저장하기 위한 서브루틴 호출 관리를 위해 사용.
세 번째는 후위 수식 계산. 4+3에서 3과 3은 피연산지이고 +는 연산자이다. 이전에 입력되어 스택에 저장되어 있는 피연산자들을 스택에 저장하고 입력되는 연산자들과 관계를 이용하여 계산 순위를 결정.
네 번째는 프로그램 수행도중 발생되는 인터럽트의 처리와 끝난 후 되돌아가는 명령 수행 지점을 저장하기 위해 스택이 사용된다.
다섯 번째는 한 문자 한문씩 입력받은 후 문법이 옳은지 검사하기 위한 컴파일러 그리고 마지막에 함수가 자신을 함수로 되부르는 순환 호출의 실행이 끝나고 되돌아갈 실행 주소를 저장하기 위한 순환 호출 관리 등에 사용된다.
스택은 입력값의 입력순서나 사건의 선후 순서를 기억하기 위해 사용되는 자료구조.

스택의 연산

int pop(){
    if(top ==-1)
           return StackEmpty( );
    else return stack [top-]; }

pop()를 호출하면 top의 값이 -1과 같으면 빈상태를 말하는 거고 공백이니 StackEmpty를 호출하고, 아니라면 top이 가리키는 메모리 주소에 있는 값을 함숫값으로 반환하고 조수값을 하나 감소시키는 것을 말한다. C/C++에서 후위--를 기억하자.

void push(int item) {
    if (top>= STACK_SIZE-1)
        retrun StackIsFull( );
    else stack [++top] = item;

먼저 push는 저장할 데이터 item도 있어야 한다. pust를 호출했을 때 탑이 스택 크기 - 1보다 크거나 같다면 풀임을 출력하고 아니라면 top의 주소를 1 증가시키고 item 전달값을 저장한다. STACK_SIZE-1 인 이유는 top이 가리키는 인덱스는 0부터 시작하기 때문이다.

전위, 후위, 중위 표현

실제로 덧셈과 뺄셈을 계산할 때는 많은 의미가 담겨있습니다.
1.A+B-C+D
위의 수식을 좀 더 복잡하게 표현해 본다면
2.(((A+B)-C)+D)
첫 번째 내용과 두 번째는 수식에 나타나는 연산자의 계산순서를 더 명확하게 표기하기 위함입니다.
3.A+B*C+D
를 좀 더 세분화한다면
4.((A+(B*C))+D)
연산자의 계산 순서가 곱셈을 먼저계산하고 덧셈을 계산하는 순서를 따르게 됩니다.
1번과 3번의 계산 순서는 다른데요. 1번은 순서대로 계산되고 3번은 순서에 따르지 않습니다. 그 이유는 연산자의 우선순위 때문입니다. 기본산술 연산자로 +, -, *, / 비교연산자로는 <, >, ≤등이 있고 논리연산자로는 and, or, not이 있습니다. 비교 연산자와 논리 연산자로 구성된 결과는 참이나 거짓으로 되는데 이것은 boolean불리언이라고 합니다. 우선순위는 기본연산자가 가장 낮고 비교연산자보다 논리연산자의 우선순위가 높아 높은 순서대로 계산을 해야 한다는 것을 의미합니다.
+인 더하기보다는 *곱하기가 우선순위가 높아 곱하기를 먼저 해줘야 합니다. 이러한 우선순위에 따라 계산순위는 바뀌게 됩니다. 즉 왼쪽에서 나타나는 숫자나 수식부터 계산하면서 계산의 우선순위는 연산자 우선순위에 따릅니다.

1. 중위 표기법 : 연산자를 피연산자의 사이에 표기하는 방법으로 일반적으로 가장 많이 사용됨 A+B
2. 전위 표기법 : 연산자를 피연산자의 앞에 표기하는 방법 AB
3. 후위 표기법 : 연산자를 피연산자 뒤에 표기하는 방법 AB+

중위 표기법의 수식이 스택을 이용하여 후위 표기법으로 변경되어야 한다 왜냐면 후기표기법이 컴퓨터로 처리되기 가장 효율적인 표기법이기 때문입니다.

전위 표기법

전위 표기법은 A+B를 +AB와 같이 피연산자 앞에 연산자를 놓고 표현하는 방법이다.

(A-((B+K)/D)) 를 전위 표기법으로 바꿔본다면
-A(/(+BK) D)로 변경이 됩니다. 컴퓨터는 수식연산자와 피연산자를 순서대로 입력받을 수밖에 없고 나중에 나올 높은 연산자를 고려해야 해서 어쩔 수 없이 스택을 사용하게 됩니다. 이러한 이유로 전위 표기법으로 프로그램을 작성하려면 복잡해집니다.

후위표기법

후위 표기법은 A+B를 AB+로 표현하는 기법입니다.
연산자를 피연산자 뒤에 놓다 보니 컴퓨터가 해석이 빠르고 간결해 사용이 많이 되게 됩니다.

E+(A-B)*C/D를 후위표기법으로 변환한다면
E(((AB-) C*) D/)

스택에서 후위 표기식의 계산

A-B/C-D*E를 스택을 이용해서 후위 표기식으로 변환해 본다면

1. A의 값이 처음 입력되었고 피연산자는 스택에 저장 안 되고 바로출력됩니다. A
2. 다음입력값은 - 로 연산자는 스택에 저장 A
3. 그리고 B가 입력되고 피연산자임으로 출력되게 됩니다. AB
4. 다음 입력값인 / 가 가장 위에 저장된 -보다 우선순위가 높아 스택에 저장되게 됩니다. AB
5. 다음 입력값인 피연산자 C는 바로출력됩니다. ABC
6. 다음 입력값 - 는 연산자로 스택에 저장되어야 하지만 가장 위에 있는 /보다 우선순위가 더 낮아 연산자 /를 삭제하고 출력하고 그렇게 되면 - 의 같은 연산자가 스택에서 만나면 이미 저장되어 있는 연산자가 계산이 먼저 되어야 돼서 이미 저장되어 있던 - 연산자를 삭제하고 출력하게 됩니다. ABC/-
7. 다음 D는 바로 출력돼서 ABC/-D
8. 다음 연산자 *이고 스택에 저장
9. 마지막입력값인 E는 바로 출력되고 ABC/-DE
10. 더 이상 입력값이 없으므로 스택에 저장된 연산자의 출력결과는 ABC/-D*-

또한 스택에 가장 위에 있는 연산자의 우선순위가 새로 입력되는 연산자의 우선순위보다 높거나 같으면 가장 위에 저장된 스택을 삭제하고 출력하며, 다시 스택가장 위에 연산자와 새로 저장하려는 연산자를 비교해서 반복해야 합니다. 즉 가장 위에 저장되어 있는 기존에 있던 연산자의 우선순위보다 높을 때만 스택에 저장이 되게 되죠.
 

알고리즘 설명

element evalPostfix(char *exp) // 후위 표기식 369*+를 계산해 보자
int oper1, oper2, value, i=0;
int length = strlen(exp);
char symbol;
top=-1;
for(i=0; i <lengthl i++){
symbol = exp [i];
if(symbol!='+' && symbol!= '-' && symbol != '*' && symbol!='/'){
value = symbol-'0';
push(value);
}
else {
oper2 = pop( );
oper1 = pop( );
switch(symbol) {
case'+' : push(oper1 + oper2); break;
case'-' : push(oper1 - oper2); break;
case'*' : push(oper1 * oper2); break;
case'/' : push(oper1 / oper2); break;
}}}
return pop( ); }

• 스택 사용을 위해 함수 evalPostfix를 정의하고 369*+가 저장된 char형으 포인터 매개변수로 exp배열을 전달받는다.
• 사칙연산을 위해 피연산자 두 개를 저장할 oper1, oper2과 char형으로 받는 것을 int형으로 변환할 value변수를 정의하고 반복문을 위해 변수 i를 0으로 저장한다.
• 배열의 길이만큼 반복해야 하니 lenth로 변수를 저장한다. 여기서 length는 5가 됨
• 배열에서 값을 가져와 저장해 놓을 symbol을 정의
• 스택의 위치를 가리키는 top의 변수를 -1로 초기화한다.
• 반복문이 시작되고 i의 값이 length의 값인 5보다 작으므로 조건문이 참이 되고 반복문이 실행되고 처음 i가 0이므로 exp [0]의 값인 3을 가져와 symbol에 저장하고 연산자가 아니므로 값이 참이 되어 if문 연산이 실행되고 연산을 위한 정수형 값이 필요하므로 charguddml rkqtdptj 0을 뺸 값을 저장해서 int형으로 변환해 줍니다. 이는 숫자 코드 값으로 변환하여 int형 값을 얻기 위함입니다. 그리고 스택에 저장합니다.
• exp [1], exp [2] 도 동일하게 저장합니다.
• i가 3일 때의 값은 * 곱셈을 symbol 변수에 저장 연산자임으로 값이 거짓이 되어 if문을 실행하지 않고 else 연산을 실행한다.
• 이제 피연산자를 꺼내어 pop 하여  제일 위에 있을 9를 oper2에 저장하고, 그다음 6을 oper1에 저장합니다.
• oper1 * oper2 연산을 하여 54의 값을 다시 push 하여 저장한다.
• i가 4일 때 exp [4]는 +이고 위와 동일하게 하여 oper2에 54를 oper1에 3을 저장하고 다시 57을 스택에 저장하고 
• i의 값이 다시 1 증가하여 5가 되면 for(i=0; i <lengthl i++) 에따라 i가 5보다 작지 안으므로 반복문이 종료되고
  
• return pop( ); }에 의해서 스택에 저장된 57을 반환하고 후위 표기식 계산함수를 종료한다.

oper2에 먼저 저장되어야 하는 이유는 스택은 최근에 들어간 것이 위에 있기 때문에  6*9를 그대로 가져와야 하기 때문에 최근에 들어간 oper2에 넣고 해야 oper1 * oper2 셈이 완성되기 때문이다.