큐 - 리스트로 구현

 

1) 리스트를 이용한 큐

- 리스트를 이용한 큐에도 원형 큐처럼 front와 rear가 존재합니다. 

   front는 꺼내야 할 노드를 가리키고, rear는 맨 마지막 노드를 가리킵니다. 

   rear를 통해 빠르게 마지막 노드를 찾아, 마지막 노드의 다음 노드로 삽입할 수 있도록 합니다. 

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

class Node{
	Node next;
    Object data;
}


public class ListQueue{

	Node front;
    Node rear;
    
    public boolean isEmpty(){
    	return null == front;
    }
    
    public void add(Object data){
    	Node newNode = new Node();
        newNode.data = data;
        if(isEmpty()){
        	front = rear = newNode;
        }else{
        	rear.next = newNode;
            rear = newNode;
        }
    }
    
    public Object poll(){
    	if(isEmpty()){
        	return null;
        }
        
        Node removeNode = front;
        Object tempData = removeNode.data;
        front = removeNode.next;
        
        if(removeNode == rear){
        	rear = null;
        }
        return tempData;
    }
    
    public Object peek(){
    	if(isEmpty()){
        	return null;
        }
        return front.data;
    }
    
}

 

참고

[자바 자료구조 강의] Queue(리스트) - 구현 - 코드라떼 (codelatte.io)