[자료구조] 추상 자료형(스택 & 큐)

추상 자료형에 대한 설명은 여기 ← 클릭!!!

 

대표적인 추상 자료형, 스택(Stack)과 큐(Queue)

우리의 상상 속에만 존재하는 대표적인 자료구조 두 가지로는 스택과 큐가 있다!

왜 상상 속에만 존재할까? 스택과 큐는 실제로 프로그래밍 언어들에서 존재하지 않는다.

쉽게 말해 스택과 큐는 일종의 '규칙'이라고 할 수 있다.

 

https://techdifferences.com/difference-between-stack-and-queue

자료구조가 스택 혹은 큐로 구분되기 위한 규칙! 이걸 추상 자료형(ADT)이라고 한다.

ADT는 자료구조의 한 형태인데 자료구조의 방법이 코드로 정의된 것이 아니라, 그 구조의 행동 양식만 정의된 것을 말한다.

 

스택(Stack)

https://luv-n-interest.tistory.com/161

스택(Stack : 쌓다)은 그림에서 사과를 쌓을 때 위로 쌓는 것만 가능하듯이 한 방향으로만 입력할 수 있으며 구조 중간에 값을 끼워 넣어 저장할 수 없다. 즉, 같은 크기의 자료를 정해진 한 방향으로만 입력, 저장, 삭제가 가능하다.

 

맨 아래 있는 사과를 꺼내기 위해서 가장 위에 있는 사과부터 꺼내야 하는 것처럼 후입선출(Last In First Out, LIFO) 구조로 가장 마지막에 들어온 데이터(사과)가 가장 먼저 리턴, 삭제된다는 뜻이다.

 

📌 스택의 활용 예시

🔙 브라우저의 뒤로가기

웹 브라우저의 뒤로 가기를 누르면 '스택' 자료구조를 사용하는 것이다.

 

왜냐! 뒤로가기를 누르면 웹페이지 히스토리 스택의 맨 위에서 한 페이지를 가져가는 것이기 때문이다.

 

⏰ 실행 취소(Ctrl + Z)

내 앱에서 되돌리기를 실행하려면 유저가 하고 있는 행동들을 스택에 차곡차곡 쌓다가 되돌리기를 누르는 순간 스택으로 가서 과거를 되돌릴 수 있는 것이다.

 

큐(Queue)

https://luv-n-interest.tistory.com/161

큐(Queue : 대기줄)는 맛집에 사람들이 웨이팅을 하는 줄과 같이 양 방향에서 입력과 출력이 진행되는 자료구조를 뜻한다.

 

먼저 온 사람이 먼저 맛집의 음식을 먹고 나가는 것처럼 선입선출(First In First Out, FIFO) 구조로 가장 먼저 들어온 데이터가 가장 먼저 리턴, 출력된다는 뜻이다.

 

📌 큐의 활용 예시

📞 콜센터의 상담사

Suck Study - Seok(바쁜 콜센터 직원)

전화 온 순서대로 상담을 처리하는 콜센터의 백엔드도 큐의 일종이다.

 

💸 쇼핑몰에서 주문을 처리하는 방식

우리가 주문을 하면 쇼핑몰에서 주문이 온 순서대로 처리하는 방식도 큐의 일종이다.

 

References

📺 https://www.youtube.com/watch?v=Nk_dGScimz8

📄 https://ontheway.tistory.com/23

📄 https://luv-n-interest.tistory.com/161