자료구조의 핵심, 스택·큐·트리·그래프의 특징과 실전 활용 완전정리

 

 

 

 

 

프로그램이 다루는 모든 데이터는 어딘가에 저장되고, 어떤 순서로든 꺼내어져 처리된다. 이때 데이터를 어떤 형태로 담고 어떤 규칙으로 접근할 것인가를 결정하는 것이 바로 자료구조이다. 같은 문제라도 어떤 자료구조를 선택하느냐에 따라 처리 속도와 메모리 사용량이 크게 달라지기 때문에, 자료구조에 대한 이해는 효율적인 프로그램을 설계하는 데 있어 가장 기초적이면서도 핵심적인 지식으로 꼽힌다. 이 글에서는 대표적인 자료구조인 스택, 큐, 트리, 그래프의 개념과 동작 방식, 그리고 실제로 어떤 상황에서 활용되는지를 체계적으로 살펴본다.

 

 

 

▍ 자료구조란 무엇이며 왜 중요한가

 

자료구조는 데이터를 컴퓨터의 메모리 공간에 저장하고, 이를 효율적으로 조작하기 위한 논리적인 구조와 그에 수반되는 연산의 집합을 의미한다. 단순히 데이터를 담아두는 그릇이 아니라, 데이터를 넣고(삽입) 꺼내고(삭제) 찾는(탐색) 일련의 규칙까지 포함하는 개념으로 이해해야 한다. 같은 데이터라도 배열에 저장할 때와 연결 리스트에 저장할 때 삽입과 삭제에 걸리는 시간이 다르며, 이러한 차이는 프로그램의 성능에 직접적인 영향을 준다.

 

자료구조를 학습해야 하는 이유는 크게 두 가지로 요약할 수 있다. 첫째, 동일한 기능을 수행하더라도 자료구조의 내부 동작 방식을 이해하고 있어야 상황에 맞는 최적의 선택을 할 수 있다. 둘째, 대부분의 알고리즘은 특정 자료구조를 기반으로 동작하기 때문에, 자료구조에 대한 이해 없이는 알고리즘의 원리를 온전히 파악하기 어렵다. 결국 자료구조와 알고리즘은 서로 분리해서 생각할 수 없는 짝을 이루는 개념이라 할 수 있다.

 

 

 

▍ 선형 구조와 비선형 구조의 구분

 

자료구조는 데이터 요소들이 배열되는 방식에 따라 크게 선형 구조와 비선형 구조로 나뉜다. 이 두 가지 분류를 먼저 이해하면, 이후 살펴볼 스택, 큐, 트리, 그래프가 각각 어느 범주에 속하고 왜 그런 특징을 갖는지를 좀 더 명확하게 파악할 수 있다.

 

선형 구조는 데이터가 하나의 줄을 이루듯 순차적으로 나열되어 있는 형태를 말한다. 배열, 연결 리스트, 스택, 큐가 대표적인 예이며, 각 요소는 원칙적으로 하나의 앞 요소와 하나의 뒤 요소만을 가진다. 반면 비선형 구조는 하나의 데이터가 여러 개의 데이터와 동시에 관계를 맺을 수 있는 구조로, 트리와 그래프가 이에 해당한다. 비선형 구조는 데이터 간의 계층적 관계나 복잡한 연결 관계를 표현하는 데 적합하다.

 

 

 

 

이러한 분류를 바탕으로, 이제부터 각 자료구조가 실제로 메모리에서 어떤 방식으로 데이터를 다루는지 구체적으로 살펴본다.

 

 

 

▍ 스택(Stack)의 특징과 동작 원리

 

스택은 데이터를 한쪽 끝에서만 넣고 뺄 수 있는 자료구조로, 후입선출이라 불리는 LIFO(Last In First Out) 방식을 따른다. 가장 나중에 저장된 데이터가 가장 먼저 꺼내진다는 의미이며, 이는 마치 책상 위에 쌓아 올린 접시나 책 더미와 비슷한 구조라고 이해하면 쉽다. 맨 위에 올려놓은 것을 먼저 집어야 하고, 중간에 있는 것을 바로 꺼낼 수는 없다.

 

스택의 기본 연산은 데이터를 추가하는 push, 데이터를 꺼내는 pop, 가장 위에 있는 데이터를 확인만 하는 peek, 그리고 스택이 비어 있는지를 확인하는 연산으로 구성된다. 이러한 연산들은 모두 한쪽 끝에서만 이루어지기 때문에 처리 속도가 매우 빠르며, 배열이나 연결 리스트 어느 쪽으로 구현하더라도 삽입과 삭제에 걸리는 시간은 데이터의 개수와 무관하게 일정하다.

 

