자료구조 - 큐(Queue)의 정의와 예제

• 자료구조(Data Structure)란?
  • 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다.
• 그 중 스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성된다.
  • 삽입(Push): 데이터를 삽입한다.
  • 삭제(Pop): 데이터를 삭제한다.
• 오버플로(Overflow)와 언더플로(Underflow)
  • 오버플로(Overflow)는 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생한다. ⇒ 저장 공간을 벗어나 데이터가 넘쳐흐를 때 발생한다.
  • 언더플로(Underflow)는 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 발생한다.
• 큐(Queue)
  • 놀이공원의 대기 줄처럼 먼저 들어 온 데이터가 먼저 나가는 형식의 자료구조이다.
  • 입구와 출구가 모두 뚫려 있는 터널과 같은 형태.
  • 선입선출(First In First Out)구조라고 한다.

 

• 큐 예제
  • 큐에서 오버플로/언더플로가 발생하면 예외를 던지는 연산
    • add(A): 큐에 A를 넣는다.
    • remove(): 맨 처음에 들어간 데이터를 제거한다.
    • element(): 큐에서 가장 앞에 있는 것을 반환한다.
  • 큐에서 오버플로/언더플로가 발생하면 null 또는 false를 반환하는 연산 
    • offer(A): 큐에 A를 넣는다.
    • poll(): 맨 처음에 들어간 데이터를 제거한다.
    • peek(): 큐에서 가장 앞에 있는 데이터를 반환한다.
    • isempty(): 큐가 비어있으면 true, 아니면 false를 반환한다.

import java.util.LinkedList;
import java.util.Queue;

public class ex5_2 {
//큐 예제
	public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();

        // 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
        q.offer(5);
        q.offer(2);
        q.offer(3);
        q.offer(7);
        q.poll();
        q.offer(1);
        q.offer(4);
        q.poll();
        // 먼저 들어온 원소부터 추출
        while (!q.isEmpty()) {
            System.out.println(q.poll());
        }
    }
}

 

자료구조 - 스택(Stack)의 정의와 예제