스택 - 스택의 개념, 스택의 추상 자료형, 연산 및 응용, 사칙연산식의 전위 중위 후위 표현

1. 스택의 개념

스택의 정의

스택은 매우 중요한 자료 구조 중 하나로, 마치 책이나 돌멩이를 순서대로 쌓아 올린 것과 같은 구조를 가진다. 스택은 '후입선출(LIFO, Last In First Out)'의 특성을 가지며, 가장 나중에 쌓은 항목이 가장 먼저 나오는 구조를 갖는다. 이러한 특성 때문에, 스택은 여러 컴퓨팅 과정에서 유용하게 사용된다.

스택의 핵심 개념은 다음과 같다:

• 후입선출(LIFO)의 원리: 스택에 추가된 마지막 항목이 가장 먼저 제거된다. 즉, 가장 최근에 쌓은 것이 가장 먼저 나오는 구조다.
• Push와 Pop 연산: 스택에 데이터를 추가하는 행위를 'Push', 데이터를 제거하는 행위를 'Pop'이라 한다. 이 두 연산은 스택을 관리하는 데 핵심적인 역할을 한다.
• Top 포인터: 스택의 가장 상단에 있는 요소를 가리키는 포인터로, 스택의 현재 상태를 나타낸다.

스택의 활용

스택은 다양한 컴퓨팅 상황에서 사용된다. 예를 들어, 함수 호출 시 시스템 스택에 각 함수의 반환 주소와 지역 변수를 저장하는 데 사용되며, 특히 재귀 함수에서 스택의 역할은 더욱 중요하다. 또한, 괄호 검사, 후위 표기법 계산, 웹 브라우저의 뒤로 가기 기능 구현 등에서 스택 구조가 활용된다.

핵심적인 이해

• 스택의 추상적 구조: 스택은 명확한 '위'와 '아래'를 가진 선형 구조이며, 연산은 오직 한 쪽 끝에서만 일어난다.
• 데이터 관리의 유연성: 스택은 데이터를 일시적으로 저장하고 관리하는 데 유용하며, 제한된 접근 방식으로 인해 데이터 관리가 효율적이다.

스택의 구현

스택은 배열이나 연결 리스트로 구현될 수 있으며, 각 구현 방식에 따라 특성과 성능이 다를 수 있다. 배열 기반의 스택은 인덱스를 통한 빠른 접근이 가능하지만 크기가 고정되어 있다는 한계가 있다. 반면, 연결 리스트 기반의 스택은 동적으로 크기가 조절되는 유연성을 가진다.

2. 스택의 추상 자료형

스택의 추상 자료형

스택의 추상 자료형(ADT)은 데이터의 저장과 접근 방식을 정의한다. 스택은 LIFO(Last In, First Out) 방식을 따르며, 데이터가 마지막으로 추가된 위치에서만 접근 가능하다.

createStack 연산

createStack 연산은 새로운 스택을 생성한다. 이때 스택의 최대 크기를 정할 수 있으며, 이 크기는 스택이 수용할 수 있는 최대 항목 수를 의미한다.

function createStack(maxSize):
    stack = new Stack()
    stack.maxSize = maxSize
    stack.top = -1
    return stack

push 연산

push 연산은 스택에 새로운 항목을 추가한다. 이때 항목은 스택의 맨 위에 추가되며, 스택이 가득 차 있으면 이 연산은 실패한다.

function push(stack, item):
    if stack.top == stack.maxSize - 1:
        return "Stack Overflow"
    else:
        stack.top += 1
        stack[stack.top] = item

pop 연산

pop 연산은 스택의 맨 위에 있는 항목을 제거하고 반환한다. 스택이 비어 있을 경우 이 연산은 실패한다.

function pop(stack):
    if stack.top == -1:
        return "Stack Underflow"
    else:
        item = stack[stack.top]
        stack.top -= 1
        return item

pop/push 연산의 실행

