2021년 8월 20일 - Stack & Que

● 본 공부와 기록은 유튜버 '노마드 코더 Nomad Coders' 님의 "어? 재밌네? 정렬 알고리즘, 한방에 이해하기!"을 기본으로 하였다.

→ https://www.youtube.com/watch?v=Nk_dGScimz8&lc=z23zjhqxmozxstx0eacdp431rnmtvmda4dybmf2m1p1w03c010c 

 

 

---

 

☆ Abstract Data Type - APT

• Stack
• Que

 

→ ADT는 실제로 존재하지 않고 추상적인 개념으로만 존재한다.

→ 실제로 프로그램 언어들에서는 존재하지 않는 일종의 '규칙'이다.

→ 데이터 구조가 스택 혹은 큐로 구분되기 위한 규칙들이라고 볼 수 있다.

→ 자료구조의 방법이 코드로 정의된 것이 아니라, 구조의 행동 양식만 정의된 것을 의미한다.

→ 즉, 규칙만 이해하면 직접 '스택'이나 '큐'의 자료구조를 만들 수 있다.

 

→ Stack과 Que는 단순히 배열(Arrays) 위의 어떤 규칙들을 설정한 모습들이다.

 

---

 

★ Satck

 

 

→ 팬케이크를 쌓는 걸 상상했을 때, 가장 먼저 쌓은 것이 아래로 간다.

→ 또한 팬케이크를 제거하거나 꺼낼 때도 맨 위 것을 먼저 먹거나 치워버린다.

 

 

→ '스택'은 배열이 수직으로 쌓여있는 것이다.

→ 이 배열에서는 요소를 추가하거나 삭제할 때, 맨 위에서부터 차례대로 할 수 있다.

→ 이런 방식을 LiFo(Last in First out) 이라고 한다.

→ 마지막으로 쌓아올린 팬케이크가 가장 먼저 나간다는 뜻이다.

 

---

 

☆ Que

 

 

→ 버스를 타기 위해 사람들이 줄 서 있다고 생각해보자.

→ 먼저 온 사람이 먼저 버스를 타고, 늦게 온 사람이 늦게 버스에 탑승한다.

 

 

 

→ '큐'는 배열인데, 가장 먼저 '큐'에 입장한 요소가 가장 먼저 '큐'에서 나가는 요소가 된다.

→ 새로운 요소는 큐 맨 뒤로 추가되고, 큐의 맨 앞에 있는 요소만 읽거나 삭제할 수 있다.

→ 이런 구조를 FiFo(First in First out) 이라고 한다.

 

---

 

★ 정리

 

◎ 스택 : 새로운 요소는 스택 위에 차곡차곡 쌓이며, 스택의 맨 위 요소에서만 요소를 읽거나 삭제할 수 있다.

◎ 큐 : 버스에서 줄을 서는 것처럼, 새로운 요소는 큐의 맨 뒤로 추가되고, 큐의 맨 앞에 있는 요소만 읽거나 삭제할 수 있다.

 

→ 이것들은 '추상적' 자료 구조라서 규칙들만 잘 이해하면 진짜 자료구조들에 바로 적용해볼 수 있다.

 

---

 

★ 언제 사용할까?

 

◎ 스택

• 웹 브라우저에서 뒤로가기 - 웹 페이지 히스토리 스택 맨 위에서 한 페이지를 가져가는 것 
• Ctrl Z
• 되돌리기를 누르는 순간, '스택'으로 가서 쌓여있는 걸 하나씩 제거함으로써 과거를 돌릴 수 있는 것이다.

 

◎ 큐

• 이메일 전달
• 푸쉬 알림
• 쇼핑몰에서 선착순으로 주문을 처리하는 방식
• 전화 온 순서대로 상담을 처리하는 콜센터 백엔드