06｜자료구조: 리스트·스택·큐·데크

자료 구조는 데이터를 일정한 규칙에 따라 저장하고, 필요한 데이터를 효율적으로 검색·삽입·삭제·수정할 수 있도록 구성하는 방법입니다. 같은 데이터라도 어떤 자료 구조에 저장하는지에 따라 처리 속도와 메모리 사용량이 달라질 수 있습니다.

이 장에서는 자료 구조를 선형 구조와 비선형 구조로 구분하고, 선형 구조에 해당하는 리스트·스택·큐·데크의 특징과 연산 방식을 정리합니다. 배열 기반 리스트와 연결 리스트의 차이, 스택의 삽입·삭제 알고리즘, 스택 가드, 0주소 명령어와 스택의 관계도 함께 살펴봅니다.

자료 구조란 무엇인가?

자료 구조(Data Structure)는 데이터를 컴퓨터의 기억장치에 어떤 형태로 저장하고, 저장된 데이터에 어떤 연산을 적용할지를 정의하는 체계입니다. 자료 구조를 선택할 때는 데이터의 관계, 검색 빈도, 삽입·삭제 빈도, 메모리 사용량과 구현 복잡도를 함께 고려해야 합니다.

예를 들어 데이터의 특정 위치에 자주 접근해야 한다면 배열 기반 구조가 유리할 수 있고, 중간에 데이터를 자주 삽입하거나 삭제한다면 연결 리스트가 적합할 수 있습니다. 마지막에 들어온 데이터를 먼저 처리해야 한다면 스택을, 먼저 들어온 데이터를 먼저 처리해야 한다면 큐를 사용할 수 있습니다.

자료 구조는 어떻게 분류할까?

자료 구조는 데이터가 연결되는 형태에 따라 선형 구조와 비선형 구조로 구분할 수 있습니다.

구분	의미	대표 구조
선형 구조	데이터가 앞과 뒤의 순차적인 관계를 가지는 구조	리스트, 스택, 큐, 데크
비선형 구조	하나의 데이터가 여러 데이터와 계층적 또는 망형 관계를 가지는 구조	트리, 그래프

자료 구조는 어디에 활용될까?

자료 구조는 단순한 데이터 저장뿐 아니라 정렬, 검색, 인덱스와 파일 편성 등 여러 처리 과정의 기반이 됩니다.

활용 분야	의미	대표 사례
정렬 Sort	데이터를 일정한 기준에 따라 다시 배열	오름차순, 내림차순, 버블 정렬, 선택 정렬
검색 Search	저장된 데이터 가운데 원하는 값을 탐색	순차 검색, 이진 검색
인덱스 Index	원본 데이터의 위치를 빠르게 찾기 위한 보조 자료 구조	B-트리 인덱스, 범위 검색
파일 편성	저장장치에서 레코드를 물리적·논리적으로 배열하는 방식	순차 편성, 색인 편성, 직접 편성

정렬과 검색

정렬은 흩어진 데이터를 특정 기준에 따라 순서대로 배치하는 작업입니다. 오름차순은 작은 값에서 큰 값으로, 내림차순은 큰 값에서 작은 값으로 배열합니다.

검색은 저장된 데이터 중에서 원하는 값을 찾는 작업입니다. 순차 검색은 처음부터 하나씩 비교할 수 있지만, 이진 검색은 데이터가 정렬되어 있어야 하며 검색 범위를 반복적으로 절반씩 줄입니다.

인덱스

인덱스는 원본 데이터의 모든 내용을 다시 저장하기보다 검색에 사용할 키와 데이터의 위치 정보를 별도의 구조로 관리하여 조회 속도를 높입니다. 인덱스를 추가하면 검색은 빨라질 수 있지만 별도의 저장 공간이 필요하고 데이터 삽입·수정·삭제 시 인덱스도 함께 갱신해야 합니다.

B-트리 계열 인덱스는 정렬 가능한 값을 계층적으로 관리하며 동일값 검색뿐 아니라 특정 범위를 찾는 조건에도 활용할 수 있습니다.

리스트란 무엇인가?

리스트(List)는 데이터가 순서에 따라 나열된 선형 자료 구조입니다. 각 데이터는 리스트 안에서 위치를 가지며, 구현 방식에 따라 배열을 이용한 순차 저장 방식과 노드를 연결하는 연결 리스트 방식으로 나눌 수 있습니다.

순차 리스트

