스택

기술노트
Admin (토론 | 기여)님의 2025년 5월 19일 (월) 13:41 판

예상 질문

자료 저장 형태 중 스택(Stack)과 큐(Queue)에 대해서 설명하시오. 스택과 큐는 어떤 차이가 있는지 설명하시오. 스택과 큐를 적용할만한 예를 들어 설명하시오.

이 질문을 하는 이유

스택과 큐는 자료 구조의 기본적인 개념이다. 각각 적합한 활용처가 있으며, 그 활용처가 무엇인지 숙지해야 한다. 또한 코딩의 기본이 되는 요소이기도 하므로, 코드 레벨로 구현할 수 있어야 한다. 기본 중의 기본이므로 반드시 숙달해야 할 영역이다.

CS 지식

스택(Stack)

책이 책상 위에 쌓여 있다고 가정하자. 제일 아래에 있는 책을 꺼내는 것보다는 제일 위에 있는 책을 꺼내는 것이 더 쉽다. 이런 방식으로 자료를 저장하고 사용하는 형태의 자료구조를 스택(Stack)이라고 한다. '쌓여 있다'는 의미 그대로, 후입선출(FILO: First In, Last Out) 방식으로 동작한다.

즉, 데이터를 스택에 입력한 뒤 가져오게 되면, 가장 마지막에 입력한 데이터가 가장 먼저 나온다.

큐(Queue)

큐는 줄을 서는 개념이다. 먼저 줄을 서 있는 사람이 먼저 기회를 얻는다. 즉, 선입선출(FIFO: First In, First Out) 구조이다.

데이터가 큐에 입력되면, 먼저 들어간 데이터가 먼저 꺼내져서 사용된다.

구현 관점

개념을 이해했다면 이제 어떻게 구현할 수 있을까?

사실 스택이나 큐는 많은 프로그래밍 언어에서 이미 라이브러리나 기본 클래스로 구현되어 있다. 예를 들어 Java의 경우 Stack, Queue 클래스를 직접 사용할 수 있다.

하지만, 스택이나 큐가 어떻게 동작하는지를 구현할 수 있어야 진정으로 이해한 것이다.

배열 기반 구현

  • 스택과 큐는 모두 배열(Array)을 이용해서 구현할 수 있다.
  • 배열의 현재 위치를 가리키는 인덱스 변수를 두고, 현재 위치를 변경하면서 값을 입력하거나 반환한다.

예를 들어, 숫자를 입력받는 스택이라면:

  • push() 함수: 값을 저장하고 인덱스를 증가시킨다.
  • pop() 함수: 현재 인덱스에서 값을 꺼내고 인덱스를 감소시킨다.

큐는 다음과 같이 구성할 수 있다:

  • enqueue() 함수: 배열의 뒤쪽에 값을 넣고 rear 인덱스를 증가시킨다.
  • dequeue() 함수: 앞쪽에서 값을 꺼내고 front 인덱스를 증가시킨다.

결론

  • 스택은 후입선출(FILO), 큐는 선입선출(FIFO)
  • 실제 프로젝트에서는 라이브러리를 활용하되, 내부 동작 방식은 반드시 숙지할 것
  • 직접 구현해보는 과정을 통해 자료구조에 대한 이해도를 높일 수 있음

개발자가 스택(Stack)과 큐(Queue)를 알아야 하는 이유

스택과 큐는 자료 구조의 기본 중 기본으로, 많은 알고리즘 문제와 실무 개발에서 자주 등장합니다. 이 두 자료 구조를 이해하고 구현할 줄 아는 것은 개발자의 핵심 역량입니다.

✅ 왜 알아야 하나?

  1. 기본적인 문제 해결 능력

많은 알고리즘 문제(예: 괄호 유효성 검사, 트리 순회, BFS/DFS, 히스토리 기능 구현 등)는 스택/큐를 기반으로 합니다.

  1. 언어별 API를 이해하고 응용하기 위해

Java, Node.js, Python 등에서는 스택/큐 관련 클래스와 함수가 기본 제공됩니다. 하지만 동작 원리를 모르면 효과적으로 활용하거나 디버깅하기 어렵습니다.

  1. 효율적인 메모리 관리와 성능 최적화

큐는 요청 처리나 작업 스케줄링에, 스택은 재귀 대체 등에서 활용되며 성능 개선에 중요한 역할을 합니다.

  1. 비동기 처리와 요청 처리 로직에 자주 사용

예: 메시지 큐, 서버 요청 대기열, 이벤트 처리 등에 큐 구조는 필수적입니다.

📘 Java 예제: 스택을 이용한 괄호 검사

import java.util.Stack;

public class BracketChecker {
    public static boolean isBalanced(String input) {
        Stack<Character> stack = new Stack<>();
        for (char ch : input.toCharArray()) {
            if (ch == '(') stack.push(ch);
            else if (ch == ')') {
                if (stack.isEmpty()) return false;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(isBalanced("(()())")); // true
        System.out.println(isBalanced("(()"));    // false
    }
}

📗 Node.js 예제: 큐를 이용한 요청 처리 시뮬레이션

class Queue {
  constructor() {
    this.items = [];
  }
  enqueue(item) {
    this.items.push(item);
  }
  dequeue() {
    return this.items.shift();
  }
  isEmpty() {
    return this.items.length === 0;
  }
}

const requestQueue = new Queue();
requestQueue.enqueue("User1");
requestQueue.enqueue("User2");
requestQueue.enqueue("User3");

while (!requestQueue.isEmpty()) {
  const user = requestQueue.dequeue();
  console.log(`Processing request from ${user}`);
}

// 출력:
// Processing request from User1
// Processing request from User2
// Processing request from User3

📕 Python 예제: 스택을 이용한 브라우저 히스토리

class BrowserHistory:
    def __init__(self):
        self.back_stack = []
        self.current = "Home"

    def visit(self, url):
        self.back_stack.append(self.current)
        self.current = url

    def back(self):
        if self.back_stack:
            self.current = self.back_stack.pop()
        return self.current

# 사용 예
browser = BrowserHistory()
browser.visit("google.com")
browser.visit("github.com")
print(browser.back())  # google.com
print(browser.back())  # Home

🧠 결론

스택과 큐는 단순한 데이터 저장 방식이 아니라, 실무 개발에서도 자주 사용되는 핵심 자료구조입니다. 이를 이해하고 응용할 수 있어야 문제 해결 능력과 시스템 설계 능력을 갖춘 개발자가 될 수 있습니다.

원본 주소 "https://technote.wiki/index.php?title=스택&oldid=667"