스택과 큐

자료구조 하면서 많이 들어봤다 그죠? 그겁니다. 네.

---

이거 진짜 생각보다 간단하다. 아니 진짜임.

 

쉽게 말하자면 스택은 부페 접시고, 큐는 대기열이다. 회계로 치자면 스택은 후입선출법이고, 큐는 선입선출법이다. 

 

회계에서 물건 들어오고 나간 걸 기장하는 방식 중에 선입선출법, 후입선출법이 있다. 이건 뭐냐면 먼저 산 물건이 먼저 나간걸로 기장하느냐, 나중에 산 물건이 먼저 나간걸로 기장하느냐의 차이. 

 

예를 들어서 내가 어제는 카스테라 100개를 하나당 1000원에 샀고, 오늘은 카스테라 100개를 하나당 900원에 샀다. 그리고 150개를 팔았을 때 선입선출법은 어제 들여온 천원짜리 100개+오늘 들여온 900원짜리 50개가 나가고 후입선출법은 오늘 들여온 카스테라 900원짜리 100개+어제 들여온 카스테라 천원짜리 100개가 나간다. 카스테라를 개당 1200원에 팔았다 치면 18만원이고, 선입선출법일 때는 나간 카스테라에 대한 원가가 10만원+45000원 해서 14만 5천원이지만 후입선출법일 때는 9만원+5만원 해서 14만원이다.

 

부페 접시와 스택

스택은 후입선출법이라고 했는데, 부페 접시를 예로 들어보자.

 

1. 부추엄마(나임) 친구의 결혼식에 가게 된 김부추씨, 결혼식장 부페에는 각종 산해진미가 있었다. 김부추씨는 일단 초밥을 먹기 위해 접시를 들었다. -> 팝

2. 김부추씨와 같이 초밥을 먹기 위해 접시를 들려던 김배추씨, 그 때 직원이 갓 설거지+건조를 마친 따끈따끈한 접시를 들고 와 접시 더미 위에 쌓았다. -> 푸시

 

스택에서 뭘 꺼내가는 건 팝, 스택에 뭘 올리는건 푸시라고 한다. 접시 더미를 예시로 들자면 쌓여있는 접시 더미에서 맨 위에 있는 접시를 꺼내는 건 팝, 접시 더미 위에 접시를 또 올리는 건 푸시.

 

스택에는 크기가 정해져 있는데, 이것도 접시에 비유할 수 있다. 접시를 너무 높게 쌓으면 접시 더미가 무너져서 깨질 수도 있고(접시장창), 만약 사람들이 많은 부페에서 접시가 우르르 꺠진다면 안전상의 문제도 문제지만 사람들이 음식을 먹을 수 없게 된다. 만약 접시 더미가 매우 안정해서 깨지지 않는다고 가정하고 사람 키만큼 쌓는다면, 최홍만이나 야오밍같은 장신이 아닌 이상 접시 더미에서 접시를 꺼낼 수 없다. 그래서 부페에서도 접시 더미를 여러 개 두고, 갓 건조를 마친 따끈따끈한 접시를 쌓을 때도 크기가 제일 작은 접시 더미에 쌓는다. 

여담이지만 스택이 넘치는 것을 스택 오버플로우라고 한다. 예, 그 사이트 맞아요.

 

대기열과 큐

큐는 대기열을 예시로 들 수 있다.

 

1. 교양수업 과제때문에 친구와 함께 전시회에 가기로 한 화강도르마무. 오늘은 주말인데다가 하필 전시회가 또 유명한 화가의 전시회라 대기열이 엄청 길었다. -> 큐

2. 20분정도 기다리고 있으니 조금씩 줄이 줄어들고, 앞에 서 있던 사람들이 들어가는 게 보인다. -> 디큐

3. 화강도르마무와 같이 전시회를 보러 갔던 김양상추씨가 뒤를 보니, 사람들이 김양상추씨의 뒤로 줄을 서고 있었다. -> 인큐

 

수강신청이나 게임 대기열, 은행 대기열(줄을 서지는 않지만 오는 순서대로 번호표를 뽑고번호순으로 처리한다), 콘서트 대기열, 팝업스토어 대기열도 일종의 큐라고 할 수 있다. 내 뒤로 누군가 줄을 서는 것은 인큐, 내 앞에 있던 사람이 들어가는 것은 디큐.