pop과 push는 스택의 핵심 연산으로, 스택의 동작을 결정한다. 이들 연산은 스택의 LIFO 특성을 구현하며, 데이터의 추가 및 제거를 관리한다.

stackIsFull, stackIsEmpty 연산

• stackIsFull 연산은 스택이 가득 찼는지 확인한다. 스택의 크기가 최대치에 도달했을 때 참을 반환한다.
• stackIsEmpty 연산은 스택이 비어 있는지 확인한다. 스택에 항목이 없을 때 참을 반환한다.

function stackIsFull(stack):
    return stack.top == stack.maxSize - 1

function stackIsEmpty(stack):
    return stack.top == -1

3. 스택의 응용

스택의 다양한 응용

• 함수 호출과 스택: 프로그램에서 함수를 호출할 때, 스택은 호출된 함수의 주소를 저장하는 데 사용된다. 함수가 종료된 후 프로그램이 이전 상태로 돌아갈 수 있게 해준다.
• 중위 표현식을 후위 표현식으로 변환: 수학적 연산을 처리할 때 ->  중위 표현식을 후위 표현식으로 변환하는 데 유용하게 쓰인다.
• 연산자 우선 순위 처리: 연산자와 피연산자가 입력되면, 스택은 이를 적절한 순서로 재정렬하여 올바른 계산 순서를 보장한다.
• 메모리 관리: 메모리 할당과 해제에서 스택은 임시 데이터를 저장하는 데 사용된다. 
• 프로그램의 실행 상태 관리: 프로그램의 현재 상태를 저장하고, 필요에 따라 이전 상태로 돌아갈 수 있게 해준다. 
• 재귀 함수의 구현: 재귀적 알고리즘에서 스택은 각 재귀 호출의 상태를 저장하는 데 사용된다.
• 문자열 역전: 문자열의 각 문자를 차례대로 스택에 넣고, 다시 꺼내는 과정을 통해 역순으로 된 문자열을 얻을 수 있다.
• 브라우저 뒤로 가기 기능: 사용자가 방문한 페이지의 URL을 스택에 저장하고, '뒤로 가기'를 누를 때마다 스택에서 URL을 꺼내 이전 페이지로 이동한다.

4. 스택의 연산

스택의 삽입 연산 (Push)

스택의 삽입 연산은 새로운 요소를 스택의 최상단에 추가하는 과정이다.

 

스택이 가득 차 있지 않을 경우, 스택의 최상단(top)에 요소를 추가한다.

 

1. 초기 상태: 스택이 비어 있거나 일부 요소를 포함하고 있다고 가정하자. 예를 들어, 스택에는 [2, 5, 7]이 차례로 저장되어 있고, top은 가장 최근에 추가된 요소인 7을 가리킨다.
2. 연산 수행: 새로운 요소, 예를 들어 9를 스택에 추가하려 한다. push(9) 함수가 호출되면, 스택이 가득 차 있지 않은지 확인 후, top을 한 단계 증가시키고, 그 위치에 9를 저장한다.
3. 연산 후 상태: 이제 스택은 [2, 5, 7, 9]를 포함하게 되고, top은 새로 추가된 요소 9를 가리킨다.

• 자바 코드 예시 
• public void push(int data) { if (!isFull()) { stack[++top] = data; } }

 

스택의 삭제 연산 (Pop)

• 스택에서 가장 최근에 추가된 요소를 제거하고 반환하는 연산이다.
• 스택이 비어있지 않을 경우, 스택의 최상단에 있는 요소를 제거하고 반환한다.

1. 초기 상태: 스택에는 [2, 5, 7, 9]가 저장되어 있으며, top은 9를 가리킨다.
2. 연산 수행: pop() 함수가 호출되면, 스택이 비어 있지 않은지 확인 후, 현재 top이 가리키는 요소(9)를 반환하고, top을 한 단계 감소시킨다.
3. 연산 후 상태: 이 연산 후 스택은 [2, 5, 7]만을 포함하게 되고, top은 이제 7을 가리킨다.

