<자료구조> 스택과 큐(2)

 

1. 큐란

* 큐

 - 스택과 같이 데이터를 임시 저장하는 자료구조이지만 가장 먼저 넣은 데이터를 가장 먼저 꺼낸다는 차이가 있다. (선입선출구조)

 - 인큐(enqueue) : 큐에 데이터를 추가하는 행위

 - 디큐(dequeue) : 큐에서 데이터를 꺼내는 행위

 - 프론트(front) : 데이터가 빠지는 가장 앞쪽 부분

 - 리어(rear) : 데이터를 넣는 부분

 

2. 배열과 큐

- 인큐 : 맨 끝 데이터의 다음 인덱스에 원소를 저장하여 처리의 복잡도는 O(1)이고 cost가 적다.

- 디큐 : que[0]에 저장된 원소를 꺼내면서 이후의 원소를 모두 앞쪽으로 옮겨야한다. 따라서 복잡도는 O(n)이고 매우 비효율적이다.

 

   ※ 우선순위 큐 : 인큐할 때 데이터에 우선순위를 부여하고 디큐할 때 우선순위대로 꺼내는 자료구조

 

3. 링 버퍼와 큐

* 링 버퍼

 - 배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조

 - 프론트와 리어는 논리적인 데이터 순서일 뿐 배열의 물리적 원소의 순서와는 관련이 없다.

 

 

 - 인큐와 디큐를 수행할 때마다 front와 rear의 값이 변한다. 이 때 처리 복잡도는 O(1)이다.

 

4. 함수의 구현

 - 큐를 링 버퍼의 방식의 함수로 만들기 위해서는 스택에서 그랬던 것처럼 다양한 클래스와 함수가 필요하지만 큐에서만 특별한 경우들에 대해서만 알아보자.

* 인큐

 - 인큐함수를 구현할 때 큐가 가득차 있으면 예외처리를 발생시켜야 한다.

 - 인큐 후 rear에 1을 증가시켜야하는데 이 때 rear값이 큐의 크기인 capacity와 같은 경우 rear을 배열의 0인덱스로 돌려야 한다.

 

 

* 디큐

 - 디큐함수는 큐의 가장 앞을 반환하되, 큐가 비어있으면 예외 처리를 해야한다.

 - 디큐 후 front의 값은 1 증가시켜야하는데 이 때 front가 배열의 끝이면 front는 배열의 0 인덱스로 돌려야한다.

 

 

* 검색

 - 큐의 배열에서 특정 값이 있는지, 있다면 어디에 있는지 검색할 때는 front부터 rear까지 선형검색을 해야한다.

 - 이 때 인덱스를 구하는 식은 (i+front)%capacity 이다.

 

 - 검색에 성공하면 index를 반환한다.

 

  ※ 덱 : 양방향 대기열로써 맨 앞과 맨 끝 양쪽에서 데이터를 넣고 꺼낼 수 있는 자료구조이다. 2개의 포인터를 사용하므로 큐와 스택을 합친 형태라고도 볼 수 있다.

 

 

 

 

 

 

 

---

 

 

참고

 

 

이 글은 ‘이지스퍼블리싱’의 ‘자료구조와 함께 배우는 알고리즘 입문’을 공부 후 정리하며 쓴 글입니다.

작성된 모든 내용과 코드는 교재 및 관련 사이트를 참고하여 직접 재구성하였습니다.

 

 

Do it! 자료구조와 함께 배우는 알고리즘 입문 - 파이썬 편

http://www.easyspub.co.kr/20_Menu/BookView/381/PUB

 

이지스퍼블리싱 스터디룸 카페

Do it! 스터디룸 : 네이버 카페

 

교재 공식 깃허브

easysIT/doit_dsalgo_with_python