Data Structure(1) Stack (스택), Queue (큐)

스택(Stack), 그리고 큐(Queue)는 모두 '자료구조'의 한 종류이다.

처리해야 할 데이터가 많아졌을 때, 어떤 순서로 저장하고 처리해야 할지를 정해둔 방식이라고 할 수 있다.

스택은 가장 마지막에 쌓인 데이터를 먼저 처리하고, 큐는 가장 먼저 쌓인 데이터를 처리한다는 점에서 차이가 있다.

데이터들을 임시 저장하는 가장 기본적인 자료구조인 스택(Stack), 큐(Queue)에 대해 좀 더 알아보자...

 

🤷‍♀️스택(Stack)

---

✏️스택(Stack)은 제한적으로 접근할 수 있는 나열 구조이다.

접근 방법은 언제나 목록의 끝에서만 일어난다.

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형구조(LIFO - Last In First Out)로 되어 있다.

 

스택은 '쌓다', '쌓이다', '포개지다'와 같은 뜻을 가지고 있다.

마치 접시를 쌓아 놓은 형태와 비슷한 이 자료구조는 자료(data)를 쌓는 자료구조이다.

(접시를 차곡차곡 쌓아 올린 형태의 자료구조는 스택 자료구조라고 할 수 있다.)

이렇게 가장 마지막에 쌓인 데이터부터 가져갈 수 있고, 새로 저장할 때도 가장 마지막 부분에 쌓아야하는 데이터 구조를 '스택(Stack)'이라고 한다.

스택 구조는 자료가 들어오고 나가는 입구가 딱 한 곳이고, 한 번에 하나의 데이터만 처리할 수 있다.

이러한 스택의 구조를 후입선출(LIFO, Last-In-First-Out) 구조라고 한다.

스택은 위 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있다.

top에는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.

스택에서 자료를 삭제할 때에도 top을 통해서만 가능하다.

스택에서 top을 통해 삽입하는 연산을 'push', top을 통한 삭제하는 연산을 'pop'이라고 한다.

스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가지게 된다. (후입선출(LIFO, Last-In-First-Out) 구조)

비어있는 스택에서 원소를 추출하려고 할 때 stack underflow라고 하며, 스택이 넘치는 경우 stack overflow라고 한다.

스택의 push, pop, size 예시

스택의 활용 예시

• 웹 브라우저 방문 기록(뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
• 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
• 후위 표기법 계산
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

시간 복잡도(Big - O)

 

👇스택 시간 복잡도

Insertion(삽입하는 경우)	O(1)
Deletion(삭제하는 경우)	O(1)
Search(탐색, 가져오기)	O(n)

 

스택에 데이터를 추가하거나 삭제하는 데 걸리는 시간은 모두 O(1)이다. 맨 위에 있는 요소를 꺼내고 맨 위에 데이터를 쌓기 때문에 따로 요소들을 하나씩 확인할 필요가 없기 때문이다.

 

하지만 데이터를 가져오려면 O(n)의 시간이 걸린다.

빅오 표기법은 최악의 경우를 계산하는 방법인데, 스택에서 최악의 경우는 제일 아래 있는 (가장 먼저 들어온) 데이터를 가져오는 경우이기 때문이다.

위에 쌓인 모든 데이터를 꺼내야 가장 아래있는 데이터를 가져올 수 있어서 n개의 데이터를 하나씩 스캔해야 한다.

추가로 스택은 재귀 알고리즘에서 유용하게 사용된다.

 

 

🤷‍♀️큐(Queue)

---

큐(Queue)의 사전적 의미는 1. 무엇을 기다리는 사람, 자동차 등의 줄, 혹은 줄을 서서 기다리는 것을 의미한다.

일상생활에서 놀이동산에서 줄을 서서 기다리는 것, 은행에서 먼저 온 사람의 업무를 창구에서 처리하는 것과 같이 선입선출(FIFO, First In First Out) 방식의 자료구조를 말한다.

(가장 먼저 들어온 데이터를 가장 먼저 처리하는 방식을 큐(Queue)라고 한다.)

스택과는 달리 자료가 들어오고 나가는 곳이 두 곳이나 있다.

큐는 어떤 작업을 순서대로 실행하거나, 사용을 위해 대기를 시켜야 하는 경우에 사용한다.

큐의 enqueue, dequeue 메서드

 

정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리 큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.

이때 삭제연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)로 정하여 각각의 연산 작업만 수행하게 된다.

이 때 큐의 리어에서 이루어지는 삽입 연산을 인큐(enqueue), 프런트에서 이루어지는 삭제연산을 디큐(enqueue)라고 부른다.

큐에서 프론트 원소는 가장 먼저 큐에 들어왔던 첫 번째 원소가 되는 것이고, 리어 원소는 가장 늦게 큐에 들어온 마지막 원소가 되는 것이다.

 

큐의 활용 예시

• 우선순위가 같은 작업 예약(프린터의 인쇄 대기열)
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 캐시(Cache) 구현

시간 복잡도(Big - O)

 

👇큐 시간 복잡도

Insertion(삽입하는 경우)	O(1)
Deletion(삭제하는 경우)	O(1)
Search(탐색, 가져오기)	O(n)

 

큐(Queue) 역시 스택(Stack)과 동일한 시간 복잡도를 가진다.

추가, 삭제는 맨 앞이나 맨뒤에서만 진행되기 때문에 O(1)의 시간이 걸리고, 데이터를 가져올 땐 최악의 경우 n개의 데이터를 스캔해야 하기 때문에 O(n)이 걸리게 된다.