[알고리즘] 2.2.자료구조 : 연결리스트를 이용한 큐(Queue) 구현

  큐 이해하기

2017/01/30 - [Programming/Algorithm] - [알고리즘] 2.2.자료구조 : 큐(Queue)

  연결리스트를 이용한 큐 구현

배열로 구현한 큐의 단점은 크기를 미리 정해야 하고, 그 크기를 넘어서면 error가 발생한다는 것입니다. 반면 연결리스트로 구현하면 큐의 크기(size)를 미리 정할 필요가 없습니다. 위의 그림의 100번지, 200번지에 해당하는 것이 node인데 이 node는 앞의 게시물인 스택에서 구현한 노드class를 가져다 사용하겠습니다. 

//연결 리스트로 사용 할 노드 class

public class Node {

private Object data;

private Node nextNode;

public Node(Object data){

this.data = data;

this.nextNode = null;

}

//해당 노드를 원하는 노드(Node top)와 연결해주는 메소드

public void linkNode(Node top){

this.nextNode = top;

}

//해당 노드의 데이터를 가져오는 get메소드

public Object getData(){

return this.data;

}

//해당 노드와 연결된 노드를 가져오는 get메소드

public Node getNextNode(){

return this.nextNode;

}

}

public class ListQueue {

private Node front;

private Node rear;

public ListQueue(){

this.front = null;

this.rear = null;

}

public boolean isEmpty(){

if (front == null) return true;

else return false;

}

public void enQueue(Object item){

Node newNode = new Node(item);

//추가하는 Node가 처음인지 아닌지

//처음이면 rear,front모두 추가한 노드로 초기화

//처음이 아니면 이전에 있는 노드와 새로 추가된 노드를 연결

//rear를 새로 추가한 노드로 초기화

if(isEmpty()){

rear = newNode;

front = newNode;

}else{

rear.linkNode(newNode);

rear = newNode;

}

}

public Object peek(){

return front.getData();

}

public Object deQueue(){

Object backUpItem = peek();

//front를 삭제한 다음 Node로 초기화

front = front.getNextNode();

//삭제한 노드가 마지막 노드였을 경우 rear도 초기화

if(front == null) rear = null;

return backUpItem;

}

}

우선 살펴봐야 할 것이 front와 rear입니다. 배열에서는 이 두 변수가 인덱스(위치)였지만 연결리스트에서는 Node입니다. 새로 추가한 데이터(Node)를 보면 배열에서는 rear에 +1을 하여 그 위치에 데이터를 추가하였는데, 연결리스트에서는 일단 새로 추가할 데이터를 만든 후 rear에 새로 추가한 노드를 넣어주면 됩니다. 

enQueue()를 보면, 우선 처음 추가하는 것인지 아닌지 확인을 하여야 합니다. 만약 처음 추가하는 것이면 front,rear노드 모두 새로 추가한 노드를 가리켜야 합니다. 반면에 이전에 큐가 있으면 rear가 새로 추가된 노드를 가리키면 됩니다. 그리고 이전에 있던 큐와 연결시켜야 하는데 rear.linkNode(newNode); 이렇게 구현되어있습니다. 여기서 rear는 이전에 있던 큐의 마지막 노드입니다. 따라서 rear(마지막노드)와 새로 추가된 노드(newNode)를 연결시켜줘야 합니다.

deQueue()는 front를 다음 노드를 가리키면 됩니다. 그러면 삭제된 노드의 다음노드가 맨 처음 노드가 됩니다. front = front.getNextNode();