[JAVA/자료구조] 강의노트 2강 下 : 큐(Queue) 1차원 배열(Array-Based), 순환형(Circle), 연결 리스트(Linked List) 구현, 코드

---

강의노트 2강에서는 자료구조 중 Stack과 Queue에 대하여 공부해보고자 합니다.

저번 시간에 알아본 스텍 다음으로 오늘은 큐에 대하여 공부해보겠습니다.

1) 큐(Queue)

스텍은 자료를 저장하는 방식으로 FIFO 구조를 따릅니다.

FIFO는 Frist-In Frist-Out의 약자로 선입선출의 구조입니다.

스텍과 달리 가장 처음에 삽입된 자료가 우선순위를 가지는 자료구조입니다.

일반적으로 실생활에서 접할 수 있는 지하철 역에서 줄서기를 떠올리시면 이해하시기 쉽습니다.

가장 먼저 줄을 선 사람이 처음으로 지하철에 탑승할 수 있겠죠?

 

2) Queue Operation

- enqueue(object) : 큐에 elemeent를 삽입합니다.

- object dequeue() : 큐에 element를 제거합니다.

- object front() : 큐 최상단 element를 보여줍니다.

- integer size() : 큐의 크기를 보여줍니다.

- boolean isEmpty() : 큐가 비어져있는지 아닌지 판단합니다.

---

!) Queue Opearation Example

Operation	Output	In_Queue
enqueue(3)	-	(3)
enqueue(5)	-	(3, 5)
dequeue()	3	(5)
enqueue(7)	-	(5, 7)
front()	7	(5, 7)
isEmpty()	false	(5, 7)
dequeue()	5	(7)
dequeue()	7	()
dequeue()	"error"	()

---

큐 역시 스텍과 마찬가지로 자바에서 유틸 패키지로 지원합니다.

지금도 학습하는 시간이니 Array구조로 된 Queue를 조금 더 공부해보도록 하겠습니다.

* Queue interface

public interface Queue {
    public int size();
    public boolean isEmpty();
    public char front();
    public char enqueue(char o);
    public char dequeue();
}

 

3) Array-based Stack 

큐가 처음에 비어져 있었을 때의 모습과 한 개의 object가 큐에 enqueue되었을 때입니다.

f는 front로 queue에 저장되어 있는 element중 가장 처음으로 삽입된 element를 가르킵니다.

r은 다음에 queue에 element가 삽입될 공간을 가르키는 것으로, 항상 비워져있어야합니다.

f와 r은 큐의 시작지점에서 N-1(큐의 사이즈 -1)지점의 방향으로 이동합니다.

r이 N-1지점까지 도달한다면 r은 다시 큐의 시작지점으로 돌아오도록 설계할 수도 있습니다.

이런 큐를 순환형 큐, 원형 큐라고 표현합니다.

만약 r이 f를 따라잡게 된다면, 큐의 저장공간이 모두 찼음을 의미합니다.

 

Array-based Queue JAVA Code

public class ArrayQueue {
    private char[] data;
    private int front;
    private int rear;
    private int size;
 
    public ArrayQueue(int size){
        this.front = -1;
        this.rear = -1;
        this.size = size;
        this.data = new char[size];
    }
 
    // isFull() = (rear == this.size-1);
    public boolean isEmpty() {
        return (front == rear);
    }
    
    //if queue isFull exception 처리 필요
    public char front() {
        return this.data[this.front];
    }
    
    //if queue isEmpty Exception 처리 필요
    public char enqueue(char o) {
        data[++rear] = o;
    }
 
    public char pop() {
         return data[++front]
    }
 
}

Circle Queue Enqueue&Dequeue

public char enqeue(char o) {
    // if queue iSFull exception 처리 필요
    this.rear = (++rear) % suze;
    this.data[rear] = o;
}
 
public char deque() {
    // if queue iSEmpty exception 처리 필요
    char returnC = this.front;
    this.front = (++front) % size;
    return this.data[returnC]
}
 
    

4) Linked-List Qeueue

큐 역시 스텍과 마찬가지로 연결리스트로도 구현할 수 있습니다.

---

!) 연결리스트란?

연결리스트(스텍) 설명보러가기

---

*Node

public class Node {
    private Object data;
    private Node nextNode;
    
    public Node(Object data){
    this.data = data;
    this.nextNode = null;
    }
    
    public void linkNode(Node top){
    this.nextNode = top;
    }
    
    public Object getData(){
    return this.data;
    }
    
    public Node getNextNode(){
    return this.nextNode;
    }
}

 

Linked-List Queue Enqueue&Dequeue

public void enqueue(Object item){
    Node newNode = new Node(item);
    node.nextNode = null;  
    
    if(isEmpty()){
        rear = node;
        front = node;
    } else{
        rear.nextNode = node;
        rear = node;
        }
}
 
public Object dequeue(){
    //peek() = data[front]
    Object returnC = this.peek();
    this.front ++;
    return returnC;
}