자료구조 - Stack이란

스택은 솔직하게 면접용으로 암기식 공부를 했었다. 하지만 이번엔 자료구조를 공부하며 정리를 해보았다

스택의 기본개념부터 확장된 연산 표기식까지 흩어졌던 지식들을 모아보았다

 

---

자료구조 - Stack이란

 

스택은 객체가 저장되는 순서를 기억하는 방법에 관한 자료구조이다

가장 마지막에 들어간 놈이 제일 먼저 출력(LIFO) 되는 방식이다

→ 한마디로 스택은 객체의 순서를 정해주는 자료구조 !

 

 

 

스택의 추상 자료형

 

스택의 정의와 적용 가능 연산을 명세

→ 생성부터 종료까지 스택의 매니징에 필요한 여러 기능들을 소개한다

 

• stack : 0개 이상의 원소를 갖는 스택 (값이 들어 있는)

• item : 스택에 삽입되는 원소

• maxQueueSize : 스택의 최대 크기를 정의

// 스택 생성
Stack CreateStack(maxSize) ::=
	maxSize 크기인 빈스택 생성 및 반환

// 스택 push
Stack Push(stack, item) ::= 
	if(IsFull(stack)){
    	then { 'stack is full' 출력 }
        else { 스택 최상위에 item 삽입, 스택 반환 }
    }

// 스택 pop
Element Pop(stack) ::=
	if(IsEmpty(stack){
    	then { 'stack is empty' 출력 }
        else { 스택 최상위 원소 삭제, 스택 반환 }    	
    }

// 스택 꽉찼는지
Boolean IsFull(stack, maxSize) ::=
	if(stack의 elements 갯수 === maxSize) {
    	then { 'TRUE' 반환 }
    	else { 'FALSE' 반환 }
    }

// 스택 비어있는지
Boolean IsEmpty(stack) ::=
	if(stack == CreateStack(maxSize)){
    	then { 'TRUE' 반환 }
    	else { 'FALSE' 반환 }
    }

 

 

PUSH 

스택에 원소를 추가하는 연산을 구현해보자

void push(int *stack, int *top, element item){
	if(*top >= STACK_SIZE - 1){ // 정원 초과 예외 처리 
    	return stackFull();
    }

    stack[++(*top)] = item; // 주소값을 ++1 하고 top(1증가 업그레이드)의 주소에 item 값을 추가
}

 

 

POP 

스택에 원소를 삭제하는 연산을 구현해보자

element pop(int *top){ // 포인터로 직접 값에 접근
	if(*top == -1){ // 값이 -1 이면 예외처리
    	return stackEmpty();
    }
    
    return stack[(*top)--]; // *top 의 주소값을 --1 만큼 감소
}

 

 

 

스택의 사용처

 

✅ 시스템 스택 : 변수들의 생명주기를 관리 (메모리에 할당되고 비워지기까지 변수의 한살이)

✅ 서브루틴 호출 관리 : 실행컨텍스트 동작방식과 비 - 슷 (함수끝나고 pop 함수 끝나고 pop)

✅ 인터럽트 처리 :  인터럽트 처리 후에 명령 수행 지점 저장 (운영체제 관련)

✅ 컴파일러 : 한문자씩 입력받고 검사하는 구문 분석기에서 사용

✅ 순환 호출 관리 : 자신을 호출하는 재귀함수가 끝나고 되돌아갈 실행 주소를 저장해서 관리

✅ 수식 계산 : 연산자로 연산할 때

 

 

사칙 연산식의 수식 계산

 

스택에서 연산이 어떻게 계산되는지 살펴보자

그전에 연산 표기식을 알아야 한다. 간단하게 살펴보자

• 중위 표기법 : 우리가 아는 연산식, 연산자가 중간에 위치 ex) 1 + 2 
• 전위 표기법 : 연산자가 앞에 오는 표기법 ex) + 1 2
• 후위 표기법 : 연산자가 뒤에 오는 표기법 ex) 1 2 +

 

 

스택에서는 후위 표기법을 사용한다. 그래서 일반적인 표기법(중위)이 → 후위표기법의 수식으로 변경된다

exp = '369 * -' // 다음과 같은 후위 표기식을 계산해보자

// 후위 표기식의 계산 알고리즘
element evalPostfix (char *exp) { 	// 스택을 사용해서 후위표기식 계산
    int oper1, oper2, value, i = 0; 	// 변수 정의
    int length = strlen(exp); 		// 배열의 길이
    char symbol;  			// 얘는 원소를 의미
    top = -1;  				// 스택의 위치를 가리키는 변수 초기화

    for(i = 0; i < length; i++){
        symbol = exp[i]; // 배열의 원소

        // 연산자가 아닐 경우, 즉 피연산자인 경우
        if(symbol != '+' && symbol != '-' && symbol != '*' && symbol != '/'){
            value = symbol - '0'; // char → 정수형으로 변환 (0을 뺀값을 저장) 
            push(value); // 그값 고대로 push!
            
        // symbol이 연산자인 경우
        } else {
            oper2 = pop(); // 피연산자 두개를 pop 시키고
            oper1 = pop();
            swtich(symbol){ // 연산자로 연산들을 시 - 작
                case '+':
                    push(oper1 + oper2); // 연산된 값을 push!
                    break;
                case '-':
                    push(oper1 - oper2);
                    break;
                case '*':
                    push(oper1 * oper2);
                    break;
                case '/':
                    push(oper1 / oper2);
                    break;

            }
        }
    }
    
    return pop(); // 그렇게 연산 다했으면 결과값을 스택에서 pop()하며 종료
}