[자료구조] 큐 (python, java)

큐

큐는 먼저 삽입된 데이터가 먼저 나오는 FIFO특성을 지닌 자료구조이다.
데이터를 한쪽 끝에서 삽입하고 반대편 끝 쪽에서 빼낸다.

순서대로 데이터를 처리하기 위해 사용된다.

Python)

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, value):
        new_node = Node(value)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
            return

        # 새 노드를 tail뒤에 연결하고 tail로 설정
        self.tail.next = new_node
        self.tail = new_node

    def dequeue(self):
        if self.is_empty():
            return "queue is empty"
        delete_node = self.head
        self.head = self.head.next
        return delete_node

    def peek(self):
        if self.is_empty():
            return "queue is empty"
        return self.head.data

    def is_empty(self):
        return self.head is None

• enqueue와 dequeue 메소드를 보면, 데이터 삽입이 tail, 데이터 꺼내는 것이 head에서 이루어지는 것을 볼 수 있다. (양쪽 끝에서 데이터 삽입/삭제가 이루어짐!)

---

Java)

자바에서는 Queue 자료구조 사용을 편리하게 하기 위해 java.util 패키지에 Queue 클래스를 제공한다.

Queue<Integer> queue_int = new LinkedList<Integer>(); // Integer 형 queue 선언
Queue<String> queue_str = new LinkedList<String>(); // String 형 queue 선언

queue_int.offer(2);  // 추가
queue_int.poll();    // 삭제

직접 구현해보기)

public class MyQueue<T> {
    private ArrayList<T> queue = new ArrayList<T>();
    
    // 데이터 추가
    public void enqueue(T data) {
        queue.add(data);
    }
    
    // 데이터 삭제
    public T dequeue() {
        if (queue.isEmpty()) {
            return null;
        }
        return queue.remove(0);
    }
    
    public boolean isEmpty() {
        return queue.isEmpty();
    }
    
    public static void main(String[] args) {
        MyQueue<Integer> mq = new MyQueue<Integer>();
        mq.enqueue(1);
        mq.enqueue(2);
        mq.enqueue(3);
        System.out.println(mq)
    }
}

큐는 데이터의 삽입/삭제가 빈번하기 때문에 링크드 리스트로 구현하는 것이 바람직하다.