[ 자료구조 ] 큐 복습 ( Queue )

큐

큐의 정의 : 선입선출 (  First In First Out : FIFO ) 의 자료구조.

큐는 놀이동산을 생각하면 편하다. 놀이동산에서 먼저 줄선 사람이 먼저 놀이기구를 타게되듯 한줄로 서있고 중간에 새치기 같은게 불가능하다고 생각하면 된다. 

먼저 들어온 자료 등이 먼저 처리되는 자료구조다.

기능 : 삽입 ( 입력 ) ENQUEUE / 출력 ( 삭제 ) DEQUEUE / 참조 FRONT , REAR( = BACK )

키워드 : ENQUEUE ( 인큐 ), DEQUEUE ( 디큐 ), FRONT, REAR, BACK

ENQUEUE : 큐에서의 삽입 ( 가장 뒤에 줄을 서는 것 )

DEQUEUE : 큐에서의 삭제 ( 맨 앞에 줄 서있던 사람이 나가는 것 )

FRONT : 맨 앞을 참조 

BACK, REAR : 맨 뒤를 참조

구현 : 배열 / 링크드 리스트

배열 : 배열을 스택처럼 쭉 늘여놓고 사용했을 땐 여러 문제가 있을 수 있다. 

FRONT 는 앞으로만 나아가고 REAR ( = BACK ) 은 그걸 점점 따라잡는데,

FRONT 가 배열의 끝까지 도달하면, 그다음은....??

이런 문제를 해결하기 위해 만들어 진것이 원형으로 구현하는 것이다.

배열의 끝이 다시 처음과 연결 되도록 구현 하는 것인데

이런 식이라고 생각하면 되겠다 ( 개념적으로 그렇단 거지 실제로 저렇진 않다! )

어떻게 하면 될까 하면 바로 % 연산이 있다 Modulo 연산 !

배열크기가 10 이고 FRONT 가 계속 증가한다 했을 때, FRONT ++ 에다가
%10 을 걸어놓는다면?

0,1,2,3 .... 7,8,9,0,1,..... 을 반복하게 될것이다. 즉 배열 안을 뱅글뱅글 돈다는 뜻

다만 아직 사용 되지않은 기존의 자료를 덮어 씌워 버릴 수도 있으므로 주의해야 할 것이다

※ 밑의 예제 코드는 이 부분은 구현하지 않았다. 덮어 씌우는 것에대한 처리는...알아서 해보길 누가 할진 모르겠지만

예제코드 - 배열 -

#include <iostream>
#include < string >
using namespace std;
int enqueue(int p);
int dequeue();
int queue[1000];
int front = 0;
int rear = 0; 
int main() {
	int end = 1;
	int select;
	int p;
	string choice;
	while (end) {
		cout << "enqueue n\ndequeue \nend" << endl;
		cin >> choice;
		if (choice == "enqueue" || choice == "ENQUEUE") {
			cin >> p;
			if (enqueue(p))
				cout << p << " enqueue 성공 " << endl;
			else
				cout << " enqueue 실패 " << endl;
		}
		else if (choice == "dequeue" || choice == "DEQUEUE") {
			if (front != rear)
				cout << "dequeue 결과 : " << dequeue() << endl;
			else
				cout << "불가능하다 이 짜식아" << endl;
		}
		else
			end = 0;
		choice.clear();
	}
}
int enqueue(int p) {
	queue[rear++] = p;
	rear %= 1000;
	return 1;
}
int dequeue() {
	int ret = queue[front++];
	front %= 1000;
	return ret;
}

링크드 리스트 구현

링크드 리스트로 구현하려면, 싱글로 가능 할까 ? 가능 할수도 안할수도 있습니

가능하지만 하지않는다 ! 왜냐하면 FRONT 에서 DEQUEUE 로 나가고 나면 이제 2등이 1등이 되어야 하는데

2등의 주소를 알고있는건 싱글 링크드 리스트에선 3등이기에 맨 마지막에서부터 다 찾아 올라와야한다.

이 얼마나 비효율적이란 말인가 대한민국처럼 

어쨋든 그래서 더블 링크드 리스트로 구현을 하는 것이 일반적이다.

스택에서 삭제의 연산이 다른 곳에서 일어나고, 더블링크드 리스트 라는 차이를 보인다.

코드는 시간이 빡빡해서 안 못짰다