스택 Stack
한 쪽으로만 데이터를 넣고 뺄 수 있는 LIFO 형식의 자료구조
LIFO (Last In First Out) : 후입선출, 마지막으로 들어온 값이 먼저 나가는 것
- 프링글스를 먹을 때 처럼 정해진 입구를 통해 차례대로 쌓인 데이터에 접근을 함
- 데이터의 삽입, 삭제 연산은 top 에서만 가능
- 메모리 공간에서의 스택 영역은 함수의 호출과 관계되는 지역 변수와 매개변수가 저장되는 임시 메모리 영역이다
- 스택 영역은 함수의 호출과 함께 할당되고 함수의 호출이 완료되면 소멸함
연산
- pop(): 스택의 가장 위에 있는 데이터를 제거하고 반환
- push(item): 데이터 item을 스택의 가장 위에 추가
- peek(): 스택의 가장 위에 있는 데이터를 반환
- isEmpty(): 스택이 비어있으면 true를 반환
- isFull(): 스택이 가득 차있으면 true를 반환
데이터의 삽입, 삭제가 top에서 바로 이루어지기 때문에 O(1)의 시간복잡도를 가짐
구현 방법
- 배열
- 데이터를 저장할 배열과 스택의 가장 위에 있는 데이터를 가리키는 top 변수가 필요함
- 구현이 간단하지만 배열의 크기가 정해져 있어서 overflow 발생 가능
- 연결리스트
- 스택의 가장 위에 있는 데이터를 가리키는 top이 필요하고 다음(밑)에 있는 데이터를 가리켜야 함
- 데이터 추가 시 동적할당을 받으므로 런타임시 필요에 따라 크기를 확장 및 축소시킬 수 있음
- 포인터를 위한 추가 메모리 공간이 필요함
활용 예시
- 재귀 알고리즘 (예:
DFS) - 후위 표기법
- 괄호 검사
큐 Queue
한쪽 끝에서 데이터를 삽입하고 다른 한쪽 끝에서 데이터를 빼는 FIFO 형식의 자료구조
FIFO (First In First Out) : 선입선출, 처음 들어온 값이 먼저 나가는 것
- 사람들이 줄을 설 때 처럼 입구에 먼저 들어온 데이터가 출구를 통해 먼저 나감
- 데이터의 삽입은 rear을 통해, 삭제는 front를 통해 발생
연산
- enqueue(item): 큐의 끝(rear)에 item을 추가
- dequeue(): 큐의 앞(front)에 있는 데이터를 삭제 및 반환
- peek(): 큐의 맨 앞(front)에 있는 데이터 반환
- isEmpty(): 큐가 비어있으면 true를 반환
- isFull(): 큐가 가득 차있으면 true를 반환
데이터의 삽입, 삭제가 rear, front에서 바로 이루어지기 때문에 O(1)의 시간복잡도를 가짐
구현 방법
- 배열
- 데이터를 저장할 배열과 큐의 앞,뒤를 가리키는 front, rear 변수 필요
- 구현이 간단하지만 넣을 수 있는 데이터의 개수가 정해져 있음
- 연결리스트
- 큐의 앞, 뒤를 가리키는 front, rear 변수 필요
- 데이터 추가 시 동적할당을 받으므로 런타임시 필요에 따라 크기를 확장 및 축소시킬 수 있음
- 포인터를 위한 추가 메모리 공간이 필요함
선형 큐의 문제점
- 배열로 구현 시 크기가 제한되어 있음
- 데이터의 삽입, 삭제 작업이 계속 일어나면 rear과 front가 증가하므로 이전의 index를 재사용할 수 없음
- 큐가 비어있어도 자료를 삽입하지 못하는 상황 발생
원형 큐 (Circular Queue)로 해결. 
- 배열의 처음과 끝이 연결된 형태, 원으로 생각하면 이해가 쉬움
- %(나머지 연산자)로 빈 공간을 재사용함
활용 예시
- CPU/디스크 스케줄링
- IO 버퍼, 파이프
- BFS
- 캐시(Cache)
스택과 큐 모두 끝부분 이외에 있는 (중간의) 데이터에 접근할 수 없다.
탐색하려면 모든 데이터를 꺼내면서 진행해야 하고 이때 시간복잡도는 O(n)이다.
출처 및 참고
[자료구조] 스택 Stack, 큐 Queue, 덱 Deque
[자료구조] 스택 (Stack)
[자료구조] 큐 (Queue)
스택 (Stack) - 배열, 연결리스트로 구현
큐(Queue) - 배열, 연결리스트로 구현