순차 리스트는 배열처럼 데이터 항목을 연속된 기억장소에 저장합니다. 각 원소의 위치를 계산하여 직접 접근할 수 있으므로 특정 위치의 값을 빠르게 조회할 수 있습니다.

그러나 리스트 중간에 원소를 삽입하거나 삭제하면 뒤에 있는 원소들을 이동해야 할 수 있습니다. 고정 크기 배열에서는 처음 정한 용량을 초과할 때 새로운 공간을 확보하는 과정도 필요합니다.

연결 리스트

연결 리스트(Linked List)는 데이터를 저장하는 노드와 다음 노드를 가리키는 링크를 연결하여 구성합니다. 각 노드는 기억장치의 연속된 위치에 저장될 필요가 없습니다.

삽입하거나 삭제할 노드의 위치를 이미 알고 있다면 주변 링크만 변경하여 처리할 수 있습니다. 반면 특정 순번의 원소를 찾으려면 앞쪽 노드부터 링크를 따라 이동해야 하며, 링크를 저장하기 위한 추가 공간도 필요합니다.

비교 항목	순차 리스트	연결 리스트
저장 방식	연속된 기억장소에 저장	노드가 링크로 연결되며 위치가 연속적일 필요 없음
위치 접근	인덱스로 직접 접근 가능	앞에서부터 링크를 따라 이동
중간 삽입·삭제	뒤 원소의 이동이 필요할 수 있음	대상 위치를 알면 링크 변경으로 처리 가능
추가 공간	일반적으로 데이터 저장 공간 중심	노드마다 링크 저장 공간 필요
공간 확장	배열 크기 변경이나 재할당이 필요할 수 있음	새 노드를 개별적으로 할당 가능
캐시 효율	연속 저장으로 상대적으로 유리	노드가 흩어져 있어 상대적으로 불리할 수 있음

스택이란 무엇인가?

스택(Stack)은 한쪽 끝에서만 데이터의 삽입과 삭제가 이루어지는 선형 자료 구조입니다. 가장 나중에 삽입된 데이터가 가장 먼저 삭제되므로 후입선출(LIFO, Last In First Out) 방식이라고 합니다.

데이터를 삽입하고 삭제하는 쪽을 Top이라고 하며, 스택의 가장 아래쪽을 Bottom이라고 합니다. 스택에 데이터를 넣는 연산은 push, 가장 위 데이터를 꺼내는 연산은 pop, 삭제하지 않고 확인하는 연산은 peek 또는 top이라고 합니다.

연산	의미	상태 변화
push	스택의 Top에 데이터를 삽입	저장된 원소 수 증가
pop	스택의 Top 데이터를 삭제하고 반환	저장된 원소 수 감소
peek	Top 데이터를 삭제하지 않고 확인	변화 없음
isEmpty	스택이 비어 있는지 확인	변화 없음
isFull	고정 크기 스택이 가득 찼는지 확인	변화 없음

스택의 삽입 알고리즘

배열의 첫 번째 위치를 0번으로 사용하고, 빈 스택의 Top을 −1로 표현한다고 가정합니다.

push(데이터)
    만약 Top = 스택 용량 - 1이면
        오버플로 처리
    그렇지 않으면
        Top ← Top + 1
        스택[Top] ← 데이터

스택의 삭제 알고리즘

pop()
    만약 Top = -1이면
        언더플로 처리
    그렇지 않으면
        데이터 ← 스택[Top]
        Top ← Top - 1
        데이터 반환

스택은 어디에 활용될까?

활용 분야	스택을 사용하는 이유
함수 호출과 복귀	복귀 주소, 매개변수와 지역 변수 등의 호출 정보를 역순으로 복원
재귀 호출	함수 호출마다 실행 상태를 스택 프레임에 저장
인터럽트 처리	현재 실행 상태를 저장한 뒤 처리 완료 후 이전 상태로 복귀
수식 계산	괄호 검사, 연산자 우선순위 처리와 후위 표기식 계산
0주소 명령어	연산 대상이 명령어에 직접 나타나지 않고 스택의 Top에서 암시적으로 결정
되돌리기	가장 최근 작업부터 역순으로 취소
깊이 우선 탐색	최근 방문한 경로부터 되돌아가며 탐색
미로 탐색	이동 경로를 저장하고 막힌 지점에서 이전 위치로 복귀

0주소 명령어와 스택

