<5> 큐(Queue)

이 글은 시험이 19시간정도 남은 사람이 내용 정리를 위해 적는 글입니다.
*[C언어로 쉽게 풀어쓴 자료구조]  책과 숙영리 교수님의 강의를 참고하여 작성하였음을 밝힙니다.

이걸로 계속 가겠음.🪸😎

 

 

🪸 특징

: 선입선출(FIFO)  - 들어오는 문과 나가는 문이 다름. 

 

- enqueue : 큐의 끝(rear)에 요소를 추가함.

- dequeue : 큐의 앞(front)에서 요소를 제하고 반환함.

* peek() : 큐의 앞에서 요소를 읽어 반환함 (제거하지 않음)

 

 

🪸 선형큐

: 배열을 선형으로 사용하여 큐를 구현한 것

 

*front : 가장 최근에 제거된 data가 저장됐던 위치

*rear : 가장 최근에 들어온 data의 위치

 

(e) 그림에 값 5가 지워졌서요

 

* 초기 상태의 front , rear의 값은 -1

* 공백 상태의 경우 front == rear ; 가장 최근에 들어온 요소가 제거됐다는 의미

 

✨ 문제점: front에서 요소들이 삭제되어 여유공간이 있어도 파악 불가 (full을 판단할 때 rear만 가지고 판단하기 때문)

==> 원형큐로 해결 가능!

rear이 큐의 끝에 있는지 확인

 

-enqueue

rear 값 증가한 뒤에 item 넣기

- dequeue 

front 값을 증가하고 item 빼기

*스택이랑 헷갈리지 말자! 스택에서 pop하는 경우에는, 요소를 먼저 빼고 top 변수를 1감소했음.

 

 

---

🪸 원형큐 

 

- front : 첫번째 요소 하나 앞의 인덱스

- rear :  마지막 요소의 인덱스 

(둘 다 시계방향으로 돎)

 

 

* 초기 상태의 front, rear 값은 0, 저장은 1부터! --> 공백상태와 포화상태의 구분을 위해서 하나의 공간을 비움!

* 공백 상태 : front == rear (선형큐랑 동일)

 

✨포화 상태 : front % M == (rear +1) % M 

--> index의 값이 7 다음에 0으로 가야하니까 modulo 연산을사용함!  

front = rear + 1 % M

 

-enqueue

rear을 reat+1 % M 으로

 

-dequeue

front를 front+1 % M

*스택이랑 헷갈리지 말자! 스택에서 pop하는 경우에는, 요소를 먼저 빼고 top 변수를 1감소했음.

 

 

 

---

🪸 큐의 응용 : 버퍼

: 서로 다른 속도로 실행되는 두 프로세스 간의 상호작용 조화

 

 

😎 큐에 일정한 비율로 난수를 생성해 입력 (20%) 하고, 일정한 비율로 출력(10%) 하는 프로그램

 

=> enqueue가 실행될 확률이 더 높기 때문에 큐가 growing!

 

---

 

🪸 덱 (deque)

: 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐

 

😎연산 ***

1) 스택과 동일한 연산 : add_front() , delete_front()

 

2) 큐와 동일한 연산 : delete_front() , add_rear()

 

3) 덱만의 연산 : delete_rear() , 조금 다른 add_front()

 

 

-배열을 이용한 덱의 구현

: front<- (front -1 + M) % M

: rear <- (rear -1 + M) % M

* -1을 했을 때 음수가 되면 안되기 때문에 M을 더해줘야 함.

 

 

-큐와 동일한 공백/포화 검출 함수

 

✨ add_rear(후단 삽입)과 delete_front(전단 삽입)의  경우에도 큐와 코드가 동일함.

q->rear = (q->rear+1) % M; 다음에 삽입

q->front = (q->front+1) % M; 다음에 삭제

 

 

✨큐와 다른 add_front() 와 delete_rear

 

-add_front()

 

-delete_rear()

 

🥲아 진짜.. 헷갈려요,,,,,,,,,,,,,,,,,,,,ㅠ  긍까 원형 큐의 경우에는 전단(rear)에서만 삽입이 일어나고, 후단(front)에서만 삭제가 일어나죠.. 원형큐의 경우에는 M다음에 0으로 가야하니까.응응.. 삽입할 때는 rear +1 하면 되는데, 그러면 M 다음에 M+1로 가잖아 그러니까 rear +1 % M 해준다. 오키 삭제할 때도 마찬가지임. front +1 한담에 삭제하면 되는데 동일한 이유로 front +1 % M해줘야 함. 

자 덱의 경우에도 전단rear 삽입과 후단front 삭제의 경우에는 위와 동일하게 진행되지만, 특이한 점 전단rear 삭제와 후단front 삽입이 가능하다는것. 이 경우에는? rear랑 front 값을 빼줘야 하는 거잖아요? 그러니까 위에처럼 계산하면 안됨 왜냐면 이제 문제가 되는 거는 index 0에서 -1 했을 때 M이 돼야 하는데 음수값이 되는 것. -> 그래서 삽입의 경우 front -1 + M 한 거를 %M , 삭제의 경우 rear -1 + M % M 이런 식으로 해줘야 돼!!!!!!오키 이해했음