[자료구조] 스택(STACK)과 큐(QUEUE)

Stack and Queue

1. 스택 Stack

이름에서 알 수 있듯 아래에서 위로 쌓아 올리는 구조.

Tower of Hanoi

💡 하노이탑에서 가장 맨 밑의 원반을 위의 원반보다 먼저 빼내지 못함 -> 후입선출(LIFO)

💡 비슷하게 스택에서는 삽입, 삭제가 한쪽 끝(맨 위)에서만 일어남 -> top이라는 포인터 존재

💡 삽입(PUSH): top이 가리키는 자리 위에(top = top + 1) 메모리 생성, 데이터 삽입

💡 삭제(POP): 스택의 가장 윗 데이터(top) 삭제. 스택이 비었다면 연산 정의불가

🔧 스택 언더플로우: 비어있는데 꺼내려 할 때 <-> 스택 오버플로우: 꽉 찼는데 새로 넣으려 할 때 오류 발생

 

그 유명한 개발자 커뮤니티  StackOverflow의 이름이 여기서 나왔다 ㅎㅎ

 

❓스택은 어디에 쓸까? -> LIFO 특성 이용

• 웹 페이지 방문 기록: 뒤로가기를 누르면 가장 마지막에 열린 페이지부터 보여줌
• 실행취소(UNDO): 가장 마지막 처리된 작업부터 지움
• 수식 괄호 검사: 올바르게 쓰인 괄호는 항상 대칭, 가장 마지막에 쓰인 괄호부터 닫아 나가야 함

---

2. 큐 Queue

Queue는 이름 그 자체로 대기열이라는 뜻을 갖고 있다.

게임을 할 때 함께 플레이할 유저들을 기다리는 것을 흔히 큐를 잡는다, 큐를 돌린다고 표현한다.

협곡 입장 대기 중인 유저들

내가 5분 전부터 기다렸는데,

방금 전에 큐 돌리기 시작한 사람이 나보다 먼저 게임을 시작한다면 열 받지 않겠는가?

 

그래서 게임 대기열은 선입선출(FIFO), 즉 먼저 온 사람이 먼저 나갈 수 있는 구조를 취하고 있다.

이런 특징을 갖는 자료구조가 바로 Queue다.

 

💡 삽입, 삭제가 양 방향에서 각각 이루어짐(rear, front 포인터), 선입선출(FIFO)

💡 삽입(ENQUEUE):

rear에 데이터 삽입

💡 삭제(DEQUEUE): front에서 데이터 삭제

 

만약 rear, front 쓰지 않고 일반 배열(Array)로 구현

-> Enqueue와 Dequeue를 할 때마다 계속 데이터가 앞으로 밀려나는 문제 발생 (앞쪽은 채워지고 뒤쪽은 빠져나가므로)

=> 원형 버퍼를 사용!

: 시작 부분과 끝 부분을 포인터로 지정한 뒤 Enqueue와 Dequeue.

❗ 가득찰 때와 비어있을 때 두 포인터가 같은 위치를 가리키기 때문에 이를 해결하기 위해 한 공간을 비워놓는다.

 

❓큐는 어디에 쓸까? -> FIFO 특성 이용

• 프린터의 인쇄 대기열 -> 먼저 명령한 놈부터 출력
• 은행 / 콜센터 업무 처리 -> 먼저 온 사람부터 대응
• 프로세스 관리 -> 방법에 따라 다르지만... 자세한 내용은 OS에서 다룬다.

---

참고

1. https://devuna.tistory.com/22

[자료구조] 스택 (STACK), 큐(QUEUE) 개념/비교 /활용 예시

2. https://url.kr/buqd2u 

[개념 콕] 스택과 큐 - 내일배움캠프 블로그

3. https://url.kr/sixjbc

스택 - 위키백과, 우리 모두의 백과사전