0주소 명령어는 명령어 안에 연산 대상의 주소를 명시하지 않습니다. 연산에 필요한 피연산자를 스택의 Top에서 꺼내 사용하고, 연산 결과를 다시 스택에 저장합니다.

스택 가드란 무엇인가?

스택 가드(Stack Guard) 또는 스택 카나리(Stack Canary)는 함수의 스택 영역에 특정한 보호 값을 저장해 두었다가 함수가 반환되기 전에 값이 변조되었는지 검사하는 보안 기법입니다.

버퍼 오버플로 등으로 스택의 제어 정보가 손상되는 과정에서 보호 값도 함께 변경되면 프로그램은 비정상 상태를 감지하고 실행을 중단할 수 있습니다. 보호 값의 구체적인 위치와 구현 방식은 컴파일러와 시스템 구조에 따라 달라질 수 있습니다.

스택의 출력 순서는 어떻게 결정될까?

A, B, C, D를 차례로 push한 뒤 모든 원소를 pop하면 가장 마지막에 들어온 D부터 출력됩니다.

연산	스택 상태	출력
push A	A	—
push B	A, B	—
push C	A, B, C	—
push D	A, B, C, D	—
모두 pop	비어 있음	D → C → B → A

연산 순서 계산 사례

입력 자료를 A, B, C, D 순서로 사용하며 다음 연산을 수행한다고 가정합니다.

순서	연산	사용 데이터	스택 상태	출력
1	push	A	A	—
2	push	B	A, B	—
3	pop	—	A	B
4	push	C	A, C	—
5	push	D	A, C, D	—
6	pop	—	A, C	D
7	pop	—	A	C
8	pop	—	비어 있음	A

큐란 무엇인가?

큐(Queue)는 한쪽 끝에서 데이터를 삽입하고 다른 쪽 끝에서 데이터를 삭제하는 선형 자료 구조입니다. 기본적인 큐에서는 먼저 삽입된 데이터가 먼저 삭제되므로 선입선출(FIFO, First In First Out) 방식으로 동작합니다.

데이터를 삭제하는 앞쪽을 Front, 데이터를 삽입하는 뒤쪽을 Rear라고 합니다. 큐에 데이터를 넣는 연산은 enqueue, 앞쪽 데이터를 꺼내는 연산은 dequeue라고 합니다.

연산	위치	의미
enqueue	Rear	큐의 뒤쪽에 데이터를 삽입
dequeue	Front	큐의 앞쪽 데이터를 삭제하고 반환
front·peek	Front	삭제하지 않고 가장 앞 데이터를 확인

큐의 활용 분야

1. 작업 스케줄링 — 준비된 작업을 도착 순서나 정책에 따라 관리합니다.
2. 입출력 버퍼 — 생산된 데이터와 소비되는 데이터의 처리 속도 차이를 조절합니다.
3. 프린터 대기열 — 먼저 요청된 인쇄 작업부터 처리합니다.
4. 네트워크 패킷 처리 — 도착한 패킷을 대기열에 저장한 뒤 순차적으로 처리합니다.
5. 너비 우선 탐색 — 먼저 발견한 정점부터 차례로 탐색합니다.

데크란 무엇인가?

데크(Deque, Double-Ended Queue)는 앞과 뒤 양쪽 끝에서 데이터의 삽입과 삭제를 모두 수행할 수 있는 선형 자료 구조입니다. 스택과 큐의 기능을 함께 표현할 수 있어 양방향 큐라고도 합니다.

배열로 구현할 때는 일반적으로 Front와 Rear 인덱스를 사용하고, 연결 구조로 구현할 때는 앞과 뒤 노드를 가리키는 링크나 포인터를 사용할 수 있습니다. 두 개의 포인터를 사용한다는 것은 대표적인 구현 방법이며 데크 자체의 정의는 양쪽 끝에서 연산할 수 있다는 점입니다.

연산	의미
addFirst	앞쪽에 데이터 삽입
addLast	뒤쪽에 데이터 삽입
removeFirst	앞쪽 데이터 삭제
removeLast	뒤쪽 데이터 삭제

스택·큐·데크 비교

비교 항목	스택	큐	데크
처리 원리	후입선출	기본적으로 선입선출	양쪽 끝에서 처리
삽입 위치	Top	Rear	Front와 Rear
삭제 위치	Top	Front	Front와 Rear
대표 포인터	Top	Front, Rear	Front, Rear
대표 연산	push, pop	enqueue, dequeue	addFirst, addLast, removeFirst, removeLast
대표 활용	함수 호출, 재귀, 되돌리기	작업 대기열, 버퍼, 너비 우선 탐색	양방향 탐색, 슬라이딩 윈도, 작업 관리

