Queue 큐_이중연결리스트 구현

Queue 큐

큐는 스택과 다르게 앞뒤가가 뚫린 긴통이라고 보면 된다. 즉 입구와 출구가 다르다.

뒤에서 넣고 앞에서 꺼낸다. 그래서 먼저 들어간 것이 제일 먼저 나오는 FIFO구조이다.

큐를 조작하는 방법에는 put동작과 get동작이 있다.

put  : 뒤에서 넣음

get  :  앞에서 꺼냄

사진 : 위키백과

 

큐 구현방법에는 배열구현과 연결리스트 구현이 있다. 

큐노드 클래스

큐 초기화(이중연결 리스트)

Put

K의 값은 가지는 노드를 만들어 꼬리의 앞에 삽입한다. 

Get

큐가 비었는지 확인하고(머리노드 다음이 꼬리이면 꺼낼 노드가 없다)

C++같은 메모리 직접 관리가 가능한 언어는 당연히 메모리를 삭제했으니 메모리해제과정이 필요하다.

출력

확인

맨처음 put한 데이터가 맨 위에있다.

Get테스트