8. 큐(Queue) - 선형 큐(Linked Queue)

1. 큐(Queue) 개념

선입선출(First-In-First-Out: FIFO)형 자료구조

순서가 보장된 처리 (사용자가 몰린 서버 응답 처리)

 

 

주요 동작 (언어마다 동작명이 조금 다르지만 같은 기능)

push() = offer(), add() : 데이터 추가

pop() = poll() : 데이터 빼오기

peek() : 데이터 확인

---

2. 선형 큐(Linked Queue) 구현 (JAVA)

큐는 선형구조이지만 배열로 구현하는 것은 비효율적이다.

(데이터를 전체적으로 옮기는 연산을 넣어야하기 때문에)

따라서 Linked List Node 기반으로 큐를 구현한다.

생성자로 인한 처음 상태

데이터 추가 후 모습

package queue;

public class MyLinkedQueue<T> implements IQueue<T> {
    private Node head;
    private Node tail;
    private int size;

    public MyLinkedQueue() {        // 생성자 처음 상태를 그림으로 참고하라
        this.size = 0;              // size는 0이고 head, tail 모두 null을 참조하고 있다.
        this.head = new Node(null);
        this.tail = this.head;
    }

    @Override
    public void offer(T data) {     // 먼저들어온 노드가 head쪽으로 밀리면서 가장 최신의 노드가 tail쪽에 위치한다.
        Node node = new Node(data); // data를 집어 넣은 새로운 노드
        this.tail.next = node;      // 새로운 노드를 tail 뒤로 집어 넣고
        this.tail = this.tail.next;     // 가장 마지막에 위치한 노드가 tail이 되도록 한다.
        this.size++;
    }

    @Override
    public T poll() {       // 가장 처음에 들어왔던 노드(head바로 옆) 데이터를 반환하고 삭제하는 동작
        if (isEmpty()) {    // 데이터가 아예 처음이면 오류 반환
            throw new IllegalStateException();
        }
        Node ret = this.head.next;  // head 앞에 있는 가장 처음 들어왔던 node 선택
        this.head.next = ret.next;  // head의 연결을 선택한 노드의 다음으로 바꾼다
        ret.next = null;            // 선택한 노드의 연결을 끊는다
        this.size--;
        if (this.head.next == null) {   // 만약 head의 다음 연결이 null이면 데이터가 하나 밖에 안들어 있었어서
            this.tail = this.head;      // head=tail로 초기화 시킨다
        }
        return ret.data;            // 선택했던 노드의 데이터를 반환한다.
    }

    @Override
    public T peek() {       // 데이터를 빼지 않고 가장 먼저 들어온 데이터(head 바로 앞) 확인
        if (isEmpty()) {
            throw new IllegalStateException();
        }
        return this.head.next.data;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public void clear() {  // 데이터 초기화
        this.head.next = null;
        this.tail = head;
        this.size = 0;
    }

    @Override
    public boolean isEmpty() {
        return this.head.next == null;  // head 뒤가 null이면 비어 있는 상태이다.
    }

    private class Node {        // 기본 Node 구현
        T data;
        Node next;

        Node(T data) {
            this.data = data;
        }

        Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
}

---

3. 선형 큐(Linked Queue) 구현 (Python)

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

class LinkedQueue:

    def __init__(self):
        self._size = 0
        self.head = Node(None)
        self.tail = self.head

    def offer(self, data):
        node = Node(data)
        self.tail.next = node
        self.tail = self.tail.next
        self._size += 1

    def poll(self):
        if self._size == 0:
            raise RuntimeError("Empty")

        ret = self.head.next
        self.head.next = ret.next
        ret.next = None
        self._size -= 1
        if self.head.next is None:
            self.tail = self.head
        return ret.data

    def peek(self):
        if self._size == 0:
            raise RuntimeError("Empty")
        return self.head.next.data

    def size(self):
        return self._size

    def clear(self):
        self.head.next = None
        self.tail = self.head
        self._size = 0


if __name__ == '__main__':
    q = LinkedQueue()
    for elem in [5, 3, 6, 8, 9, 10]:
        print(f"q.offer({elem})")
        q.offer(elem)

    print(f"q.size(): {q.size()}")
    while q.size() > 0:
        print(f"q.peek(): {q.peek()}")
        print(f"q.pop(): {q.poll()}")

    print(f"q.size(): {q.size()}")