ReBugs
블로그 이미지

Home

About Me
11-24 01:39
light
자료구조 & 알고리즘/자료구조

[JAVA] 큐(Queue) / 링 버퍼(Ring Buffer) / 데크(Deque)

ReBugs
|2023. 1. 29. 00:50

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다.

큐

큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조이다. 하지만 큐는 스택과 다르게 선입선출(FIFO, First In First Out)이다.

아래의 그림과 같이 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 구조로 되어 있다.

큐에 데이터를 넣는 작업을 인큐라 하고, 데이터를 꺼내는 작업을 디큐라고 한다.

 

인큐와 디큐

 

인큐

위 그림에서 리어(rear)인 53 뒤에 24를 인큐 한다.

이 처리의 시간복잡도는 O(1)이고 적은 비용으로 구현할 수 있다.

 

디큐

위 그림에서 프론트(front)인19와 22을 디큐 한다. 디큐한 후에는 모든 요소를 앞으로 옮겨야 한다.

이 처리의 시간복잡도는 O(N)이며 데이터를 꺼낼 때마다 이런 처리를 하게 되면 효율이 떨어진다.

 

구현

IntAryQueue 클래스 (int형 배열로 구현)

더보기 
public class IntAryQueue {
    private int max; //큐 용량
    private int num; //현재 데이터 수
    private int[] que;

    IntAryQueue(int capacity) //생성자
    {
        this.max = capacity;
        que = new int[max];
        num = 0;
    }

    private boolean isFull() {return num >= max;} //큐의 공간이 모두 사용중인지 리턴

    private boolean isEmpty() {return num <= 0;} //큐의 공간이 비어있는지 리턴

    public int capacity() {return max;} //큐의 용량을 리턴

    public int size() {return num;} //큐의 현재 데이터 수를 리턴

    public void enque(int value)
    {
        if(!isFull()) que[num++] = value;
        else System.out.println("큐의 공간을 모두 사용중입니다.");
    }

    public void deque()
    {
        if(!isEmpty())
        {
            for (int i = 1; i < num; ++i)
            {
                que[i-1] = que[i];
            }
            que[--num] = 0;
        }
        else System.out.println("이미 큐의 공간이 비어있습니다.");
    }

    public void peek() //큐의 front를 리턴
    {
        if(num > 0) System.out.println("front : " + que[0]);
        else System.out.println("큐의 공간이 비어있습니다.");
    }

    public void back() //큐의 rear을 리턴
    {
        if(num > 0) System.out.println("rear : " + que[num- 1]);
        else System.out.println("큐의 공간이 비어있습니다.");
    }

    public void indexOf(int value) //큐에서 찾는 데이터가 있는지 출력
    {
        for(int i = 0; i < num; ++i)
        {
            if(que[i] == value)
            {
                System.out.println("찾는 값이 있습니다. 인덱스 : " + i);
                return;
            }
        }
        System.out.println("찾는 값이 없습니다.");
    }

    public void clear() {num = 0;} //큐의 front를 초기화 시킴

    public void dump() //모든 큐의 값을 출력
    {
        if(isEmpty())
        {
            System.out.println("큐가 비어있습니다.");
            return;
        }
        for (int i = 0; i < num; ++i)
        {
            System.out.println("[" + i + "]" + "=" + que[i]);
        }
    }
}

 

실행 예제

더보기 
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("큐 용량 입력 : ");
        int command = sc.nextInt();
        IntAryQueue que = new IntAryQueue(command);
        while(true)
        {
            System.out.println();
            System.out.println("현재 데이터 수 : " + que.size() + "/" + que.capacity());
            System.out.println("(1)inqueue (2)dequeue (3)search (4)front (5)back (6)dump (7)clear (8)exit");
            System.out.print("cmd : ");
            command = sc.nextInt();
            if(command == 1)
            {
                System.out.print("value : ");
                command = sc.nextInt();
                que.enque(command);
            }
            else if(command == 2) que.deque();
            else if(command == 3)
            {
                System.out.print("Data for Search: ");
                command = sc.nextInt();
                que.indexOf(command);
            }
            else if(command == 4) que.peek();
            else if(command == 5) que.back();
            else if(command == 6) que.dump();
            else if(command == 7) que.clear();
            else if(command == 8) System.exit(0);
            else continue;
        }
    }
}

 

링 버퍼(Ring Buffer)

일반 큐는 디큐를 하고나서 모든 배열의 요소를 맨 앞으로 옮기는 작업을 해야 했다.

그래서 시간복잡도가 증가하였다.

