자료구조 | 배열, 스택, 큐

선형 자료구조

데이터를 효과적으로 관리 및 접근하는 방법은 소프트웨어 개발에서 중요한 요소이다. '자료구조 (Data Structure)'는 그 이름에 걸맞게 데이터를 저장, 관리, 조작하기 위한 구조적인 방법을 의미한다.

 

그 중에서도 선형 자료구조는 이름에서도 알 수 있듯, 데이터 요소들이 선(linear)처럼 일렬로 연결되어 있는 자료구조이다. 선형 구조는 데이터의 시작부터 끝까지 순차적으로 접근한다는 특징을 가진다. 

 

대표적인 선형 자료구조는 다음과 같다.

- 기본적인 자료구조: 배열, 문자열, 스택, 큐, 연결 리스트 (단순 연결 리스트)
- 심화(응용) 자료구조: 연결 리스트의 변형 (이중 연결 리스트, 원형 연결 리스트), 큐의 변형 (덱)

 

아래는 위 리스트 중에서 배열, 스택, 큐, 덱에 대한 간단한 정리! 

---

배열 (Array)

연속된 메모리 공간에 같은 타입의 데이터를 순서대로 저장하는 구조

• 각 요소는 인덱스를 통해 직접 접근이 가능하다.
• 배열 중간에 데이터를 추가나 삭제할 경우엔 데이터를 재배치해야하는 단점이 있음.
• 기본 배열: 처음 배열 선언할 때 메모리를 할당하고, 이후에 그 크기를 바꿀 수 없음.
• 파이썬의 리스트는 동적 배열 (Dynamic Array) 사용
  • 배열의 크기는 처음에 자동으로 설정 (적은 용량)
  • 만약 배열의 크기가 다 찼다면, 메모리를 재할당하고 데이터를 복사하는 과정을 자동으로 수행
  • 배열의 크기가 작아졌을 때도 마찬가지로 자동으로 관리

 

스택(Stack)과 큐(Queue), 덱(Deque)

	스택 (Stack)	큐 (Queue)	덱 (Deque)
특징	1. LIFO 구조 (후입선출) 2. 주요 연산: • push(item): 스택의 맨 위에 항목을 추가한다. • pop(): 스택의 맨 위 항목을 제거하고 반환한다. • top(): 스택의 맨 위 항목을 조회한다. • is_empty(): 스택이 비어있는지 확인한다. • __len__(): 스택에 쌓여있는 데이터 개수(stk 값)를 반환한다.	1. FIFO 구조 (선입선출) 2. 주요 연산: • enqueue(item): 큐의 끝에 항목을 추가한다. • dequeue(): 큐의 처음 항목을 제거하고 반환한다. • front(): 큐의 처음 항목을 조회한다. • is_empty(): 큐가 비어있는지 확인한다.	1. 큐의 변형된 형태. 데크는 양쪽 끝에서 데이터를 추가하거나 제거할 수 있는 자료구조로, 스택과 큐의 기능을 모두 포함한다. 2. 주요 연산: ◦ append(item): 덱의 오른쪽 끝에 항목을 추가한다. ◦ appendleft(item): 덱의 왼쪽 끝에 항목을 추가한다. ◦ pop(): 덱의 오른쪽 끝 항목을 제거하고 반환한다. ◦ popleft(): 덱의 왼쪽 끝 항목을 제거하고 반환한다. ◦ front(): 덱의 왼쪽 끝 항목을 조회한다. ◦ rear(): 덱의 오른쪽 끝 항목을 조회한다. ◦ is_empty(): 덱이 비어있는지 확인한다.
장점	1. 간단한 구조 2. 데이터 추가, 삭제가 O(1)로 빠르다. 3. 함수 호출과 같은 컴퓨터 내부의 프로세스에서 사용될 때, 구조가 직관적이다.	1. 데이터 순서 유지 2. 데이터 추가, 삭제가 O(1)로 빠르다.	1. 양쪽 끝에서의 데이터 추가와 삭제가 O(1)로 빠르다. 2. 스택과 큐의 기능을 모두 포함하고 있다.
단점	1. 스택의 크기가 제한적일 경우, 스택 오버플로우(stack overflow)가 발생할 수 있다. 2. 스택의 중간 데이터에 접근하기 위해서는 많은 데이터를 pop해야 하기 때문에 비효율적이다.	1. 큐의 크기가 제한적일 경우, 큐 오버플로우(queue overflow)가 발생할 수 있다. 2. 큐의 중간 데이터에 접근하기 위해서는 많은 데이터를 dequeue해야 하기 때문에 비효율적이다.	1. 중간 데이터에 접근하기 위해서는 인덱스를 통해 접근해야 하기 때문에 비효율적이다.
용도	1. 함수 호출: 컴퓨터에서 함수 호출을 관리하는데 사용된다. 2. 백트래킹: 스택은 알고리즘에서 백트래킹 (특히 깊이 우선 탐색, DFS) 시 사용된다. 예를 들어 미로 찾기 문제에서 방문한 경로를 스택에 저장하고, 더 이상 진행할 수 없을 때 이전 경로로 돌아가는 용도로 사용된다. 3. 웹 브라우저 방문 기록: 웹 브라우저의 뒤로 가기 기능은 스택을 사용하여 구현된다고 한다.	1. 데이터의 순서대로 처리: 작업 스케줄링, 이벤트 처리 등에서 사용된다. 2. 너비 우선 탐색 (BFS): 그래프에서 너비 우선 탐색을 수행할 때 사용된다. 3. 캐시 알고리즘: FIFO 캐시 알고리즘 등에서 활용된다. 4. 멀티태스킹: 운영체제에서 여러 작업을 관리할 때, 준비 상태의 프로세스를 큐에 저장하여 CPU 스케줄링을 할 때 사용된다. 5. 메시지 큐: 시스템 간의 비동기 메시지를 전송하거나 처리할 때 사용되는 데이터 구조이다. 6. 프린터 대기열: 여러 문서의 인쇄 요청을 순서대로 처리하기 위해 사용된다.	1. 양방향으로 데이터를 처리해야 하는 경우에 유용하다. (예: Palindrome 체크) 2. 스크롤 등의 UI 구현에서 사용된다.

 

(출처: Do it! 자료구조와 함께하는 알고리즘 입문)

- 스택 배열: stk (스택 본체인 list형 배열)

- 스택 크기: capacity (스택의 최대 크기를 나타내는 int형 정수. 이 값은 배열 stk의 원소 수인 len(stk)와 일치함)

- 스택 포인터: ptr (스택에 쌓여 있는 데이터의 개수를 나타내는 정숫값. 비어있으면 ptk == 0, 가득 차 있으면 ptk == capacity)