20. 큐와 스택 (FIFO, LIFO)

스택 (stack)

출처: https://tinyurl.com/y4a5wxlt

큐(queue)

출처: http://www.leafcats.com

---

1. 스택 (stack)

나서스 스택 아님.

사전 뜻.

 [명사] 동적이고 순차적인 자료의 목록. 
 [영어] 무더기, 많음 다량, 굴뚝

여러 의미로 사용되는 스택은 자료구조에서는 무언가를 쌓는다라는 의미를 갖는 자료구조.
후입선출(後入先出, Last In First Out; LIFO)의 자료구조.

 

입력은 push, 출력은 pop이다.

peek는 Top의 위치에 있는 데이터를 확인하는 것을 말한다.

쉽게 말해 스택은 일종의 바닥이 막힌 상자라고 보면 된다.

나중에 넣은 물건이 위에 있으므로 먼저 꺼낼 수밖에 없다.

스택은 힙 영역 메모리에서 일반적인 데이터를 저장하는 스택과 

스택 영역 메모리에서 프로그램의 각 분기점에 변수와 같은 정보를 저장하기 위한 스택이라는 두 가지 의미로

사용될 수 있므로 유의해야 한다.

이것도 종류를 나눌 수 있는데,

Ascending stack VS Descending stack
Empty stack VS Full stack

종류가 나뉜다.

Part IA Engineering: Digital Circuits and Information Processing

https://namu.wiki/w/%EC%8A%A4%ED%83%9D(%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0)

 

스택 구현.

배열을 이용해서 구현할 때를 예로 들면.

처음으로 스택을 위한 배열을 하나 잡아 놓고, index 값을 0으로 잡는다. index가 0이면 스택이 비어 있는 것이고,

스택에 뭔가를 집어넣을 때는 index의 자리에 집어넣고 index를 하나 올리면 된다.

index가 초기 배열 크기 이상이면 스택이 꽉 찬 것이다.

스택에서 뭔가를 뺄 때는 index에 있던 값을 돌려주고 index를 하나 뺀다.

---

2. 큐 (Queue)

출처: http://image.auction.co.kr/itemimage/12/70/d9/1270d97ba1.jpg

당구 큐 아님.

 

사전 뜻.

 

대기 행렬, 줄을 서서 기다리다.
꼬리, 끝, 후미

선입선출(先入先出, First In First Out; FIFO)의 자료구조.

대기열이라고도 한다. Queue라는 단어 자체가 표 같은 것을 구매하기 위해 줄서는 것을 의미한다.

데이터가 들어오는 위치는 가장 뒤(Rear 또는 Back이라고 한다)에 있고, 데이터가 나가는 위치는 가장 앞(Front라고 한다)에 있어서, 먼저 들어오는 데이터가 먼저 나가게 된다.

우선순위 큐, 원형 큐 등의 베리에이션이 존재한다. 입력 동작은 Enqueue, 출력 동작은 Dequeue라고 한다.

 

보통의 배열을 사용해서 큐를 구현하면 Enqueue와 Dequeue을 할 때마다 계속 데이터가 앞으로 밀려나는 문제가 생기는데(앞쪽은 채워지고 뒤쪽은 빠져나가므로), 이를 해결하기 위해 원형 버퍼를 사용한다. 시작 부분과 끝 부분을 포인터로 지정한 뒤 Enqueue와 Dequeue를 하는 형태. 대신 가득찰 때와 비어있을 때 포인터가 같은 위치를 지정하기 때문에 이를 해결하기 위해 한 공간을 비워놓는다.

연결 리스트를 사용하면 배열에 비해 매우 쉽게 구현이 가능하다.

STL에는 선형 큐가 이미 알고리즘으로 구현되어 있지만, STL의 알고리즘을 이용해 원형 큐를 구현하는 것은 힘들다.

 

특수 큐.

 

원형 큐

큐를 위해 배열을 지정해 놓고 큐를 쓰다보면 배열의 앞부분이 비게된다는 점을 활용해서 배열의 맨 마지막 부분을 쓰면 다시 제일 처음부터 다시 큐를 채우기 시작하는 형태의 큐이다.

 

데크

일반적인 큐는 뒤에서만 삽입이 이루어지고 앞에서만 인출이 가능한 데 비해,

데크는 양쪽에서 모두 삽입/인출이 가능하다.

 

큐 용도.

 

어떠한 작업/데이터를 순서대로 실행/사용하기 위해 대기시킬 때 사용한다.

서로 다른 쓰레드 사이 또는 프로세스 사이에서나 네트워크를 통해 자료를 주고받을 때 자료를 일시적으로 저장하는 용도로 많이 사용된다.

흔히 자동매칭이 되는 게임(대표적으로 리그 오브 레전드)에서 대기할 때 "큐를 돌린다"고 하는데 그게 바로 이 큐다.

먼저 준비를 마친 쪽이 우선적으로 매칭이 되도록 만드는 시스템이기 때문.

사실 이 경우는 굳이 전문용어로서의 큐가 아니라 단어 자체의 원의 의미인 '줄서기'에 가깝다.

 

https://namu.wiki/w/%ED%81%90(%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0)

큐(자료구조) - 나무위키

 

https://link.coupang.com/a/DOJ55

풀무원 얇은피 꽉찬속 고기만두 (냉동)

https://link.coupang.com/a/DOKe3

COUPANG

"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."