스택/큐/덱

안녕하세용

드디어 hash를 끝냈습니다람쥐

오늘은 스택/큐입니동동동

 

스택 Stack

 

 

 

Stack은 쌓아올린다는 뜻입니다.

스택 자료구조는 데이터를 차곡 차곡 쌓어올린 형태의 자료구조입니다.

 

스택 특징

 

스택은 같은 구조와 크기의 자료를 정해진 방향으로 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있습니다.

top에는 가장 위에 있는 자료는 가장 최근 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 됩니다.

스택에서 자료를 삭제할 때도 top을 통해서만 가능합니다.

스택에서 top을 통해 삽입하는 연산을 "push", top을 통한 삭제를 하는 연산을 "pop"이라고 합니다.

 

따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가집니다.

 

이러한 스택의 구조를 후입선출(LIFO, Last In First Out) 구조 라고 합니다.

 

그리고 비어있는 스택에서 원소를 추출하려고 할 때 stack underflow 라고 하며, 스택이 넘치는 경우 stack overflow 라고 합니다. 

(유명한 사이트 stack overflow 의 이름이 여기서 유래되었다고... )

 

시간 복잡도

 

top의 위치의 데이터에 바로 접근이 가능하기 때문에 데이터 삽입, 삭제의 시간 복잡도는 O(1)입니다.

 

장단점

• top을 통해서 접근하기 때문에 데이터 접근, 삽입, 삭제가 빠릅니다.
• top 위치 이외의 데이터에 접근할 수 없기 때문에 탐색이 불가능합니다. 탐색하려면 모든 데이터를 꺼내면서 진행해야합니다. 

 

스택 활용예시

스택의 특징인 후입선출(LIFO)를 활용하여 여러 분야에서 활용 가능합니다.

• 웹 브라우저 방문기록(뒤로가기): 가장 나중에 열린 페이지 부터 다시 보여준다.
• 역순 문자열 만들기(뒤로가기): 가장 나중에 열린 페이지 부터 다시 보여준다.
• 실행 취소(undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
• 후위 표기법 계산
• 수식의 괄호 검사(연산자 우선 순위 표현을 위한 괄호검사)

 

큐 Queue

 

큐의 사전적 의미는 (무엇을 기다리는 사람, 자동차 등의) 줄, 혹은 줄을 서서 기다리는 것을 의미합니다.

따라서 일상생활에서 놀이동산에서 줄을 서서 기다리는 것, 은행에서 먼저 온 사람의 업무를 창구에서 처리하는 것과 같이 선입선출(FIFO, First In First Out) 방식의 자료구조를 말합니다.

 

선형 큐 Linear Queue

선형 배열을 사용하여 구현된 큐로 삽입을 위해서는 계속 요소들을 이동 시켜야합니다. 이 때 요소들이란 데이터 각각이 아니라, front와 rear 입니다. 그런데 rear 요소를 이용해서 삽입이 일어나기 때문에, front 앞쪽에 공간이 있더라도, 삽입할 수 없는 경우가 발생할 수 있습니다. 

 

원형 큐 Circular Queue

선형 큐의 단점을 보완하였습니다.

• front = 맨 첫번째 요소 바로 앞을 가리킴
• rear = 마지막 요소를 가리킴
• empty 상태 : front == rear
• full : front == (rear + 1) % MAX_QUEUE_SIZE
• 공백 상태와 포화 상태를 구분하기 위해 하나의 공간을 비워둠

 

시간 복잡도

큐 역시 front, rear 의 위치로 데이터 삽입 삭제가 바로 이루어지기 때문에 원소 삽입, 삭제의 시간 복잡도는 O(1)이다.

 

장 단점

• 데이터의 삽입, 삭제가 빠르다.
• 큐 역시 스택과 마찬가지로 중간에 위치한 데이터에 대한 접근이 불가능하다.

 

큐의 특징

 

정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과 달리

큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.

이때 삭제 연산만 수행되는 곳을(front), 삽입 연산만 이루어지는 곳을(rear)로 정하여 각각의 연산작업만 수행됩니다.

이때, 큐의 rear에서 이루어지는 삽입 연산을 인큐(enQueue), 프론트에서 이루어지는 삭제연산을 디큐(deQueue) 라고 부릅니다.

 

• 큐의 가장 첫 원소를 front/ 가장 끝 원소를 rear
• 큐는 들어올 때 rear로 들어오지만 나올 때는 front로 부터 빠지는 특성
• 접근 방법은 가장 첫 원소와 끝 원소로만 가능
• 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제

즉 큐에서 프론트 원소는 가장 첫번째 원소가 되는 것이며, 리어 원소는 가장 늦게 들어온 마지막 원소가되는 것입니다.

 

큐의 활용 예시

 

큐는 주로 데이터가 입력된 시간 순서대로 처리해야할 필요가 있는 상황에 이용합니다.

• 우선 순위가 같은 작업 예약(프린터의 인쇄 대기열)
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스관리
• 너비 우선 탐색 구현
• 캐시 구현

 

덱 Deque

 

Deque 은 Double -Ended Queue 의 줄임말입니다.

한쪽에서만 삽입, 다른 쪽에서만 삭제가 가능했던 queue와 달리 양쪽 front, rear에서 삽입 삭제가 모두 가능한 큐를 의미하는 자료구조입니다.

 

 

연속적인 메모리를 기반으로 하는 시퀀스 컨테이너이고 선언 이후 크기를 줄이거나 늘릴 수 있는 가변적 크기를 갖습니다.

 

또한 중간에 데이터가 삽입될 때 다른 요소들을 앞 뒤로 밀수 있습니다.

 

시간 복잡도

삽입 삭제 연산은 마찬가지로 O(1)의 시간 복잡도를 가지고, 스택/큐와 달리 index를 통해 요소들에 탐색이 가능하므로 이 역시 O(1)의 시간 복잡도를 가집니다.

 

장단점

• 데이터의 삽입 삭제가 빠르고 앞, 뒤에서 삽입 삭제가 모두 가능
• 가변적 크기
• index를 통해 임의의 원소에 바로 접근이 가능
• 새로운 원소 삽입 시, 메모리를 재할당하고 복사하지 않고 새로운 단위의 메모리 블록을 할당하여 삽입
• 중간에서의 삽입 삭제가 어려움
• 스택,큐에 비해 구현이 어려움

 

Deque(덱)은 Vector(벡터) 보다 좋은 성능을 가집니다. 메모리 추가 할당이 더 저렴하기 때문인데요, vector는 데이터를 저장하는 버퍼를 1차원 배열 형태로 관리하기 때문에 vector는 메모리를 추가로 할당할 경우 기존 메모리 영역의 2배 만큼 메모리를 추가로 할당하고 기존의 요소를 복사합니다.

 

Dequeu은 chunk를 이용해 관리합니다. chunk는 메모리 영역 군데 군데 흩어져있고 컨테이너에서 내부적으로 chunk에 바로 접근이 가능하로독 인터페이스를 제공합니다. 때문에 처음에 할당 받은 chunk를 모두 사용했다면 deque는 새로운 chunk를 만드는 것만으로 메모리 추가할당이 완료됩니다.

 

* 다음의 글을 보고 작성하였습니다.

https://velog.io/@nnnyeong/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9D-Stack-%ED%81%90-Queue-%EB%8D%B1-Deque

https://devuna.tistory.com/22