선형 큐(Linear Queue)



- FIFO - First In First Out(선입선출)

인큐(EnQueue)를 통해 자료 입력, 디큐(DeQueue)을 통해 자료 출력


* 매표소, 가장 먼저 줄서있는 사람에게 표를 먼저 제공한다.



* 선형 큐 알고리즘은 Rear가 배열의 끝에 닿아 있으면, 앞에 배열의 빈 부분(Q[0])이 남아 있어도 더이상 삽입연산을 하지 못한다.

메모리를 효율적으로 관리하지 못함. 이러한 문제점을 해결하기 위해 원형 큐가 만들어졌다.


JAVA 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
import java.io.InputStream;
import java.util.Scanner;
 
public class Queue {
    
    private int front;
    private int rear;
    private int maxSize;
    private Object[] queueArray;
    
    //Queue 생성
    public Queue(int maxSize){
        this.front = 0;
        this.rear = -1;
        this.maxSize = maxSize;
        this.queueArray = new Object[maxSize];
    }
    
    //Queue 비었는지 확인
    public boolean empty(){
        return (front == rear+1);
    }
    
    //Queue 꽉 찼는지 확인
    public boolean full(){
        return (rear == maxSize-1);
    }
    
    //Queue에 item 입력
    public boolean enqueue(Object item){
        if(full()){
            System.out.println("Queue is FULL!!");
            return false;
        }
        queueArray[++rear] = item;
        return true;
    }
 
    //Queue 가장 먼저들어온 데이터 출력
    public Object dequeue(){
        if(empty()){
            System.out.println("Queue is EMPTY!!");
            return null;
        }else{
            Object item = queueArray[front];
            queueArray[front] = null;
            front++;
            return item;
        }
    }
    
    //Queue 출력
    public void printQueue(Queue queue){
        if(!empty()){
            for(int i = 0; i<maxSize; i++ ){
                if(queue.queueArray[i] == null){
                    System.out.print("|\t\t");
                }else{
                    System.out.print("|\t"+ queue.queueArray[i]+ "\t");
                }
            }
            System.out.println(" |");
        }else{
            System.out.println("큐 비어있음");
        }    
    }
    
    public static void main(String[] args) {
 
        InputStream a = System.in;
        Scanner sc = new Scanner(a);
        
        System.out.println("큐 SIZE 입력 : ");
        int size = sc.nextInt();
        Queue arrayQueue = new Queue(size); //create queue
        
        boolean flag = true;
        
        while(flag){
            menu();
            String s = sc.next();
            switch(s){
            case "1":
                System.out.print("ENQUEUE : ");
                String data = sc.next();
                arrayQueue.enqueue(data);
                break;
            case "2":
                System.out.println("DEQUEUE : " + arrayQueue.dequeue());
                break;
            case "3":
                arrayQueue.printQueue(arrayQueue);
                break;
            case "q":
            case "Q":
                flag = false;
                break;
            }
        }
    }
    public static void menu(){
        System.out.println("1. enQueue");
        System.out.println("2. deQueue");
        System.out.println("3. QUEUE");
        System.out.println("Q. 종료");
    }
}
cs


'JAVA > 알고리즘' 카테고리의 다른 글

Codility 간략 소개  (1) 2016.04.17
[JAVA] 소수 구하기 + 실행시간 단축  (1) 2015.12.10
선형 큐(Linear Queue)  (0) 2015.10.28
스택(Stack) 알고리즘(JAVA)  (0) 2015.10.27

Tags

Read Next

*

*