[자료구조] 스택(Stack)과 큐(Queue)

들어가며

오늘은 프로그래밍의 기본이자 많은 애플리케이션에서 사용되는 스택(Stack)과 큐(Queue)에 대해서 작성해 보려고 한다.

스택(Stack): LIFO(Last In First Out)

스택은 데이터의 삽입(Push)과 제거(Pop)가 한쪽 끝에서만 이루어지는 선형 자료구조이다. 가장 마지막에 추가된 데이터가 가장 먼저 제거되는 구조이기 때문에 LIFO (Last In First Out)로 불린다.

특징

• 데이터를 넣는 동작과 데이터를 꺼내는 동작 모두 상수 시간 (O(1))에 가능하다.
• 스택의 주요 사용 사례는 컴퓨터 내부의 함수 호출, 괄호 검사, 후위 표기법 계산 등에 활용된다.

스택의 활용 예시

스택은 다양한 프로그래밍 문제와 실제 시나리오에서 사용된다.

1. 괄호 검사: 스택은 여는 괄호와 닫는 괄호의 쌍이 제대로 이루어져 있는지 검사하는 데 유용하다.
2. 수식의 후위 표기법 변환: 중위 표기법을 후위 표기법으로 변환할 때 스택을 사용한다.
3. 함수 호출: 컴퓨터에서 함수의 호출과 반환을 관리하기 위해 시스템 스택을 사용한다.
4. 실행 취소
5. 웹 브라우저 방문 기록
6. 역순 문자열 만들기

큐(Queue): FIFO(First In First Out)

큐는 데이터의 삽입(Enqueue)이 한쪽 끝에서, 데이터의 제거(Dequeue)가 반대쪽 끝에서 이루어지는 선형 자료구조이다. 처음 들어간 데이터가 처음 나오는 구조이기 때문에 FIFO (First In First Out)로 불린다.

특징

• 데이터를 넣고 빼는 동작 모두 상수 시간 (O(1))에 가능하다.
• 큐의 주요 사용 사례는 운영체제의 태스크 스케줄링, 너비 우선 탐색(BFS) 등에서 활용된다.

주요 활용 사례

• 스택: 웹 브라우저의 ‘뒤로 가기’ 기능, 괄호 검사, 후위 표기법 계산, 깊이 우선 탐색(DFS) 등에 활용.
• 큐: 프린터의 인쇄 대기열, 태스크 스케줄링, 너비 우선 탐색(BFS) 등에 사용.

큐 의 사용사례

1. 프로세스 관리
2. 은행 업무
3. 서비스 센터 대기시간

파이썬 예시 코드

1. 스택 구현

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.isEmpty():
            return None
        return self.items.pop()

    def peek(self):
        if self.isEmpty():
            return None
        return self.items[-1]

    def size(self):
        return len(self.items)

1. 큐 구현

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return len(self.items) == 0

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        if self.isEmpty():
            return None
        return self.items.pop()

    def size(self):
        return len(self.items)

스택의 응용 - 괄호 검사 알고리즘

괄호 검사는 프로그래밍 언어나 수학 수식에서 괄호의 짝이 올바른지 확인하는 문제이다.

알고리즘

문자열의 각 문자를 처음부터 끝까지 읽는다. 여는 괄호 (가 나오면 스택에 push한다. 닫는 괄호 )가 나오면 스택에서 pop한다. 문자열의 끝에 도달했을 때 스택이 비어 있으면 괄호의 짝이 올바른 것이고, 비어 있지 않으면 짝이 맞지 않는 것이다.

def check_parentheses(s: str) -> bool:
    stack = Stack()
    for char in s:
        if char == '(':
            stack.push(char)
        elif char == ')':
            if stack.isEmpty():
                return False
            stack.pop()
    return stack.isEmpty()

이 괄호 검사 알고리즘은 매우 간단하며 스택의 기본적인 사용법을 잘 보여준다. 이와 유사하게 {}, []와 같은 다양한 괄호 짝도 검사할 수 있다.

결론

스택과 큐는 컴퓨터 과학과 프로그래밍의 기초 중 하나이다. 이들은 단순한 데이터 구조처럼 보일 수 있지만, 실제로는 다양한 알고리즘과 응용 프로그램에서 중요한 역할을 한다.

프로그래머로서 스택과 큐를 제대로 이해하고 활용하는 것은 여러 가지 이유로 매우 중요하다.

효율성: 적절한 데이터 구조를 사용하면 프로그램의 성능과 효율성이 크게 향상된다. 스택과 큐는 특정 연산을 빠르게 처리하기 위해 설계되었기 때문에, 이를 잘 활용하면 연산 속도를 크게 향상시킬 수 있다.

문제 해결 능력: 많은 알고리즘 문제들이 스택과 큐를 기반으로 한다. 이들을 잘 이해하고 활용하면 문제 해결 능력이 크게 향상될 것이다.

응용 프로그램의 확장성: 실제 응용 프로그램에서는 여러 가지 복잡한 작업을 처리해야 한다. 스택과 큐를 잘 활용하면 이러한 작업들을 효과적으로 관리하고 확장할 수 있다.

따라서, 프로그래밍의 기본 개념으로서 뿐만 아니라 실제 응용에서도 스택과 큐는 핵심적인 역할을 한다. 이러한 이유로, 프로그래머로서 스택과 큐에 대한 깊은 이해와 활용 능력은 필수적이다.

맨 위로 올라가기