정의, 특징, 시간복잡도, 선형/비선형 자료구조
Stack
정의:
한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO 자료 구조
특징:
- 가장 최근에 들어온 자료를 가리키는 포인터를 top이라고 한다.
- 자료의 삽입과 삭제는 top에서만 이루어진다.
- 스택이 비어 있을 때 데이터를 꺼내려고 할 때 stack underflow가 발생하고, 스택이 차있을 때 자료를 꺼내려 하면 Stack Overflow가 발생한다.
예시:
- 재귀적 알고리즘
- ctrl + z
- 각 프로세스의 변수 할당 등에 활용
Queue
정의:
front에서 자료의 삭제, rear에서 자료의 삽입이 이루어지는 FIFO 자료 구조
특징:
- stack의 top과 다르게 head, tail 2개의 포인터를 사용한다. head는 추가된지 가장 오래된 데이터를 가리키며, tail은 가장 최근에 들어온 데이터 index + 1을 가리킨다.
- head와 tail이 같은 값이면 비어있는 큐이며, 이때 데이터를 꺼내려고 하면 queue underflow가 발생한다.
- head = tail + 1이면 꽉찬 큐이며, 이때 데이터를 추가하려고 하면 queue overflow가 발생한다.