자료구조 - Queue

Queue

---

queue 자료구조

• 선입선출 알고리즘으로 먼저 들어온 데이터를 먼저 반환한다.

• 시간 복잡도
  1. insert: O(1)
  2. delete: O(1)
  3. search: O(n)

 

구현 with JAVA

//큐를 만들기 위해 필요한 연결 노드 정보
class QueueNode {
    private int data;
    private QueueNode link;
 
    public QueueNode(int data) {
        this.data = data;
        this.link = null;
    }
 
    public int getData() {
        return this.data;
    }
}
public class Queue {
    private QueueNode head, tail;
    private int size;
 
    //생성자
    public Queue(int size) {
        head = null;
        tail = null;
        this.size = size;
    }
 
    public boolean isEmpty() {
        return (head == null && tail == null);
    }
 
    public boolean isFull() {
        int nodeCount = 0;
        QueueNode temp = head;
 
        if(head == null) return false;
        while(temp.link != null) {
            nodeCount++;
            temp = temp.link;
        }
        return (this.size - 1 == nodeCount);
    }
 
    //큐에 data insert
    public void add(int data) {
        QueueNode temp = new QueueNode(data);
    
        if(isFull()) return; //큐에 정보를 저장하기 전에 큐가 꽉 찼는지 검사
        else if(isEmpty()) { //큐에 정보를 저장하기 전에 큐가 비어있는지 즉, 첫 번째 노드인지 확인
            this.head = temp;
            this.tail = temp;
        } else {
            tail.link = temp;
            tail = temp;
        }
    }
 
    //첫 데이터 조회
    public int peek() {
        if(isEmpty()) return; //데이터 조회하기 전에 큐가 비어있는지 검사
        return head.getData();
    }
 
    //첫 데이터 반환(조회 후 삭제)
    public QueueNode poll() {
        QueueNode temp;
 
        if(isEmpty()) return; //데이터를 반환하기 전에 큐가 비어있는지 검사
        else if(head.link == null) { //데이터를 반환하기 전에 현재 노드가 하나밖에 안남아 삭제할 노드가 마지막 노드인지 확인
            temp = head;
            head = null;
            tail = null;
        } else {
            temp = head;
            head = head.link;
        }
        return temp;
    }
 
    //data가 큐에 몇 번째에 존재하는지 검색
    public int search(int data) {
        QueueNode temp = head;
        int count = 1;        
 
        if(isEmpty()) return;
        while(temp.link != null) {
            if(temp.getData() == data) return count;
            temp = temp.link;
            count++;
        }
        return -1; //데이터가 큐에 존재하지 않음.
    }
}

 

reference