쉽게 배우는 자료구조 - Chap7.

큐(Queue)

가장 먼저 들어온 것이 가장 먼저 나가는 구조인 FIFO(First-In-First-Out, 선입선출)을 가지고 있다.

큐의 개념과 원리

큐의 맨 앞에 잇는 원소(맨 먼저 들어온 원소)를 front라고 하고, 맨뒤에 있는 원소(맨 나중에 들어온 원소)를 tail이라 한다.
큐에서 삽입(enque)할 때 삽입할 원소를 알려주어야 하며 삭제(deque)할 때는 단순히 삭제하라고 한다.
스택에서 삭제는 무조건 최근 들어간 원소를 대상으로 하기 때문에 삭제할 원소는 명시할 필요가 없다.

추상 데이터 타입 큐(ADT Queue)

맨 끝에 원소를 추가한다.
원소를 삭제하면서 알려준다.
맨 앞의 원소를 알려준다.
큐가 비어 있는지 확인한다.
큐를 깨끗이 비운다.

배열을 이용한 큐

큐의 최대 크기를 예상할 수 있는 경우에는 배열이 가장 적합하지만 크기를 예상할 수 없는 경우에는 운영하다가 더 큰 배열로 옮기는 작업을 수행해야한다.
이런 불편함에도 불구하고 배열 기반 큐는 간명함과 효율성이 뛰어나 많이 사용한다.

각 필드의 작업 의미

queue[] <- 큐에 원소들이 저장되는 배열
numItems <- 큐의 총 원소 수 저장
front <- 큐 맨 앞 원소의 인덱스
tail <- 큐 맨 뒤 원소의 인덱스
enque(x) <- 큐의 끝에 원소 x를 삽입한다.
dequeue() <- 큐의 맨 앞에 있는 원소를 알려주고 삭제한다.
front() <- 큐의 맨 앞에 있는 원소를 알려준다.
isEmpty() <- 큐가 비어있는지 알려준다.
dequeueAll() <- 큐를 깨끗이 청소한다.

Array Queue.java

package queue;

public class ArrayQueue<E> implements QueueInterface<E> {
    
    private E queue[];
    private int front, tail, numItems;
    private static final int DEFAULT_CAPACITY = 64;
    private final E ERROR = null; //임의의 에러값

    public ArrayQueue() { // 생성자 1
        queue = (E[]) new Object[DEFAULT_CAPACITY];
        front = 0;
        tail = DEFAULT_CAPACITY - 1;
        numItems = 0;
    }

    public ArrayQueue(int n) { // 생성자 2
        queue = (E[]) new Object[n];
        front = 0;
        tail = n - 1;
        numItems = 0;
    }

    // 큐에 원소 삽입하기
    public void enqueue(E newItem) {
        if (isFull()) { System.out.println("Queue is full!"); } 
        else {
            tail = (tail + 1) % queue.length;
            queue[tail] = newItem;
            numItems++;
        }
    }

    // 큐가 꽉 찼는지 확인하기
    public boolean isFull() {
        return (numItems == queue.length);
    }
    
    // 큐에서 원소 삭제하기
    public E dequeue() {
        if (isEmpty()) return ERROR;
        else {
            E queueFront = queue[front];
            front = (front + 1) % queue.length;
            numItems--;
            return queueFront;
        }
    }
 
    // 큐에서 맨 앞의 원소 알려주기
    public E front() {
        if (isEmpty()) return ERROR;
        else return queue[front];
    }

    // 큐가 비었는지 확인하기
    public boolean isEmpty() {
        return (numItems == 0);
    }

    // 큐 비우기
    public void dequeueAll() {
        queue = (E[]) new Object[queue.length];
        front = 0;
        tail = queue.length - 1;
        numItems = 0;
    }
}

연결리스트를 이용한 큐

LinkedQueue.java

package queue;
import list.Node;

public class LinkedQueue<E> implements QueueInterface<E> {
    private Node<E> tail;
    private final E ERROR = null; //임의의 에러 값

    public LinkedQueue() {
        tail = null;
    }

    //큐에 원소 삽입하기
    public void enqueue(E newItem) {
        Node<E> newNode = new Node<>(newItem);
        if (isEmpty()) {
            newNode.next = newNode;
            tail = newNode;
        } else {
            newNode.next = tail.next;
            tail.next = newNode;
            tail = newNode;
        }
    }

    //큐에 원소 삭제하기
    public E dequeue() {
        if (isEmpty()) return ERROR;
        else {
            Node<E> front = tail.next;
            if (front == tail)  // only one item in queue
                tail = null;
            else  // more than one Item
                tail.next = front.next;
            return front.item;
        }
    }

    // 큐 맨 앞의 원소 알려주기
    public E front() {
        if (isEmpty()) return ERROR;
        else return tail.next.item; //tail.next: front
    }

    // 큐가 비었는지 확인하기
    public boolean isEmpty() {
        return (tail == null);
    }

    // 큐 깨끗이 비우기
    public void dequeueAll() {
        tail = null;
    }
}

큐 응용: 좌우동형 문자열 체크

좌우동형(palindrome)문자열 이란?

앞에서 읽으나 뒤에서 읽으나 같은 문자열을 말한다.
ex) 'abbcbba'는 앞에서 읽으나 뒤에서 읽으나 같으므로 좌우 동형이다.
but, 'abb'는 좌우 동형이 아니다.

Palindrome.java

package queue;
import stack.LinkedStack;

public class Palindrom {
	private static boolean isPalindrom(String A) {
    	LinkedStack s = new LinkedStack();
        LinkedQueue q = new LinkedQueue();
        for (int i = 0; i < A.length(); i++) {
        	s.push(A.charAt(i)); //문자열 A의 i번째 문자
            q.enqueue(A.charAt(i));
        }
        while(!s.isEmpty() && s.pop() == q.dequeue()) {
        }
        if(if(s.isEmpty()) return true;
        else return false;
    }
    
    public static void main(String[] args) {
    	System.out.println("Palindrome Check!")
        String str = "loininoil"
        boolean t = isPalindrom(str);
        System.out.println(str + "is Palindrom: " + t);
    }
}