๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
๐ŸŽ› Others.../- ์‹ค์ „ ๋ฌธ์ œ ํ’€์ด : PS

[์•Œ๊ณ ๋ฆฌ์ฆ˜-PS] Java ์—์„œ ํ๋ฅผ ๊ตฌํ˜„ํ•˜๋Š” ๋ฐฉ๋ฒ•

by Wonit 2020. 2. 16.

Queue๋ž€

Stack ์ž๋ฃŒ๊ตฌ์กฐ์™€ ๋‹ค๋ฅด๊ฒŒ FIFO(First In First Out) ๋ฐฉ์‹์˜ ์„ ์ž… ์„ ์ถœ ๊ตฌ์กฐ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ์ž๋ฃŒ ๊ตฌ์กฐ์ด๋‹ค.

ํ๋Š” ์ตœ๊ทผ ์‚ฌ์šฉ ๋ฌธ์„œ, ์ธ์‡„์ž‘์—… ๋Œ€๊ธฐ ๋ชฉ๋ก, ๋ฒ„ํผ ๋“ฑ์˜ ๋ถ„์•ผ์—์„œ ์‚ฌ์šฉ๋˜๋ฉฐ ์Šคํƒ์€ ์œ„์—๋งŒ ๋šค๋ ค ์žˆ์–ด ์ž๋ฃŒ๊ฐ€ ํ•œ ๋ฐฉ์–‘์œผ๋กœ๋งŒ ํ๋ฅธ๋‹ค๋ฉด ํ๋Š” ์–‘ ๋ฐฉํ–ฅ์œผ๋กœ ๋šค๋ ค ํŒŒ์ดํ”„ ๊ฐ™์€ ๋ชจ์–‘์œผ๋กœ ์ž๋ฃŒ๊ฐ€ ํ๋ฅธ๋‹ค.

ํ์˜ ์›๋ฆฌ

ํ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด front์™€ rear๋กœ ๋ฐ์ดํ„ฐ์˜ ์ถ”๊ฐ€ ๋ฐ ์‚ญ์ œ์˜ ๊ฒฝ๊ณ„๋ฅผ ์•Œ๋ฆฐ๋‹ค.

ํ์— ๋ฐ์ดํ„ฐ ์ถ”๊ฐ€ํ•˜๊ธฐ

๋งŒ์•ฝ ํ๊ฐ€ ๋น„์–ด์žˆ๋‹ค๋ฉด front ์™€ rear์€ ๊ฐ™์€ ๊ณณ์„ ํ–ฅํ•˜๊ฒŒ ๋  ๊ฒƒ์ด๊ณ  20 ๊ณผ 30 ์ด๋ž€ ๋ฐ์ดํ„ฐ๋ฅผ ์ถ”๊ฐ€ํ•œ๋‹ค๋ฉด ์–ด๋–ป๊ฒŒ ๋ณ€ํ•˜๋Š”์ง€ ๋ด๋ณด์ž.

front์™€ rear์˜ ํฌ์ธํ„ฐ๊ฐ€ ๋‹ฌ๋ผ์กŒ๋Š”๋ฐ ์ด๋Ÿฐ ์‹์œผ๋กœ ์ถ”๊ฐ€๋ฅผ ํ•œ๋‹ค๋ฉด rear += 1์œผ๋กœ rear์˜ ์œ„์น˜๊ฐ€ ๋ณ€๊ฒฝ๋˜๋ฉฐ rear์— ์— ํ•ด๋‹น๋˜๋Š” ์ธ๋ฑ์Šค์— ๊ฐ’์ด ์ถ”๊ฐ€๋  ๊ฒƒ์ด๋‹ค.

ํ์— ๋ฐ์ดํ„ฐ ์ถ”์ถœํ•˜๊ธฐ

๊ทธ๋Ÿผ ํ˜„์žฌ์™€ ๊ฐ™์€ ์ƒํƒœ์—์„œ ๋ฐ์ดํ„ฐ๋ฅผ ์ถ”์ถœํ•  ๋•Œ๋Š” front์˜ ํฌ์ธํ„ฐ๊ฐ€ ํ•œ ์นธ ๋’ค๋กœ ์ด๋™ํ•˜๊ฒŒ ๋˜๋ฉฐ ํ•ด๋‹น ์ธ๋ฑ์Šค์˜ ๊ฐ’์„ ์ถ”์ถœํ•œ๋‹ค.


๊ฐ’์˜ ์ถ”๊ฐ€ ๋ฐ ์‚ญ์ œ๊ฐ€ ์ด๋ฃจ์–ด์ง„๋‹ค๋ฉด ๊ฐ€๋ณ€์ ์ธ front์™€ rear๋กœ ์ธํ•œ ๋ฐฐ์—ด์˜ ๊ณ ์ •์  ๊ธธ์ด๋ฅผ ๋ฒ—์–ด๋‚˜๋Š” ๊ฒฐ๊ณผ๊ฐ€ ๋ฐœ์ƒํ•˜๋ฏ€๋กœ ArrayList๋กœ ๊ตฌํ˜„์„ ํ•ด์•ผ ํ•œ๋‹ค๋ฉด ๋ฐ์ดํ„ฐ๋ฅผ ๊บผ๋‚ผ ๋•Œ ์ƒ๊ธฐ๋Š” Front์˜ ๊ณต๋ฐฑ์„ ๋งค์šฐ๊ธฐ ์œ„ํ•ด Front ์ดํ›„์˜ ๋ฐ์ดํ„ฐ๋ฅผ ๋ชจ๋‘ ์•ž์œผ๋กœ ํ•œ ์นธ์”ฉ ์•ž๋‹น๊ธฐ๋Š” ๊ณผ์ •์„ ๊ฑฐ์ณ์•ผ ํ•œ๋‹ค.

ArrayList์˜ ๊ตฌํ˜„

class IntQueue{

    private int front;
    private int rear;
    private int max;
    private int[] queue;

    public IntQueue(int capacity){
        max = capacity;
        rear = -1;
        front = 0;
        queue = new int[max];
    }
    boolean empty(){
        return (front == (rear+1));
    }

    boolean full(){
        return (rear >= max-1);
    }

    // rear๋กœ ๋ฐ์ดํ„ฐ๋ฅผ ์ถ”๊ฐ€
    void add(int x){
        if(full()) throw new ArrayIndexOutOfBoundsException();
        queue[++rear] = x;
    }
    // front๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ๋บผ ๋•Œ๋งŒ ์‚ฌ์šฉ
    int remove(){
        if (empty()) throw new ArrayIndexOutOfBoundsException();
        return queue[front++];
    }

    int peek(){
        return queue[front];
    }

}

LinkedList์˜ ๊ตฌํ˜„

์ˆ˜์ •์ค‘..

๋Œ“๊ธ€