링 버퍼 큐는 배열의 요소를 앞쪽으로 옮기지 않는 큐이다.

링 버퍼 큐는 배열의 처음과 끝이 연결되었다고 보는 자료구조이다.

여기서 논리적으로 어떤 요소가 첫 번째 요소이고 어떤 요소가 마지막 요소인지 식별하기 위한 변수가 front와 rear이다.

  • front : 맨 처음 요소의 인덱스
  • rear : 맨 끝 요소의 하나 뒤의 인덱스(다음 요소를 인큐 할 위치를 미리 지정)
  • front와 rear는 논리적인 데이터 순서를 말한다. 배열의 물리적 요소의 순서가 아니다.

 

인큐, 디큐, 검색

인큐

인큐를 할 때, 데이터는 que[rear]에 저장된다. 즉, 데이터는 rear에 저장된다.

만약 rear가 배열의 공간과 같다면(배열의 최대 인덱스보다 크다면), rear를 배열의 가장 작은 인덱스로 바꿔줘야 한다.

que[rear++] = value;
++num;
if(rear == max) rear = 0;

디큐

디큐를 할 때, que[front]의 데이터가 삭제된다.

만약 front가 배열의 공간과 같다면(배열의 최대 인덱스보다 크다면), front를 배열의 가장 작은 인덱스로 바꿔줘야 한다.

que[front++] = 0;
--num;
if(front == max) front = 0;

검색

for(int i = 0; i < num; ++i)
{
    int index = (i + front) % max;
    if(que[index] == value)
    {
        System.out.println(value + "는 큐의 " + (i+1) + "번째 데이터이고, 배열의 " + index + "인덱스에 있습니다.");
        return;
    }
}
System.out.println("찾는 값이 없습니다.");

front가 6이고, 배열의 길이가 12라면 i와 index는 아래와 같다.

  • i : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6
  • index : 7 -> 8 -> 9 -> 10 -> 11 -> 0 -> 1

 

구현

int형 배열을 이용한 IntQueue 클래스

더보기 
public class IntQueue {
	private int max; //큐 용량
	private int num; //현재 데이터 수
	private int front; //디큐를 할 인덱스를 가리킴
	private int rear; //인큐를 할 인덱스를 가리킴
	private int[] que;
	
	IntQueue(int capacity) //생성자
	{
		this.max = capacity;
		num = front = rear = 0;
		que = new int[max];
	}
	
	private boolean isEmpty() {return num <= 0;} //큐가 비어있는지를 리턴
	
	private boolean isFull() {return num >= max;} //큐의 공간이 모두 사용중인지 리턴
	
	public int capacity() {return max;} //큐의 용량을 리턴
	
	public int size() {return num;} //큐가 현재 사용중인 공간을 리턴
	
	public void clear() {num = front = rear = 0;} //큐 초기화
	
	public void enque(int value)
	{
		if(!isFull())
		{
			que[rear++] = value;
			++num;
			if(rear == max) rear = 0;
			return;
		}
		else
		{
			System.out.println("큐의 모든 공간이 사용중입니다.");
			return;
		}
	}
	
	public void deque()
	{
		if(!isEmpty())
		{
			que[front++] = 0;
			--num;
			if(front == max) front = 0;
			return;
		}
		else
		{
			System.out.println("이미 큐가 비어있습니다.");
			return;
		}
	}
	
	public void peek() //front를 출력
	{
		if(!isEmpty()) System.out.println(que[front]);
		else System.out.println("큐가 비어있습니다.");
	}
	
	public void indexOf(int value) //값이 배열에 존재하는지와 몇 번째 데이터인지, 배열의 몇 번째 인덱스인지 출력
	{
		for(int i = 0; i < num; ++i)
		{
			int index = (i + front) % max;
			if(que[index] == value)
			{
				System.out.println(value + "는 큐의 " + (i+1) + "번째 데이터이고, 배열의 " + index + "인덱스에 있습니다.");
				return;
			}
		}
		System.out.println("찾는 값이 없습니다.");
	}
	
	public void dump() //큐에 저장중인 모든 데이터 출력
	{
		if(!isEmpty())
		{
			for(int i = 0; i < num; ++i)System.out.println(i+1 + "번째 데이터 : " + que[(i + front) % max]);
		}
		else System.out.println("큐가 비어있습니다.");
	}
}

 

실행 예제

