자료구조 분류·스택·큐·그래프

자료구조(data structure)는 데이터를 담는 모양이다. 모양에 따라 넣고 꺼내는 규칙과 속도가 달라지므로, 문제에 맞는 자료구조를 고르는 것이 알고리즘 설계의 출발점이다. 시험은 선형·비선형 분류, 스택과 큐에 넣고 뺀 뒤의 결과, 그래프의 최대 간선 수 공식을 묻는다. 원리와 구현은 CS 카테고리의 스택·큐, 그래프 문서가 더 깊게 다룬다.

선형 구조와 비선형 구조

선형 구조(linear structure)는 데이터가 한 줄로 늘어서 앞뒤가 하나씩 정해진 구조다. 비선형 구조(non-linear structure)는 한 데이터가 여러 데이터와 이어져 계층이나 망을 이루는 구조다.

분류	자료구조
선형	배열, 선형 리스트(연속 리스트·연결 리스트), 스택, 큐, 덱
비선형	트리, 그래프

선형 리스트는 배열처럼 이웃한 칸에 차례로 담는 연속 리스트(contiguous list)와, 포인터(pointer)로 다음 칸을 가리키는 연결 리스트(linked list)로 나뉜다. 스택과 큐도 한 줄로 늘어서 있으므로 선형이다. 넣고 빼는 위치만 제한했을 뿐이다.

스택

스택(stack)은 한쪽 끝에서만 넣고 빼는 자료구조다. 가장 나중에 넣은 것이 가장 먼저 나오므로 후입선출(LIFO, Last In First Out)이라 한다. 넣기는 푸시(push), 빼기는 팝(pop)이고 넣고 빼는 끝을 맨 위(top)라 부른다. 가득 찬 스택에 더 넣으면 오버플로(overflow), 빈 스택에서 빼면 언더플로(underflow)가 난다.

함수 호출을 되돌아갈 순서대로 기억하거나, 되돌리기 기능, 괄호 검사, 후위 표기식 계산처럼 "가장 최근 것부터 처리"해야 하는 곳에 쓴다.

예를 들어 1, 2, 3을 차례로 푸시한 뒤 팝을 하면 3이 나온다. 이어서 4를 푸시하고 팝을 두 번 하면 4, 2가 차례로 나와, 꺼낸 순서는 3, 4, 2이고 스택에는 1이 남는다.

큐와 덱

큐(queue)는 한쪽 끝(rear)에서 넣고 반대쪽 끝(front)에서 빼는 자료구조다. 먼저 넣은 것이 먼저 나오므로 선입선출(FIFO, First In First Out)이다. 은행 번호표처럼 도착한 순서대로 처리해야 할 때, 예를 들어 프린터 작업 대기열이나 운영체제의 작업 스케줄링에 쓴다. 스택 예와 같은 순서로 1, 2, 3을 넣은 뒤 한 번 빼면 1이 나온다. 이어서 4를 넣고 두 번 빼면 2, 3이 차례로 나와, 나온 순서는 1, 2, 3이고 4가 남는다.

덱(deque, double-ended queue)은 양쪽 끝 모두에서 넣고 뺄 수 있는 자료구조다. 시험 자료는 데크라고도 적는다. 한쪽만 쓰면 스택처럼, 양 끝을 나눠 쓰면 큐처럼 동작한다.

그래프와 최대 간선 수

그래프(graph)는 정점(vertex)과 정점을 잇는 간선(edge)으로 이루어진 구조다. 간선에 방향이 있으면 방향 그래프(directed graph), 없으면 무방향 그래프(undirected graph)라 한다. 도로망이나 친구 관계처럼 여러 대상이 서로 얽힌 관계를 나타낸다.

정점이 n개일 때 간선이 가장 많은 경우는 모든 정점 쌍이 이어진 경우다.

그래프	최대 간선 수	n = 5일 때
무방향	n(n−1)/2	10
방향	n(n−1)	20

무방향 그래프는 정점 n개에서 두 개를 고르는 쌍의 수만큼 간선이 생긴다. 방향 그래프는 A에서 B로 가는 간선과 B에서 A로 가는 간선을 따로 세므로 두 배가 된다. 모든 정점 쌍이 이어진 그래프를 완전 그래프(complete graph)라 한다.

시험 포인트

• 비선형 구조 → 트리, 그래프. 나머지(배열·리스트·스택·큐·덱)는 선형.
• 한쪽 끝에서만 입출력, 후입선출 → 스택(LIFO). 선입선출 → 큐(FIFO). 양 끝 입출력 → 덱.
• 가득 찬 스택에 삽입 → 오버플로, 빈 스택에서 삭제 → 언더플로.
• 최대 간선 수: 무방향 n(n−1)/2, 방향 n(n−1).