[자료구조] 큐(QUEUE)

1. 큐(queue)란

큐란 자료구조의 하나로서 먼저 들어간 자료가 먼저 출력되는 선입선출의 방식을 가지고 있는 자료구조입니다. 이를 FIFO(First In First Out)이라고도 합니다.

 

출처: 얄코의 가장 쉬운 자료구조와 알고리즘

 

 위 그림에서 볼 수 있듯이 큐는 아래에 뚫린 통의 형태라고 할 수 있습니다.

큐에는 데이터를 삽입하는 enqueue와 데이터를 제거하는 dequeue가 있습니다. 

큐에서의 시간복잡도는 삽입, 제거 모두 O(1)입니다.

 

큐에도 배열기반 또는 연결리스트 기반으로 구현가능합니다.

그런데 큐는 스택과 달리 배열기반에서는 주의할것이 있습니다.

 

배열기반에서 큐를 구현하려면 원형 배열에서 구현해야합니다. 왜냐하면 선형 큐에서는 첫번째 요쇼의 인덱스와 마지막 요소의 인덱스가 고정되어있어 데이터를 제거 후 데이터 삽입이 안되는 반면, 원형 큐에서는 요소가 배열에 끝에 도달할때마다 다시 처음으로 순환하여 빈자리를 재사용할 수 있기 때문입니다.

 

이를 파이썬과 자바코드로 확인해보겠습니다

 

1) 배열기반 큐

class CircularQueue:
    def __init__(self, capacity):
        self.capacity = capacity # 요소의 수용량 -> 큐의 크기
        self.queue = [None] * capacity 
        self.front = 0 # 큐의 시작점
        self.rear = 0 # 큐의 끝점
        self.size = 0 # 요소가 들어있는 개수

    def is_empty(self):
        return self.size == 0
        
    def is_full(self):
        return self.size == self.capacity
        
    def enqueue(self, item):
        if self.is_full():
            print("Queue is full")
            return
        self.queue[self.rear] = item
        self.rear = (self.rear + 1) % self.capacity
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            print("Queue is empty")
            return None
        item = self.queue[self.front]
        self.queue[self.front] = None  # optional: clear slot
        self.front = (self.front + 1) % self.capacity # 요소를 제거한 뒤 큐의 시작점을 이동
        self.size -= 1
        return item
    
    # 큐에있는 요소를 출력하는 메서드
    def display(self):
        result = []
        i = self.front
        for _ in range(self.size):
            result.append(self.queue[i])
            i = (i + 1) % self.capacity
        print(result)


cq = CircularQueue(5)

cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.enqueue(40)
cq.enqueue(50)

cq.display()  # [10, 20, 30, 40, 50]

print(cq.dequeue())  # 10
print(cq.dequeue())  # 20
print(cq.dequeue())  # 30

cq.enqueue(60)
cq.enqueue(70)

cq.display()  # [40, 50, 60, 70]

 

자바

public class CircularQueue {
    private int[] queue;
    private int capacity;
    private int front; //큐의 시작점
    private int rear; // 큐의 끝점
    private int size;

    public CircularQueue(int capacity) {
        this.capacity = capacity;
        this.queue = new int[capacity];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }
    
    public boolean isEmpty() { 
	    return size == 0; 
	  }
    
    public boolean isFull() {
	    return size == capacity;
	  }

    public void enqueue(int item) {
        if (isFull()) {
            System.out.println("Queue is full");
            return;
        }
        queue[rear] = item;
        rear = (rear + 1) % capacity;
        size++;
    }

    public Integer dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return null;
        }
        int item = queue[front];
        queue[front] = 0; // optional: clear slot
        front = (front + 1) % capacity; // 요소를 제거한 뒤 큐의 시작점을 이동
        size--;
        return item;
    }
    
    // 큐에 들어있는 요소를 확인하는 메서드
    public void display() {
        int index = front;
        for (int i = 0; i < size; i++) {
            System.out.print(queue[index] + " ");
            index = (index + 1) % capacity;
        }
        System.out.println();
    }

    public static void main(String[] args) {
    
        CircularQueue cq = new CircularQueue(5);
        
        cq.enqueue(10);
        cq.enqueue(20);
        cq.enqueue(30);
        cq.enqueue(40);
        cq.enqueue(50);
        
        cq.display(); // 10 20 30 40 50

        System.out.println(cq.dequeue()); // 10
        System.out.println(cq.dequeue()); // 20
        System.out.println(cq.dequeue()); // 30

        cq.enqueue(60);
        cq.enqueue(70);
        
        cq.display(); // 40 50 60 70
    }
}

 

