자료구조는 소프트웨어 개발의 핵심 개념 중 하나로, 특히 스택과 큐는 알고리즘 설계와 문제 해결에서 자주 활용됩니다.
이 글에서는 스택과 큐의 기본 개념부터 시작해 실제로 어떻게 구현되는지, 그리고 어떤 문제에 적용할 수 있는지를 상세히 알아봅니다. 초보자에게는 이론적인 개념 정리에 도움이 되고, 중급자에게는 실전 활용법을 넓힐 수 있는 가이드가 될 것입니다.
자료구조 기본: 스택과 큐의 이해
스택(Stack)과 큐(Queue)는 선형 자료구조의 대표적인 형태로, 데이터를 저장하고 꺼내는 방식에 차이가 있습니다.
스택은 후입선출(LIFO, Last In First Out) 구조를 갖고 있어, 마지막에 들어온 데이터가 가장 먼저 나가게 됩니다.
예를 들어 웹 브라우저의 '뒤로 가기' 기능은 스택의 전형적인 활용입니다. 사용자가 페이지를 방문할 때마다 이전 페이지의 정보를 스택에 쌓아두고, '뒤로 가기' 버튼을 누르면 가장 최근의 페이지부터 차례로 꺼내는 방식입니다.
반면 큐는 선입선출(FIFO, First In First Out) 구조입니다. 먼저 들어온 데이터가 먼저 나가는 방식으로, 줄을 서는 시스템이나 인쇄 대기열 등에서 사용됩니다. 이처럼 단순한 구조이지만 다양한 프로그램에서 핵심 역할을 합니다.
스택과 큐는 기본적으로 배열이나 연결 리스트를 기반으로 구현됩니다. 또한 프로그래밍 언어마다 기본적으로 제공되거나 직접 구현할 수 있도록 다양한 라이브러리가 준비되어 있습니다.
예를 들어 Python에서는 list로 스택을 구현하고, collections.deque로 큐를 쉽게 다룰 수 있습니다. 이러한 자료구조를 정확히 이해하는 것은 이후의 알고리즘 문제 해결 능력을 키우는 데 매우 중요합니다. 데이터가 어떻게 저장되고 이동하는지를 파악하는 것만으로도 코드의 흐름을 논리적으로 따라갈 수 있게 됩니다.
구현 방식: 배열과 연결 리스트를 활용한 구조
스택과 큐는 구현 방식에 따라 그 성능과 메모리 효율성이 달라질 수 있습니다.
기본적으로 배열(Array)을 활용한 구현은 단순하지만 유연성이 떨어질 수 있습니다. 예를 들어, 배열 기반 큐의 경우 처음 데이터를 꺼내면 앞부분이 비게 되는데, 이 부분을 재사용하려면 데이터를 이동시켜야 하므로 성능 저하가 발생할 수 있습니다. 이에 비해 연결 리스트(Linked List)를 사용하면 포인터만 조정하면 되므로 더 유연하고 빠른 처리가 가능합니다.
스택의 경우 연결 리스트를 활용하면 삽입과 삭제가 앞부분에서 빠르게 일어나며, 큐도 마찬가지로 앞쪽 노드를 제거하고 뒤쪽에 추가하는 방식으로 효율적인 처리가 가능합니다. Python이나 Java 등 다양한 언어에서는 이러한 자료구조를 손쉽게 사용할 수 있는 도구들이 존재합니다.
예를 들어 Python의 collections.deque는 양쪽에서 삽입과 삭제가 가능한 구조로, 스택과 큐 모두를 구현하는 데 적합합니다.
Java에서는 Stack, Queue, LinkedList 등의 클래스를 통해 자료구조 구현이 가능합니다. 하지만 단순히 라이브러리를 쓰는 데에 그치지 않고, 그 내부 구현 원리를 아는 것이 중요합니다. 이는 면접에서도 자주 나오는 질문이며, 실제 문제 해결에서 보다 정확한 선택을 가능하게 만듭니다.
활용법: 알고리즘 문제 해결에서의 응용
스택과 큐는 알고리즘 문제에서 가장 많이 등장하는 도구 중 하나입니다.
스택의 대표적인 활용 예로는 괄호 검사, DFS(깊이 우선 탐색), 웹 브라우저 히스토리 관리 등을 들 수 있습니다. 괄호의 짝이 맞는지 확인할 때, 열리는 괄호는 스택에 쌓고 닫히는 괄호가 나올 때마다 하나씩 꺼내 비교합니다. 이처럼 순서와 짝을 맞춰야 하는 문제에서 스택은 매우 강력한 도구입니다.
큐는 BFS(너비 우선 탐색), 캐시 시스템, 프린터 대기열 등에서 자주 사용됩니다. 특히 BFS는 그래프 탐색에서 노드를 순차적으로 방문할 때 매우 유용한 방식이며, 큐를 활용해 방문 순서를 제어할 수 있습니다. 최근에는 병렬 처리, 스레드 관리, 요청 처리 시스템 등에서도 큐 구조가 필수적으로 사용됩니다.
실전 코딩 테스트에서도 이 두 자료구조를 기반으로 한 문제들이 자주 출제됩니다. 예를 들어, "가장 가까운 큰 수 찾기", "카카오 문제 중 괄호 변환", "기본적인 그래프 탐색 문제" 등이 대표적인 예입니다. 이러한 문제에 익숙해지기 위해서는 단순한 코드 암기보다는 문제에 맞는 자료구조 선택 능력을 키워야 합니다.
스택과 큐는 단순해 보이지만 알고리즘의 기초를 이루는 핵심 도구입니다. 이를 잘 다루는 것은 단지 개발 실력 향상뿐만 아니라 논리적 사고력 향상에도 큰 도움이 됩니다.
스택과 큐는 모든 개발자가 반드시 이해하고 있어야 할 핵심 자료구조입니다. 그 원리와 구현 방식을 익히고, 다양한 알고리즘 문제에 어떻게 적용되는지 체득함으로써 보다 견고한 개발 실력을 다질 수 있습니다. 지금 바로 예제를 통해 직접 구현해 보며 실력을 쌓아보세요!