• 자바 코드 예시 

• public int pop() {
      if (!isEmpty()) {
          return stack[top--];
      }
      return -1; // 스택이 비어있을 경우
  }

스택의 보조 연산

• peek(): 연산 전과 후에 스택의 최상단 요소를 확인할 때 사용된다. 이는 top의 요소를 반환하되, 스택에서 요소를 제거하지 않는다.
• isEmpty(): 스택이 비어 있는지 확인한다. 이는 top이 -1인지 확인함으로써 수행된다.
• isFull(): 스택이 가득 차 있는지 확인한다. 스택의 최대 크기와 top의 위치를 비교하여 이를 결정한다.

 

5. 사칙연산식의 전위, 후위, 중위 표현

수식의 계산

연산자의 계산 우선순위를 생각해야 한다.

• A+BC+D -> ((A+(BC))+D)

수식의 표기 방법

1) 중위 표기법

• 가장 일반적인 표기 방식이다.
• 연산자가 피연산자의 가운데 위치한다. 예: ( A + B )

2) 전위 표기법

• 연산자가 피연산자 앞에 위치한다.
• 계산 순서를 명확히 해줄 수 있다. 예: ( + A B )

3) 후위 표기법

• 연산자가 피연산자 뒤에 위치한다.
• 컴퓨터 연산에서 유리하며, 괄호가 필요 없다. 예: ( A B + )

중위 표기식의 후위 표기식 변환 방법

• 중위 표기식을 후위 표기식으로 변환하는 과정은 연산자의 우선순위를 고려하여 스택을 사용한다.
• 연산자를 만날 때마다, 스택을 통해 처리하여 후위 표기식을 생성한다.

후위 표기식의 계산 알고리즘

• 후위 표기식의 계산은 스택을 사용하여 수행된다.
• 피연산자를 만나면 스택에 푸시하고, 연산자를 만나면 스택에서 피연산자를 팝하여 계산한 후, 결과를 다시 스택에 푸시한다.

자바 코드 예시

public int evaluatePostfix(String exp) {
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < exp.length(); i++) {
        char c = exp.charAt(i);

        if (Character.isDigit(c)) {
            stack.push(c - '0');
        } else {
            int val1 = stack.pop();
            int val2 = stack.pop();

            switch (c) {
                case '+':
                    stack.push(val2 + val1);
                    break;
                case '-':
                    stack.push(val2 - val1);
                    break;
                case '*':
                    stack.push(val2 * val1);
                    break;
                case '/':
                    stack.push(val2 / val1);
                    break;
            }
        }
    }
    return stack.pop();
}

수식이 저장된 배열과 스택의 계산 과정

예시: ( 369*+\0 )

1. 초기 상태:
   • 배열에는 369*+\0이 저장되어 있다. 이 수식은 3 * 6 + 9를 후위 표기법으로 변환한 것이다.
   • 스택은 초기에 비어 있다.
2. 계산 과정:
   • 숫자 3을 만나면 스택에 푸시한다. 스택: [3]
   • 숫자 6을 만나면 스택에 푸시한다. 스택: [3, 6]
   • 숫자 9을 만나면 스택에 푸시한다. 스택: [3, 6, 9]
   • 연산자 *를 만나면 스택에서 두 개의 숫자를 팝한다 (6과 9), 이들을 곱하고 (6 * 9 = 54), 결과를 스택에 푸시한다. 스택: [3, 54]
   • 연산자 +를 만나면 스택에서 두 개의 숫자를 팝한다 (3과 54), 이들을 더하고 (3 + 54 = 57), 결과를 스택에 푸시한다. 스택: [57]
   • 널 문자 \0는 수식의 끝을 나타낸다.
3. 최종 결과:
   • 계산이 끝난 후 스택에 남은 마지막 값 57이 최종 결과가 된다.

 

 

---

참고 자료: 자료구조 (강태원, 정광식 공저, KNOU press 출판)