06-01 배열 기반 큐(순환 큐)

 

아래의 상기 내용은

"이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.

 

1.큐(Queue)

 1)정의

  -데이터가 마지막에 들어간 데이터가 제일 나중에 나오는 후입선출(Last in -Last out)의 형태를

 띤  선형 자료구조.

 -큐의 가장 앞 요소를 전단(front) 가장 마지막 요소를 후단(Rear)이라고 한다.

  -큐은 중요 연산은 삽입(Enqueue)와 제거(Dequeue) 연산 두 가지.

 

 

 

 

 2.순환 큐(Circular Queue)

  1)개요

  -배열을 이용해서 큐를 구현하다면 아래의 그림과 요소를 제거하는 상황에서 요소를 다음 칸으로

  옮겨 전단을 옮겨야한다. 그러면 이동하는데 상당한 연산이 든다.

 -이 문제를 해결하기 위해서 전단과 후단을을 가리키는 변수를 도입해 요소를 위치를 옮기지 않고 변수의 데이터만  바꾸는 방법이 있다.

-그런데 이러한 방식에는 다른 문제가 발생하는데 연산을 수행하면서 가용용량이 부족해진다는 것.

-용량을 문제를 해결하기 위해 처음과 끝을 연결하는 방식을 추가하였다.

-큐의 최대용량보다 현재 용량이 적으면 추가되는 후단의 위치를 앞으로 보냄으로써 문제가 해결된다.

 

-시작과 끝을 연결해서 효율적은 삽입/삭제 연산이 가능하도록 구현 큐가 순환 큐이다.

2)공백상태와 포화상태

 -큐내의 요소가 비었을때 공백상태, 가득차 있을 때 포화상태라 한다.

 -아래의 그림을 보면 공백상태와 포화상태일 때 전단과 후단이 같다.  

 

-공백상태일 때와 포화상태일 때의 구분을 위해 더미 노드를 둔다.

2.순환 큐의 데이터 노드 및 스택 구현

1)데이터 노드 구현

 

 

2)배열 기반 스택의 연산 및 함수원형 선언

 

3)함수 구현

 -큐 생성 및 삭제 연산

 

 -큐 삽입 연산

 

 -큐 제거 연산

 

 

-공백 및 포화 상태 판단 연산

-큐 요소 개수를 반환 연산

-실습