스택은 순서를 거꾸로 되짚어야 하는 상황에서 특히 유용하게 쓰인다. 프로그램이 함수를 호출할 때 시스템은 호출 정보를 스택 형태로 관리하는데, 함수 A가 함수 B를 부르고 B가 다시 C를 부르면 실행이 끝난 순서는 C, B, A의 역순으로 이루어진다. 이 밖에도 괄호의 짝이 맞는지 검사하는 문제, 문서 편집기의 되돌리기(undo) 기능, 웹 브라우저의 뒤로 가기 기능, 수식을 계산하는 과정 등 다양한 곳에서 스택의 원리가 응용된다.

 

 

 

 

 

 

▍ 큐(Queue)의 특징과 동작 원리

 

큐는 스택과 대비되는 구조로, 먼저 들어온 데이터가 먼저 나가는 선입선출, 즉 FIFO(First In First Out) 방식을 따른다. 데이터가 들어오는 입구와 나가는 출구가 서로 다른 쪽에 위치한다는 점이 스택과 가장 큰 차이이다. 이는 은행 창구나 매표소에서 줄을 서는 모습을 떠올리면 직관적으로 이해할 수 있다. 먼저 줄을 선 사람이 먼저 서비스를 받고, 새로 온 사람은 줄의 맨 뒤에 서게 된다.

 

큐의 대표적인 연산으로는 데이터를 뒤쪽에 추가하는 enqueue와 앞쪽에서 데이터를 꺼내는 dequeue가 있으며, 스택과 마찬가지로 가장 앞의 데이터를 확인하는 연산과 비어 있는지 확인하는 연산이 함께 사용된다. 배열로 큐를 구현할 경우 데이터를 계속 꺼내다 보면 앞쪽 공간이 비어 낭비가 발생할 수 있는데, 이를 해결하기 위해 배열의 끝과 시작을 논리적으로 연결한 원형 큐라는 방식이 널리 사용된다.

 

큐는 처리 순서를 보장해야 하는 다양한 상황에서 활용된다. 프린터에 여러 문서가 동시에 전송되었을 때 요청이 들어온 순서대로 인쇄하는 작업, 운영체제가 여러 프로세스의 실행 순서를 관리하는 스케줄링, 네트워크 장비에서 데이터 패킷을 순서대로 전송하는 버퍼, 너비 우선 탐색 알고리즘을 구현할 때 등이 대표적인 예이다. 한편 양쪽 끝에서 모두 삽입과 삭제가 가능한 덱(Deque, Double-Ended Queue)이라는 변형 구조도 존재하며, 스택과 큐의 특성을 상황에 맞게 혼합해서 사용할 수 있다는 장점이 있다.

 

 

 

▍ 스택과 큐의 차이 비교

 

스택과 큐는 모두 선형 구조에 속하고 삽입과 삭제라는 기본 동작을 공유하지만, 데이터가 처리되는 순서라는 근본적인 지점에서 뚜렷하게 구분된다. 아래 표는 두 구조의 핵심적인 차이를 간단히 정리한 것이다.

 

 

 

 

두 구조 모두 삽입과 삭제 연산 자체는 데이터 크기와 무관하게 일정한 시간 안에 처리되지만, 어떤 문제를 풀어야 하는가에 따라 선택이 완전히 달라진다는 점을 기억할 필요가 있다. 가장 최근의 상태로 되돌아가야 하는 문제라면 스택이, 처리 순서를 공정하게 유지해야 하는 문제라면 큐가 자연스러운 선택이 된다.

 

 

 

 

 

 

▍ 트리(Tree)의 특징과 구조적 원리

 

트리는 데이터를 계층적인 형태로 표현하는 비선형 자료구조이다. 나무를 거꾸로 세워놓은 모습과 비슷하다고 하여 트리라는 이름이 붙었으며, 최상위에 위치하는 하나의 노드를 루트(root)라 부르고, 여기서 뻗어나가는 자식 노드들이 다시 각각의 하위 트리를 구성하는 재귀적인 구조를 가진다. 자식이 없는 노드는 리프(leaf) 노드라고 부른다.

 

트리 구조에서 중요한 특징은 임의의 두 노드 사이에 오직 하나의 경로만 존재한다는 점이다. 즉 순환하는 경로가 없으며, 이 때문에 트리는 흔히 사이클이 없는 연결 그래프의 일종으로 설명되기도 한다. 트리의 형태는 용도에 따라 다양하게 변형되는데, 각 노드가 최대 두 개의 자식만 가질 수 있는 이진 트리, 그리고 왼쪽 서브트리에는 자신보다 작은 값을, 오른쪽 서브트리에는 자신보다 큰 값을 저장하도록 규칙을 둔 이진 탐색 트리가 대표적이다.

 