2) 연결리스트 기반 큐

파이썬

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

class LinkedListQueue:
    def __init__(self):
        self.front = None
        self.rear = None
    
    def is_empty(self):
        return self.front is None

    def enqueue(self, item):
        new_node = Node(item)
        if self.rear is None:
            self.front = self.rear = new_node
            return
        self.rear.next = new_node
        self.rear = new_node

    def dequeue(self):
        if self.front is None:
            print("Queue is empty")
            return None
        item = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return item

    def display(self):
        current = self.front
        result = []
        while current:
            result.append(current.data)
            current = current.next
        print(result)


q = LinkedListQueue()

q.enqueue(10)
q.enqueue(20)
q.enqueue(30)

q.display()  # [10, 20, 30]

print(q.dequeue())  # 10
print(q.dequeue())  # 20

q.enqueue(40)
q.enqueue(50)

q.display()  # [30, 40, 50]

 

자바

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
    }
}

public class LinkedListQueue {

    private Node front;
    private Node rear;

    public boolean isEmpty() { return front == null; }

    public void enqueue(int item) {
        Node newNode = new Node(item);
        if (rear == null) {
            front = rear = newNode;
            return;
        }
        rear.next = newNode;
        rear = newNode;
    }

    public Integer dequeue() {
        if (front == null) {
            System.out.println("Queue is empty");
            return null;
        }
        int item = front.data;
        front = front.next;
        if (front == null) rear = null;
        return item;
    }

    public void display() {
        Node current = front;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
    
        LinkedListQueue q = new LinkedListQueue();
        
        q.enqueue(10);
        q.enqueue(20);
        q.enqueue(30);
        
        q.display(); // 10 20 30

        System.out.println(q.dequeue()); // 10
        System.out.println(q.dequeue()); // 20

        q.enqueue(40);
        q.enqueue(50);
        
        q.display(); // 30 40 50
    }
}

3. 내장 라이브러리 큐

파이썬에는 큐가 내장 라이브러리로 존재합니다.

사용방법은 아래와 같습니다.

import queue

q = queue.Queue()

q.put(3)
q.put(5)
q.put(4)

while not q.empty():
    print(q.get(),end=' ') # 3 5 4

print() ## 줄바꿈

q2 = queue.LifoQueue() ## 후입선출 큐
q2.put(4)
q2.put(7)
q2.put(9)
q2.put(10)

while not q2.empty():
    print(q2.get(),end=" ") # 10 9 7 4

 

2. Deque

데크(Deque)는 큐처럼 앞에서 넣고 앞에서 뺄수도 있으며 스택처럼 뒤에서 넣고 뒤에서 뺄수도 있는 자료구조입니다. 앞에서 넣고 뒤에서 빼는 교차사용도 가능합니다. 이 모든 작업의 시간복잡도는 스택이나 큐와 동일하게 O(1)입니다.

 

이를 코드로 확인해보겠습니다.

 

1) 연결리스트 기반 Deque

파이썬

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

class LinkedListDeque:
    def __init__(self):
        self.front = None
        self.rear = None

    def push_front(self, item):
        new_node = Node(item)
        if self.front is None:
            self.front = self.rear = new_node
        else:
            new_node.next = self.front
            self.front.prev = new_node
            self.front = new_node

    def push_back(self, item):
        new_node = Node(item)
        if self.rear is None:
            self.front = self.rear = new_node
        else:
            new_node.prev = self.rear
            self.rear.next = new_node
            self.rear = new_node

    def pop_front(self):
        if self.front is None:
            print("Deque is empty")
            return None
        item = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        else:
            self.front.prev = None
        return item

    def pop_back(self):
        if self.rear is None:
            print("Deque is empty")
            return None
        item = self.rear.data
        self.rear = self.rear.prev
        if self.rear is None:
            self.front = None
        else:
            self.rear.next = None
        return item
	
    # 맨앞의 요소를 확인하는 메서드
    def peek_front(self):
        return self.front.data if self.front else None
	
    # 맨뒤의 요소를 확인하는 메서드
    def peek_back(self):
        return self.rear.data if self.rear else None


