스택(Stack)은 컴퓨터 공학에서 매우 중요한 자료구조 중 하나로, 데이터를 저장하고 관리하는 데 사용된다.
스택은 후입선출(LIFO, Last In First Out)의 원리를 따르는 구조로, 가장 최근에 삽입된 데이터가 가장 먼저 삭제된다. 이를 책 더미에 비유하면 이해하기 쉽다. 새로 추가한 책이 맨 위에 놓이며, 맨 위에 있는 책부터 꺼내야 하는 구조와 동일하다.

스택의 구조

스택은 기본적으로 다음 두 가지 연산을 통해 동작한다.

  1. 푸시(Push): 스택의 맨 위에 데이터를 추가하는 연산이다.
  2. 팝(Pop): 스택의 맨 위에 있는 데이터를 제거하고 반환하는 연산이다.

추가적으로, 현재 스택의 상태를 확인하거나 맨 위의 데이터를 확인할 수 있는 연산이 포함될 수 있다

  • 피크(Peek): 스택의 맨 위에 있는 데이터를 제거하지 않고 반환한다.
  • isEmpty: 스택이 비어 있는지 확인한다.

스택은 보통 배열(Array)이나 연결 리스트(Linked List)를 통해 구현되며, 배열 기반의 스택은 고정 크기를 가지는 반면, 연결 리스트 기반의 스택은 동적으로 크기를 조정할 수 있다.

 

다이어그램: 스택의 구조

아래는 스택의 연산 과정을 시각적으로 표현한 다이어그램이다.

다이어그램 : 스택 연산 흐름

  1. 푸시 연산:
    • 10, 20, 30을 차례로 스택에 추가하며 스택의 상태가 업데이트된다.
  2. 피크 연산:
    • 스택의 최상단 값 30을 제거하지 않고 확인한다.
  3. 팝 연산:
    • 스택의 최상단 값 30을 제거하고 스택 상태가 업데이트된다.

 

스택의 활용 사례

스택은 다양한 알고리즘과 시스템에서 활용되며, 특히 다음과 같은 사례에서 유용하다.

 

1. 재귀 알고리즘 구현

  • 재귀 함수는 내부적으로 호출 스택(Call Stack)을 이용해 실행된다. 각 함수 호출 시 현재 상태가 스택에 저장되고, 함수 실행이 끝나면 스택에서 제거된다. 이는 재귀적으로 문제를 해결하는 과정에서 자연스럽게 스택의 동작 원리를 활용하는 예시이다.

2. 괄호 유효성 검사

  • 수학이나 프로그래밍에서 괄호가 올바르게 닫히는지 확인하는 문제는 스택을 통해 효율적으로 해결할 수 있다. 여는 괄호를 만나면 스택에 푸시하고, 닫는 괄호를 만나면 스택에서 팝하여 짝이 맞는지 확인한다.

3. DFS(깊이 우선 탐색)

  • 그래프 탐색 알고리즘 중 깊이 우선 탐색(DFS)은 스택을 사용하여 구현할 수 있다. DFS는 특정 노드에서 출발해 가능한 깊이까지 탐색한 후, 더 이상 갈 곳이 없으면 이전 상태로 되돌아가 다른 경로를 탐색한다. 이 과정은 스택의 후입선출 원리를 이용한다.

4. 웹 브라우저의 뒤로 가기/앞으로 가기 기능

  • 웹 브라우저에서 뒤로 가기와 앞으로 가기 기능은 스택을 사용하여 구현된다. 방문한 페이지는 뒤로 가기 스택에 푸시되고, 뒤로 가기를 누르면 해당 스택에서 팝되어 앞으로 가기 스택으로 이동한다.

5. Undo/Redo 기능

  • 텍스트 편집기나 그래픽 소프트웨어에서 사용자의 작업을 취소(Undo)하거나 다시 실행(Redo)하는 기능은 두 개의 스택을 사용하여 구현된다. 작업을 수행할 때는 Undo 스택에 기록하고, Undo를 실행하면 Undo 스택에서 팝하여 Redo 스택에 푸시한다.

6. 수식 계산 및 파싱

  • 스택은 계산기 프로그램에서 수식을 계산하거나, 프로그래밍 언어의 컴파일러에서 코드를 파싱하는 데 사용된다. 특히, 중위 표기법(Infix)을 후위 표기법(Postfix)으로 변환하거나 후위 표기법을 계산하는 과정에서 스택이 활용된다.