이진 탐색 트리는 데이터가 비교적 균형 있게 분포되어 있을 경우 탐색, 삽입, 삭제 연산을 평균적으로 로그 시간에 처리할 수 있다는 장점이 있다. 다만 데이터가 한쪽으로 치우쳐 삽입되면 트리가 한 방향으로 길게 늘어지는 편향 트리가 되어, 최악의 경우 연결 리스트와 비슷한 수준으로 성능이 떨어질 수 있다. 이러한 문제를 보완하기 위해 삽입과 삭제 시 트리의 균형을 자동으로 맞추는 레드 블랙 트리, AVL 트리와 같은 균형 이진 탐색 트리가 실무에서 널리 사용된다.

 

트리 구조는 컴퓨터 파일 시스템의 폴더와 파일 구조, 조직도, HTML 문서의 태그 구조, 데이터베이스의 인덱스 관리 등 계층적인 관계를 표현해야 하는 거의 모든 곳에서 사용된다. 특히 대량의 데이터 중에서 특정 값을 빠르게 찾아야 하는 검색 시스템에서 트리 기반 인덱스는 핵심적인 역할을 담당한다.

 

 

 

 

 

 

▍ 그래프(Graph)의 특징과 표현 방식

 

그래프는 트리보다 한층 더 자유로운 형태로 데이터 간의 관계를 표현하는 비선형 자료구조이다. 그래프는 정점(vertex, 또는 노드)과 이들을 연결하는 간선(edge)으로 구성되며, 트리와 달리 하나의 정점이 여러 정점과 자유롭게 연결될 수 있고 순환 경로가 존재할 수도 있다. 트리가 그래프의 특수한 형태라고 보는 시각도 있는데, 사이클이 없고 모든 정점이 하나로 연결된 그래프가 곧 트리이기 때문이다.

 

그래프는 간선에 방향이 있는지에 따라 방향 그래프와 무방향 그래프로 나뉜다. 예를 들어 도로가 일방통행인 경우는 방향 그래프로, 양방향 통행이 가능한 도로망은 무방향 그래프로 표현할 수 있다. 또한 간선에 거리나 비용과 같은 값을 부여한 가중치 그래프를 사용하면 두 지점 사이의 최단 경로를 계산하는 문제 등에 활용할 수 있다.

 

그래프를 컴퓨터 메모리에 저장하는 대표적인 방식으로는 인접 행렬과 인접 리스트가 있다. 인접 행렬은 정점의 개수만큼의 행과 열을 가진 표를 만들어 두 정점이 연결되어 있는지를 표시하는 방식으로, 구현이 단순하고 두 정점의 연결 여부를 즉시 확인할 수 있다는 장점이 있지만, 정점 수가 많아질수록 필요한 메모리가 급격히 늘어난다는 단점이 있다. 반면 인접 리스트는 각 정점마다 자신과 연결된 정점들의 목록만을 저장하는 방식으로, 연결 관계가 상대적으로 적은 희소 그래프에서 메모리를 훨씬 효율적으로 사용할 수 있다.

 

 

 

 

그래프는 실제 세계의 복잡한 연결 관계를 모델링하는 데 널리 쓰인다. 도로망이나 항공 노선과 같은 교통 체계, 소셜 네트워크에서 사람과 사람 사이의 관계, 인터넷 상의 웹페이지와 하이퍼링크 구조, 전기 회로의 배선 등이 모두 그래프로 표현될 수 있다. 그래프 위에서 특정 경로를 찾거나 전체를 빠짐없이 순회하기 위해 너비 우선 탐색과 깊이 우선 탐색이라는 대표적인 두 가지 탐색 방법이 사용되는데, 너비 우선 탐색은 큐를 기반으로, 깊이 우선 탐색은 스택 또는 재귀 호출을 기반으로 동작한다는 점에서 앞서 살펴본 스택과 큐의 원리가 그래프 탐색에도 그대로 이어진다는 것을 확인할 수 있다.

 

 

 

 

 

 

▍ 네 가지 자료구조의 실전 활용 비교

 

