[Java][자료구조] Queue / 큐 - 배열과 리스트를 사용한 구현

큐

FIFO, First-in First-out 위 단어가 큐를 가장 잘 설명해준다. 가장 먼저 들어온 요소가 가장 먼저 나온다! 우리가 줄을 서는 모든 것이 큐이다. 가장 잘 이해가 될 것이다. 원소를 넣는 것이 add() , 삭제하는 것이 remove() 이다.

 

배열과 리스트를 사용해 구현할 것인데, 리스트는 매우 쉬우므로 일단 생략하겠다.

배열을 이용해 구현할 때, 일반적인 배열을 사용한다면 삽입과 삭제가 일어나면서 오른쪽으로 계속 치우치는 현상이 일어날 것이다.

 

이를 해결하기 위해, 배열을 환형으로 만든다!

이렇게 만들기 위해 %연산자를 사용하여 front와 rear을 따로 설정해줘야 한다. front,rear = (front,rear+1) % N 으로 만들어 준다. 

만약 큐가 Empty가 되면 front가 rear의 뒤로 가는 현상을 막기 위해서 front를 맨 첫번째 원소 앞에 배치할 것이다.

 

물론 큐도 컬렉션에서 Queue<> q = new LinkedList<>()을 사용하면 바로 쓸 수 있지만 맨 처음에는 직접 구현해보면서 배우도록 하자!

 

코드

1. 배열을 통한 큐 구현

import java.util.NoSuchElementException;
 
public class ArrayQueue <E>{
    private E[] q;
    private int rear,front,size;
    
    public ArrayQueue() {
        q = (E[]) new Object[2];
        front = rear = size = 0;
    }
    
    public int size() {
        return size;
    }
    
    public boolean isEmpty() {
        return size==0;
    }
    
    public void resize(int length) {
        Object[] q2 = new Object[length];
        for(int i=1, j=front+1; i<size+1; i++,j++) {
            q2[i] = q[j%q.length];
        }
        front = 0;
        rear = size;
        
        q = (E[]) q2;
    }
    
    public void add(E newitem) {
        if((rear+1)%q.length == front) {
            resize(2*q.length);
        }
        //이 부분이 배열을 환형으로 만들어 주는 부분이다.
        rear = (rear+1) % q.length;
        q[rear] = newitem;
        size++;
    }
    
    public E remove() {
        if(isEmpty()) throw new NoSuchElementException();
        //이 부분이 배열을 환형으로 만들어 주는 부분이다.
        front = (front+1) % q.length;
        E item = q[front];
        q[front] = null;
        size--;
        
        if(size>0 && size == q.length/4) {
            resize(q.length/2);
        }
        return item;
    }
    
    public void print() {
        for(int i=0; i<q.length; i++) {
            System.out.print(q[i] + " ");
        }
        System.out.println();
    }
}
 

2. 리스트를 통한 큐 구현

import java.util.NoSuchElementException;
 
public class ListStack <E>{
    private Node<E> top;
    private int size;
    
    public ListStack() {
        top = null;
        size = 0;
    }
    
    public int size() {
        return size;
    }
    
    public boolean isEmpty() {
        return size==0;
    }
    
    public void push(E newitem) {
        top = new Node<E>(newitem, top);
        size++;
    }
    
    public E peek() {
        if(isEmpty()) throw new NoSuchElementException();
        
        return top.getKey();
    }
    
    public E pop() {
        if(isEmpty()) throw new NoSuchElementException();
        
        E item = top.getKey();
        top = top.getNext();
        size--;
        
        return item;
    }
    
    public void show() {
        Node<E> temp = top;
        for(int i=0; i<size; i++) {
            System.out.print(temp.getKey() + " ");
            temp = temp.getNext();
        }
        System.out.println();
    }
}
 
class Node <E>{
    private E key;
    private Node<E> next;
    
    public Node(E newkey, Node<E> next) {
        key = newkey;
        this.next = next;
    }
 
    public E getKey() {
        return key;
    }
 
    public void setKey(E key) {
        this.key = key;
    }
 
    public Node<E> getNext() {
        return next;
    }
 
    public void setNext(Node<E> next) {
        this.next = next;
    }
}