더보기 
import java.util.Scanner;
public class Main2{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("큐 용량 입력 : ");
		int command = sc.nextInt();
		IntQueue que = new IntQueue(command);
		while(true)
		{
			System.out.println();
			System.out.println("현재 데이터 수 : " + que.size() + "/" + que.capacity());
			System.out.println("(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit");
			System.out.print("cmd : ");
			command = sc.nextInt();
			if(command == 1)
			{
				System.out.print("value : ");
				command = sc.nextInt();
				que.enque(command);
			}
			else if(command == 2) que.deque();
			else if(command == 3)
			{
				System.out.print("Data for Search: ");
				command = sc.nextInt();
				que.indexOf(command);
			}
			else if(command == 4) que.peek();
			else if(command == 5) que.dump();
			else if(command == 6) que.clear();
			else if(command == 7) System.exit(0);
			else continue;
		}
	}
}
/*
큐 용량 입력 : 5

현재 데이터 수 : 0/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 1

현재 데이터 수 : 1/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 2

현재 데이터 수 : 2/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 3

현재 데이터 수 : 3/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 4

현재 데이터 수 : 4/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 5

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 4/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 3/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 6

현재 데이터 수 : 4/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 7

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 5
1번째 데이터 : 3
2번째 데이터 : 4
3번째 데이터 : 5
4번째 데이터 : 6
5번째 데이터 : 7

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 3
Data for Search: 5
5는 큐의 3번째 데이터이고, 배열의 4인덱스에 있습니다.

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 4/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 3/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 2/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 8

현재 데이터 수 : 3/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 9

현재 데이터 수 : 4/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 10

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 5
1번째 데이터 : 6
2번째 데이터 : 7
3번째 데이터 : 8
4번째 데이터 : 9
5번째 데이터 : 10

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 22

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 4/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 3/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 2/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 1/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 0/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2
이미 큐가 비어있습니다.
*/

링 버퍼의 활용

링 버퍼는 오래된 데이터를 버리는 용도로 사용할 수 있다.

예를 들면 요소의 개수가 n개인 배열에서 계속해서 데이터가 입력될 때 가장 최근에 들어온 데이터 n개만 저장하고 오래된 데이터는 버리는 용도로 사용한다.

예제
아래의 예제는 배열 a의 길이는 10이다. 인큐는 무한히 할 수 있지만, 배열에 저장되는 데이터는 가장 최근에 입력한 10개의 데이터만 링 버퍼에 남아있다.
import java.util.Scanner;
// 원하는 개수만큼 값을 입력 받아 요솟수 N인 배열에 마지막 N개를 저장

class LastNElements {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		final int N = 10;
		int[] a = new int[N];		// 입력 받은 값을 저장
		int cnt = 0;				// 입력 받은 개수
		int retry;					// 다시 한 번?

		System.out.println("정수를 입력하세요.");

		do {
			System.out.printf("%d번째 정수：", cnt + 1);
			a[cnt++ % N] = stdIn.nextInt();

			System.out.print("계속 할까요? (예.1／아니오.0）：");
			retry = stdIn.nextInt();
		} while (retry == 1);

		int i = cnt - N;
		if (i < 0) i = 0;

		for ( ; i < cnt; i++)
			System.out.printf("%2d번째의 정수 ＝ %d\n", i + 1, a[i % N]);
	}
}​

 

데크(deque)

deque(Double Ended Queue)는 인큐와 디큐가 배열의 양쪽 끝에서 모두 발생할 수 있는 자료구조이다.

즉, 큐의 양끝이 front이면서, rear인 형태인 것이다.

이러한 특성 때문에 데이터의 삽입과 삭제의 자유도가 높다.

Stack과 Queue의 장점만 모아서 구성한 자료구조이다.

 

int형 배열을 이용한 IntDeque 클래스

더보기 
public class IntDeque {
	private int max; //큐 용량
	private int num; //현재 데이터 수
	private int front; //디큐를 할 인덱스를 가리킴
	private int rear; //인큐를 할 인덱스를 가리킴
	private int[] que;
	
	IntDeque(int capacity) //생성자
	{
		this.max = capacity;
		num = front = rear = 0;
		que = new int[max];
	}
	
	private boolean isEmpty() {return num <= 0;} //큐가 비어있는지를 리턴
	
	private boolean isFull() {return num >= max;} //큐의 공간이 모두 사용중인지 리턴
	
	public int capacity() {return max;} //큐의 용량을 리턴
	
	public int size() {return num;} //큐가 현재 사용중인 공간을 리턴
	
	public void clear() {num = front = rear = 0;} //큐 초기화
	
	public void enque(int value)
	{
		if(!isFull())
		{
			que[rear++] = value;
			++num;
			if(rear == max) rear = 0;
		}
		else
		{
			System.out.println("큐의 모든 공간이 사용중입니다.");
		}
		return;
	}
	