시험에서 자주 혼동되는 개념

이번 장 핵심 요약

1. 자료 구조는 데이터를 저장하고 처리하기 위한 관계와 연산을 정의합니다.
2. 선형 구조에는 리스트·스택·큐·데크가 있고, 비선형 구조에는 트리와 그래프가 있습니다.
3. 순차 리스트는 연속된 기억장소를 사용하고 인덱스 접근에 유리합니다.
4. 연결 리스트는 노드와 링크를 사용하며 대상 위치를 알고 있을 때 삽입·삭제가 편리합니다.
5. 스택은 Top에서만 삽입·삭제하는 후입선출 구조입니다.
6. 스택의 대표 연산은 push·pop·peek입니다.
7. 가득 찬 스택에 삽입하면 오버플로, 빈 스택에서 삭제하면 언더플로가 발생합니다.
8. 0주소 명령어는 스택의 Top에 있는 피연산자를 암시적으로 사용합니다.
9. 스택 가드는 보호 값을 검사해 스택 메모리의 손상을 탐지합니다.
10. 기본 큐는 Rear에서 삽입하고 Front에서 삭제하는 선입선출 구조입니다.
11. 데크는 Front와 Rear 양쪽에서 삽입과 삭제가 가능합니다.
12. 스택·큐·데크는 배열 또는 연결 리스트 방식으로 구현할 수 있습니다.
13. A·B·C·D를 스택에 차례로 넣으면 전체 출력 순서는 D·C·B·A입니다.
14. push·push·pop·push·push·pop·pop·pop 연산의 출력 결과는 B·D·C·A입니다.

복습 문제

선형 자료 구조와 비선형 자료 구조의 차이는?

선형 자료 구조는 데이터가 순차적인 관계를 가지며, 비선형 자료 구조는 하나의 데이터가 여러 데이터와 계층적 또는 망형 관계를 가질 수 있습니다.

트리와 그래프는 선형 구조와 비선형 구조 중 어디에 해당할까?

비선형 자료 구조에 해당합니다.

순차 리스트와 연결 리스트의 가장 중요한 차이는?

순차 리스트는 데이터를 연속된 기억장소에 저장하고, 연결 리스트는 떨어진 위치의 노드들을 링크로 연결합니다.

연결 리스트에서 중간 노드의 삽입·삭제가 편리한 이유는?

삽입·삭제 위치를 알고 있다면 많은 원소를 이동하지 않고 주변 노드의 링크만 변경할 수 있기 때문입니다.

스택의 데이터 처리 방식은?

가장 나중에 삽입된 데이터가 가장 먼저 삭제되는 후입선출 방식입니다.

스택의 삽입과 삭제 연산은 각각 무엇일까?

삽입은 push, 삭제는 pop입니다.

스택 오버플로와 언더플로의 차이는?

오버플로는 가득 찬 스택에 데이터를 삽입할 때 발생하고, 언더플로는 빈 스택에서 데이터를 삭제할 때 발생합니다.

0주소 명령어에서 반드시 필요한 자료 구조는?

스택입니다. 연산 대상이 명령어 안에 직접 표시되지 않고 스택의 Top에 있는 값으로 결정됩니다.

스택 가드는 어떤 기능을 수행할까?

스택에 저장한 보호 값이 변조되었는지 검사하여 버퍼 오버플로 등에 의한 스택 메모리 손상을 탐지합니다.

A, B, C, D를 차례로 스택에 넣은 뒤 모두 꺼내면 출력 순서는?

D → C → B → A입니다.

기본 큐의 데이터 처리 방식은?

가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 선입선출 방식입니다.

큐에서 데이터를 삽입하고 삭제하는 위치는?

Rear에서 삽입하고 Front에서 삭제합니다.

앞과 뒤 양쪽에서 삽입과 삭제가 가능한 자료 구조는?

데크(Deque)입니다.

스택과 큐의 기능을 모두 표현할 수 있는 자료 구조는?

데크입니다. 한쪽 끝만 사용하면 스택으로, 뒤에서 삽입하고 앞에서 삭제하면 큐로 사용할 수 있습니다.

push·push·pop·push·push·pop·pop·pop 순서로 A·B·C·D를 사용하면 출력 결과는?

B → D → C → A입니다.