스택 구현 코드 예제

아래는 Java로 구현한 간단한 스택 클래스의 예제이다

public class Stack {
    private int[] stack; // 스택을 저장할 배열
    private int top; // 스택의 맨 위를 가리키는 변수
    private int size; // 스택의 최대 크기

    // 스택 생성자: 주어진 크기로 스택을 초기화한다.
    public Stack(int size) {
        this.size = size;
        this.stack = new int[size];
        this.top = -1; // 스택이 비어 있음을 나타내는 초기 값
    }

    // 푸시 연산: 스택에 값을 추가한다.
    public void push(int value) {
        if (top == size - 1) { // 스택이 가득 찼는지 확인
            System.out.println("스택이 가득 찼습니다.");
        } else {
            stack[++top] = value; // 값을 추가하고 top을 증가
        }
    }

    // 팝 연산: 스택의 맨 위 값을 제거하고 반환한다.
    public int pop() {
        if (top == -1) { // 스택이 비어 있는지 확인
            System.out.println("스택이 비어 있습니다.");
            return -1; // 오류 값을 반환
        } else {
            return stack[top--]; // 맨 위 값을 반환하고 top을 감소
        }
    }

    // 피크 연산: 스택의 맨 위 값을 반환하되 제거하지 않는다.
    public int peek() {
        if (top == -1) { // 스택이 비어 있는지 확인
            System.out.println("스택이 비어 있습니다.");
            return -1; // 오류 값을 반환
        } else {
            return stack[top]; // 맨 위 값을 반환
        }
    }

    // isEmpty: 스택이 비어 있는지 확인한다.
    public boolean isEmpty() {
        return top == -1;
    }

    // 메인 메서드: 스택의 동작을 테스트한다.
    public static void main(String[] args) {
        Stack stack = new Stack(5); // 크기가 5인 스택 생성
        stack.push(10); // 10 추가
        stack.push(20); // 20 추가
        stack.push(30); // 30 추가

        System.out.println("스택의 맨 위: " + stack.peek()); // 맨 위 값 확인
        System.out.println("스택에서 제거된 값: " + stack.pop()); // 맨 위 값 제거 및 반환
        System.out.println("스택이 비어 있는가? " + stack.isEmpty()); // 스택이 비어 있는지 확인
    }
}

 

위 코드를 실행하면 다음과 같은 결과가 출력된다

스택의 맨 위: 30
스택에서 제거된 값: 30
스택이 비어 있는가? false
  1. 클래스 멤버
    • stack: 정수를 저장하는 배열로 스택의 데이터를 관리한다.
    • top: 스택의 맨 위를 나타내는 인덱스를 저장한다. 초기 값은 -1로, 스택이 비어 있음을 나타낸다.
    • size: 스택의 최대 크기를 저장한다.
  2. 생성자
    • 배열을 초기화하고, top을 -1로 설정하여 스택을 비어 있는 상태로 만든다.
  3. 푸시 메서드
    • top을 증가시키고, 해당 위치에 새로운 값을 저장한다.
    • 스택이 가득 찬 경우, 에러 메시지를 출력한다.
  4. 팝 메서드
    • top 위치의 값을 반환하고, top을 감소시켜 스택에서 제거한다.
    • 스택이 비어 있으면 에러 메시지를 출력하고, -1을 반환한다.
  5. 피크 메서드
    • top 위치의 값을 반환하지만, top을 변경하지 않는다.
    • 스택이 비어 있으면 에러 메시지를 출력하고, -1을 반환한다.
  6. isEmpty 메서드
    • top이 -1인지 확인하여 스택이 비어 있는지 여부를 반환한다.
  7. 메인 메서드
    • 스택 객체를 생성하고 푸시, 팝, 피크 연산을 테스트하여 스택의 동작을 확인한다.
 

스택은 단순한 원리를 기반으로 하지만, 활용도는 매우 높다. 스택을 이해하고 적절히 활용하면 복잡한 문제를 효율적으로 해결할 수 있다. 특히, 재귀적 문제 해결, 그래프 탐색, 데이터 처리와 같은 다양한 분야에서 스택의 중요성이 강조된다.

따라서 스택의 개념과 동작 방식을 확실히 이해하고, 실습을 통해 다양한 문제에 적용해보는 것이 중요하다.

티스토리툴바