[Chap4] 큐

[큐의 개념]

큐

• 먼저 들어온 데이터가 나가는 자료구조
• FIFO : First in - First out  예) 매표소, 공항 대기열 등 보통 일반적인 경우

큐의 연산

• enqueue(a) : 데이터의 뒤에서 삽입 -> 줄설때 뒤에 가서 서야한다
• dequeue() : 데이터의 앞에서 삭제 -> 일을 해결하는 것은 맨앞부터 진행되야함

선형 큐

• '배열'을 사용하여 큐를 구현하는 것 (뒤에서 데이터를 삽입하고, 앞에서 데이터를 삭제하는 것을 말함)

1. 맨 처음 : front(앞)와 rear(뒤) 모두 -1로 초기화 (-1, 0, 1, 2, 3 ... 이 순서이므로 둘다 +1되어서 뒤로 나가는 것)
2. enqueue(3) : 3을 뒤에 넣으므로 rear은 +1되어서 rear = 0, front = -1
3. enqueue(7) : 7을 뒤에 넣으므로 rear은 +1되어서 rear = 1, front = -1
4. enqueue(5) : 5를 뒤에 넣으므로 rear은 +1되어서 rear = 2, front = -1
5. dequeue() : 지우는 것은 맨앞(인덱스가 0인 곳) 부터 지우니까 front 가 +1되어서 이동한다음 맨앞의 3을 지운다 rear = 2, front = 0
6. dequeue() : 지우는 것은 맨 앞부터 지우니까 front가 +1되어서 이동한다음 맨앞의 7을 지운다 rear =2, front = 1

• 단점 : 배열은 크기가 정해져있고, 데이터가 들어있는 인덱스는 고정되어있다. 그래서 데이터를 계속 삽입하려면 자리가 없으므로, 요소들을 앞으로 계속 이동시켜야한다. 

[원형 큐]

원형 큐

• front, rear은 똑같고, 원형 모양이고 시계방향으로 돌아간다. -> 시계반대 방향으로 해서 봤을 때, 첫번쨰가 제일 먼저들어온것임 (front)

원형 큐의 삽입 & 삭제

• 삽입 : enqueue(int data)
• 삭제 : int data = dequeue() : 삭제하고 싶은 데이터를 data라고 한다면 data를 dequeue에 저장해놓는 것인가 ..?
• 원형에는 -1이 없기 때문에, rear과 front 모두 0으로 초기화된다
• *그리고 front가 +1되는 경우는 데이터를 지우는 경우 뿐이다. 그래서 front에는 항상 데이터가 없이 비워져있다
• 인덱스가 0~7까지 있을 때, 만약 ) [7]다음에 데이터를 넣으면 +1하게 되면 [8]이 된다. 
  • %8(나누기 8해서 나머지)를 사용한다. 왜냐면 이렇게 하면 0~7까지의 값만 나오게 되니까
  • 8은 사이즈를 말하는 것이다
• 삽입 enqueue(x) : 
  • rear = (rear + 1) % 사이즈 -> 만약 rear이 7이라면 rear = (7+1)%8 = 0이 나온다. 그래서 0에 데이터 넣으면 됨
  • data[rear] = x : data[0]에 x가 들어가게 된다
• 삭제 dequeue() : 
  • front = (front+1) % 사이즈 -> 만약 front가 3이라면 front = (3+1)%8 = 4가 된다. 그래서 인덱스4를 지우면됨
  • return data[front] : data[4]의 값을 리턴한다. 위에 보면 int data = data[4]가 되는 것
  • 궁금점... 값을 가져오면 삭제가 되는건가......?

공백 &포화 상태

• 포화 상태 : front % 사이즈 == (rear+1) % 사이즈 : front자리 하나빼고 데이터가 다 차있다는 뜻 !
  • 근데, 원래 포화와 공백 구별하기 위해서 front하나는 비워둬야한다.
  • 왜냐면 데이터가 다 차있으면 front = rear = 0이므로 , 공백과 똑같다고 볼 수 도 있다
  • 따라서 front == rear 이면서 데이터가 다 차있으면 오류이다 !
• 공백 : front == rear

[덱] 

덱

덱 연산

덱 구현

덱 연산

dequeue 클래스