지금까지 살펴본 스택, 큐, 트리, 그래프는 각각 서로 다른 성격의 문제를 해결하기 위해 발전해 온 구조이다. 실제 소프트웨어를 개발할 때는 문제의 성격을 먼저 파악한 뒤, 그에 가장 적합한 자료구조를 선택하는 과정이 필요하다. 예를 들어 최근의 작업을 우선적으로 되돌려야 한다면 스택이, 요청이 들어온 순서를 지켜야 한다면 큐가 자연스러운 선택이다.

 

계층적인 분류 체계나 정렬된 데이터에서 빠른 검색이 필요한 경우에는 트리 구조가 적합하며, 여러 대상 사이의 복잡하고 자유로운 연결 관계를 다뤄야 한다면 그래프가 유일한 대안이 되는 경우가 많다. 다음은 각 자료구조가 어떤 상황에서 강점을 발휘하는지를 정리한 내용이다.

 

스택: 실행 취소 기능, 함수 호출 관리, 문자열 내 괄호의 짝 검사

 

큐: 작업 대기열 관리, 순서를 지켜야 하는 데이터 전송, 프로세스 스케줄링

 

트리: 파일 및 폴더 구조, 데이터베이스 인덱스, 정렬된 데이터의 빠른 탐색

 

그래프: 지도와 경로 탐색, 소셜 네트워크 분석, 네트워크 구조 모델링

 

다만 이러 실제로는 하나의 시스템 안에서 여러 자료구조가 함께 사용되는 경우가 훨씬 일반적이다. 예를 들어 그래프 탐색 알고리즘 내부에서는 큐나 스택이 보조 자료구조로 함께 동작하고, 트리 구조를 배열 형태로 저장하여 메모리 효율을 높이는 방식도 흔히 쓰인다. 따라서 각 자료구조의 원리를 독립적으로 이해하는 것도 중요하지만, 이들이 서로 어떻게 결합되어 활용되는지를 함께 살펴보는 태도가 필요하다.

 

 

 

 

 

 

▍ 자료구조 선택 시 고려해야 할 요소

 

어떤 자료구조를 선택할 것인가는 단순히 이론적인 지식만으로 결정되지 않는다. 실제로는 데이터의 규모, 삽입과 삭제가 얼마나 빈번하게 일어나는지, 탐색 연산의 빈도, 그리고 사용 가능한 메모리의 한계 등을 종합적으로 고려해야 한다. 데이터의 삽입과 삭제가 잦고 순서를 지키는 것이 중요하다면 연결 리스트 기반의 큐나 스택이 유리할 수 있고, 탐색이 훨씬 빈번하게 일어나는 상황이라면 정렬된 트리 구조나 해시 기반 구조가 더 적합할 수 있다.

 

또한 메모리의 효율성과 연산 속도는 서로 상충하는 경우가 많다는 점도 유념할 필요가 있다. 인접 행렬처럼 빠른 확인이 가능하지만 메모리를 많이 차지하는 방식이 있는가 하면, 인접 리스트처럼 메모리는 절약되지만 특정 연산에서는 상대적으로 느린 방식도 있다. 결국 정답이 하나로 정해져 있다기보다는, 다루는 문제의 특성과 시스템이 처한 제약 조건에 따라 가장 균형 잡힌 선택을 내리는 것이 자료구조를 다루는 핵심 역량이라 할 수 있다.

 

 

 

 

 

 

▍ 마무리하며

 

스택은 나중에 들어온 데이터를 먼저 꺼내는 후입선출 구조로 순서를 거꾸로 되짚는 문제에, 큐는 먼저 들어온 데이터를 먼저 꺼내는 선입선출 구조로 순서를 공정하게 유지해야 하는 문제에 강점을 지닌다. 트리는 계층적인 관계를, 그래프는 자유롭고 복잡한 연결 관계를 표현하는 데 적합하며, 두 구조 모두 실세계의 다양한 관계망을 모델링하는 기초가 된다. 이 네 가지 자료구조는 서로 독립적으로 존재하는 것이 아니라, 실제 프로그램 안에서는 서로 얽히고 보완하며 함께 사용되는 경우가 많다.

 

결국 자료구조에 대한 이해는 특정 언어나 도구에 국한되지 않는, 프로그래밍의 근본적인 사고방식을 길러주는 과정이라 할 수 있다. 스택과 큐, 트리와 그래프 각각의 원리와 차이를 명확히 파악해 두면, 앞으로 마주하게 될 다양한 문제 상황에서 어떤 구조를 선택해야 할지 스스로 판단할 수 있는 힘이 생긴다. 오늘 정리한 내용을 바탕으로 각 자료구조가 실제 코드에서 어떻게 구현되는지 하나씩 직접 다뤄보는 과정을 이어가 보는 것도 좋은 다음 단계가 될 것이다.