스택(Stack)
스택의 개념
스택(stack)은 제한적으로 접근할 수 있는 나열 구조입니다. 그 접근 방법은 언제나 목록의 끝에서만 일어나게 됩니다.
스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있습니다. 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된니다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO(Last In First Out) 구조라고 합니다.
그리고 비어있는 스택에서 원소를 추출하려고 할 때 stack underflow라고 하며,
스택이 넘치는 경우 stack overflow라고 합니다. (우리가 흔히 접하는 유명한 사이트의 이름이 여기서 유래되었습니다)
스택의 활용 예시
- 웹 브라우저의 방문기록 (뒤로가기)
- 실행 취소 (가장 나중에 실행된 명령부터 취소)
- 역순 문자열 만들기 (가장 나중에 입력된 문자열부터 출력)
- 재귀 알고리즘에서 유용하게 사용
- 하노이의탑(유명한 알고리즘)
큐(Queue)
큐의 개념
Queue 의 사전적 의미는 1. (무엇을 기다리는 사람, 자동차 등의) 줄 , 혹은 줄을 서서 기다리는 것을 의미합니다.
따라서 일상생활에서 놀이동산에서 줄을 서서 기다리는 것, 은행에서 먼저 온 사람의 업무를 창구에서 처리하는 것과 같이
선입선출(FIFO, First in first out) 방식의 자료구조입니다.
정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리
큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어지게 됩니다.
이때 삭제연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)로 정하여 각각의 연산작업만 수행됩니다. 이때, 큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue)
프론트에서 이루어지는 삭제연산을 디큐(dnQueue)라고 부르고 있습니다.
큐의 활용 예시
- 프로세스 관리
- 캐시(Cache) 구현
- 우선순위가 같은 작업 예약(프린터의 인쇄 대기열)
- 너비우선탐색 구현(BFS)
시간복잡도
스택과 큐 모두 데이터의 삽입/삭제의 경우 O(1)의 시간복잡도를 가지고 있습니다. 그래서 데이터의 삽입과 삭제가 매우 빠르다는 장점을 가지고 있습니다.
