[자료구조] 연결 리스트를 이용한 큐 / 스택의 구현 | Linked Queue & Stack

앞서 설명한 링크드 리스트를 이용해, 큐와 스택을 그대로 구현할 수 있습니다.

 

 

연결 큐의 구현은 다음과 같습니다.

링크드 리스트의 맨 앞에 위치한 노드를 Front, 맨 뒤에 위치한 노드를 Rear라고 했을 때, 

Dequeue는 기존 Front의 다음에 있는 노드를 새로운 Front로,

Enqueue는 기존 Rear 다음에 새로 추가된 노드를 Rear로 변경하는 방식으로 구현합니다.

 

연결 스택의 구현은 다음과 같습니다.

링크드 리스트의 맨 앞에 위치한 노드를 Top, 맨 뒤에 위치한 노드를 Bottom라고 했을 때, 

Pop은 기존 Top의 다음에 있는 노드를 새로운 Top으로,

Push는 새로 추가된 노드를 Top으로 변경하고, 포인터를 기존 Top과 연결하는 방식으로 구현합니다.