dq = LinkedListDeque()

dq.push_front(10)
dq.push_back(20)
dq.push_front(5)

print(dq.peek_front())  # 5
print(dq.peek_back())   # 20

print(dq.pop_back())    # 20
print(dq.pop_front())   # 5
print(dq.pop_front())   # 10
print(dq.pop_front())
# Deque is empty
# None

 

자바

class Node {
    int data;
    Node prev, next;
    Node(int data) { this.data = data; }
}

public class LinkedListDeque {

    private Node front, rear;

    public void pushFront(int item) {
        Node newNode = new Node(item);
        if (front == null) {
            front = rear = newNode;
        } else {
            newNode.next = front;
            front.prev = newNode;
            front = newNode;
        }
    }
    public void pushBack(int item) {
        Node newNode = new Node(item);
        if (rear == null) {
            front = rear = newNode;
        } else {
            newNode.prev = rear;
            rear.next = newNode;
            rear = newNode;
        }
    }

    public Integer popFront() {
        if (front == null) {
            System.out.println("Deque is empty");
            return null;
        }
        int item = front.data;
        front = front.next;
        if (front == null) rear = null;
        else front.prev = null;
        return item;
    }
    public Integer popBack() {
        if (rear == null) {
            System.out.println("Deque is empty");
            return null;
        }
        int item = rear.data;
        rear = rear.prev;
        if (rear == null) front = null;
        else rear.next = null;
        return item;
    }
	
    // 맨앞의 요소를 확인하는 메서드
    public Integer peekFront() {
        return (front != null) ? front.data : null;
    }
	
    //맨뒤의 요소를 확인하는 메서드
    public Integer peekBack() {
        return (rear != null) ? rear.data : null;
    }

    public static void main(String[] args) {
    
        LinkedListDeque dq = new LinkedListDeque();
        
        dq.pushFront(10);
        dq.pushBack(20);
        dq.pushFront(5);
        
        System.out.println(dq.peekFront()); // 5
        System.out.println(dq.peekBack());  // 20
        
        System.out.println(dq.popBack());   // 20
        System.out.println(dq.popFront());  // 5
        System.out.println(dq.popFront());  // 10
        System.out.println(dq.popFront());  
        // Deque is empty
        // null
    }
}

 

2) 내장 라이브러리 Deque

from collections import deque

dq = deque([2,4,5])

print(dq) # deque([2, 4, 5])

dq.append(10) # tail에 추가
print(dq) # deque([2, 4, 5, 10])

dq.appendleft(30) # head에 추가
print(dq) # deque([30, 2, 4, 5, 10])

dq.insert(1,7) # 특정 인덱스에 삽입
print(dq) # deque([30, 7, 2, 4, 5, 10])

t1 = dq.pop() # tail 요소 제거
print(t1) # 10
print(dq) # deque([30, 7, 2, 4, 5])

h1 = dq.popleft() # head 요소 제거
print(h1) # 30
print(dq) # deque([7, 2, 4, 5])

dq.remove(2) # 특정 요소값 제거
print(dq) # deque([7, 4, 5])

dq.appendleft(5)
print(dq) # deque([5, 7, 4, 5])
dq.remove(5) # 같은 요소가 있다면 앞에서 제거
print(dq) # deque([7, 4, 5])

dq.reverse() # 뒤집기
print(dq) # deque([5, 4, 7])

 

 

참조: 얄코의 가장 쉬운 자료구조와 알고리즘
https://inf.run/Th7xU

얄코의 가장 쉬운 자료구조와 알고리즘| 얄팍한 코딩사전 - 인프런 강의