	public void enqueFront(int value)
	{
		if(!isFull())
		{
			if(--front < 0) front = max -1;
			que[front] = value;
			++num;
			if(rear == max) rear = 0;
		}
		else
		{
			System.out.println("큐의 모든 공간이 사용중입니다.");
		}
		return;
	}
	
	public void deque()
	{
		if(!isEmpty())
		{
			que[front++] = 0;
			--num;
			if(front == max) front = 0;
			return;
		}
		else
		{
			System.out.println("이미 큐가 비어있습니다.");
			return;
		}
	}
	
	public void dequeRear()
	{
		if(!isEmpty())
		{
			if(--rear < 0) rear = max -1;
			que[rear] = 0;
			--num;
			return;
		}
		else
		{
			System.out.println("이미 큐가 비어있습니다.");
			return;
		}
	}
	
	public void peek() //front를 출력
	{
		if(!isEmpty()) System.out.println(que[front]);
		else System.out.println("큐가 비어있습니다.");
	}
	
	public void peekRear() //front를 출력
	{
		if(!isEmpty())
		{
			if(rear == 0) System.out.println(que[max -1]);
			else System.out.println(que[rear -1]);
		}
		else System.out.println("큐가 비어있습니다.");
	}
	
	public void indexOf(int value) //값이 배열에 존재하는지와 몇 번째 데이터인지, 배열의 몇 번째 인덱스인지 출력
	{
		for(int i = 0; i < num; ++i)
		{
			int index = (i + front) % max;
			if(que[index] == value)
			{
				System.out.println(value + "는 큐의 " + (i+1) + "번째 데이터이고, 배열의 " + index + "인덱스에 있습니다.");
				return;
			}
		}
		System.out.println("찾는 값이 없습니다.");
	}
	
	public void dump() //큐에 저장중인 모든 데이터 출력
	{
		if(!isEmpty())
		{
			for(int i = 0; i < num; ++i)System.out.println(i+1 + "번째 데이터 : " + que[(i + front) % max]);
		}
		else System.out.println("큐가 비어있습니다.");
	}
}

 

실행 예제

더보기 
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("큐 용량 입력 : ");
		int command = sc.nextInt();
		IntDeque que = new IntDeque(command);
		while(true)
		{
			System.out.println();
			System.out.println("현재 데이터 수 : " + que.size() + "/" + que.capacity());
			System.out.println("(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit");
			System.out.print("cmd : ");
			command = sc.nextInt();
			if(command == 1)
			{
				System.out.print("value : ");
				command = sc.nextInt();
				que.enque(command);
			}
			else if(command ==2)
			{
				System.out.print("value : ");
				command = sc.nextInt();
				que.enqueFront(command);
			}
			else if(command == 3) que.deque();
			else if(command == 4) que.dequeRear();
			else if(command == 5)
			{
				System.out.print("Data for Search: ");
				command = sc.nextInt();
				que.indexOf(command);
			}
			else if(command == 6) que.peek();
			else if(command == 7) que.peekRear();
			else if(command == 8) que.dump();
			else if(command == 9) que.clear();
			else if(command == 10) System.exit(0);
			else continue;
		}
	}
}
/*
큐 용량 입력 : 5

현재 데이터 수 : 0/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 1
value : 1

현재 데이터 수 : 1/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 1
value : 2

현재 데이터 수 : 2/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 1
value : 3

현재 데이터 수 : 3/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 2
value : 5

현재 데이터 수 : 4/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 2
value : 4

현재 데이터 수 : 5/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 8
1번째 데이터 : 4
2번째 데이터 : 5
3번째 데이터 : 1
4번째 데이터 : 2
5번째 데이터 : 3

현재 데이터 수 : 5/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 5
Data for Search: 3
3는 큐의 5번째 데이터이고, 배열의 2인덱스에 있습니다.

현재 데이터 수 : 5/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 4

현재 데이터 수 : 4/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 4

현재 데이터 수 : 3/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 8
1번째 데이터 : 4
2번째 데이터 : 5
3번째 데이터 : 1
 */
저작자표시 비영리 변경금지

'자료구조 & 알고리즘 > 자료구조' 카테고리의 다른 글

[자료구조] 해시 테이블  (0) 2023.09.05
[자료구조] 배열과 배열 기반의 집합  (1) 2023.08.09
[JAVA] 스택(Stack)  (0) 2023.01.28
[JAVA] 클래스 배열  (0) 2023.01.25
[Python] Single Linked List(단일 링크드 리스트)  (0) 2022.12.09

티스토리툴바