본문 바로가기

(탈퇴) 테슬라's Post

동적인 단일 연결 리스트 (Singly Linked List) - 큐

안녕하세요~ 오늘도 찾아온 테슬라입니다.
오늘은 큐에 대해서 할 텐데요. 저번에 올린 스택과 비슷한 수준입니다.

우선 큐에 대해 알아볼까요?
큐는 한쪽 끝에서 데이터가 삽입되고, 삭제는 반대쪽에서만 할 수 있도록 되어있는 순서리스트의 자료구조인데요.
입력과 삭제가 반대이기 때문에, 먼저 삽입된 것이 먼저 삭제되겠지요?
예를 들어 자판기에서 종이컵을 넣을 때 먼저 넣은 종이컵이 사용할때도 먼저 나오지요?
그런식으로 삽입과 삭제가 반대 방향으로 이루어 진 것을 큐라고 합니다.
때문에 큐는 선입 선출(FIFO : First In First Out)리스트 라고도 하지요.


그렇다면 이러한 큐는 어떤식으로 나타날까요?
음 아래의 그림을 보시죠...
사용자 삽입 이미지

위쪽이 연결리스트로 구현한 enqueue(큐 삽입) 밑의 그림이 개념적인 enqueue(큐 삽입)의 모습입니다.
front는 삭제될 부분, rear부분은 삽입되는 부분입니다.
연결리스트로 구현시 새로운 노드의 생성은 제일 마지막 부분에 합니다.
나중에 들어간 값이 마지막에 나오기 때문이죠

그렇다면 삭제는 어떻게 할까요? 아래의 그림을 보시죠
사용자 삽입 이미지
이것이 dequeue(큐 삭제)입니다. 음 어디서 많이 본 거 같지 않나요?
네...  저번에 보았던 스택과 같습니다.
삽입이 스택과 반대쪽이므로 삭제는 같은 것이지요.
다음 코드를 가리키고 free()해주는것이지요
 

자 그럼 이제 코드로 한번 볼까요?


네 우선 저번의 Pop과 이번의 dequeue와 별다른게 없습니다.
enqueue의 경우는 마지막 부분에 새로 삽입되는 것이기 때문에 NULL일 때까지 찾아가는 것이죠.
그 뒤에 새로운 노드를 생성시켜 이어 주는것입니다.