스택(Stack)과 큐(Queue)

스택(Stack)

 

- 스택은 데이터를 한 열로 저장합니다. 하지만 후입선출(Last In First Out) 구조로 나중에 들어간 것이 먼저 나오는 구조입니다.

- 링 던지기 게임이 스택의 예시입니다.

 

- 데이터의 추가는 push라고 불리며, 스택 내부에 데이터가 쌓입니다.

- 데이터의 삭제는 pop이라 불리며, 스택에 가장 마지막에 들어갔던 데이터가 나오게 됩니다.

 

ex) A만 들어가 있는 스택이 있다. 스택에 B, C를 넣어보자.

1) 스택에 B를 push한다. (A-B)

2) 스택에 C를 push한다. (A-B-C)

3) 스택에서 pop을 한다. (A-B)

4) 스택에서 pop을 한다. (A)

 

예시에서 처럼 가장 나중에 들어간 데이터가 가장 먼저 나오게 되는 구조가 바로 스택이다.

스택이 가장 많이 활용되는 부분이 바로 "괄호문제"이다.

괄호의 왼쪽이 나오면 스택에 push하고, 괄호의 오른쪽이 나오면 스택에서 pop하는 형태로 해결할 수 있다.

 

---

 

큐(Queue)

- 큐도 마찬가지로 일렬로 된 데이터입니다.

- 다른 자료구조와의 차이점은 입구와 출구가 반대라는 점입니다. 이를 선입선출(First In First Out) 이라고 부릅니다.

 

- 큐의 예시는 선착순 웨이팅입니다.
사람들이 온 순서대로 웨이팅 번호를 받고, 본인의 차례가 오면 번호 순서대로 나가는 방식입니다.

 

- 데이터의 추가는 enqueue라고 불리며, 데이터의 삭제는 dequeue라고 불립니다.

 

ex) A만 들어있는 큐에 B, C를 추가하고, dequeue를 두번 해보자.

1) 큐에 B를 추가한다. (A-B)

2) 큐에 C를 추가한다. (A-B-C)

3) 큐에서 dequeue를 한다. (B-C)

4) 큐에서 dequeue를 한다. (C)

 

예시에서 처럼 가장 먼저 들어간 데이터가 가장 먼저 나오게 되는 구조가 바로 큐이다.

큐가 가장 많이 활용되는 부분은 "너비우선탐색"에서 입니다.