자바 기초 공부 일지 41. 컬렉션 프레임 워크 (4) Queue<E>

(4) Queue<E> 

 

●  Queue<E> 컬렉션 클래스를 구성하는 스택Stack과 큐Queue가 있습니다. 

 

스택Stack은 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳으로만 자료를 꺼낼 수 있습니다. 

Last in First Out

 

 큐Queue는 한 곳에서는 삽입 작업이, 한 곳에서는 삭제 작업이 양 쪽으로 이루어집니다. 삭제 연산만 수행되는 곳을 front 프론트, 삽입 연산만 이루어지는 곳을 리어 rear 라고 하며 각각의 연산작업만 수행합니다. 

큐의 리어에서 이루어지는 삽입연산을 인큐enQueue, 프론트에서 이루어지는 삭제연산을 디큐deQueue 라고 합니다. 

First in First Out

 

 덱Deque 은 구멍이 두 개 입니다. 그리고 두 개의 구멍이 모두 입구도 출구도 될 수 있으며, 

일정한 규칙에 의해 입출(in-out) 되지 않습니다. 

 

 

출처 : 윤성우의 열혈 자바 프로그래밍 공부집

 

---

 

● 큐Queue의 구현

Queue<E> 인터페이스 안에는 여러 메소드들이 들어 있습니다. 

boolean add(E e)   넣기 E remove()   꺼내기 E element()   확인하기 boolean offer(E e)   넣기, 넣을 공간이 부족하면 false 반환 E poll()   꺼내기, 꺼낼 대상 없으면 null 반환 E peek()   확인하기, 확인할 대상이 없으면 null 반환

 

---

아래는 큐의 사용 예시입니다.  

 

public static void main(String[] args) {

   Queue<String> que = new LinkedList<>(); // LinkedList<E> 인스턴스 생성!

 

LinkedList 인스턴스를 que 로써 사용하겠다는 뜻. (다형성의 특징)

(다형성 : 부모 타입의 참조 변수가 자식 타입의 인스턴스를 참조할 수 있는 것. 

부모 타입 참조 변수로 자식 인스턴스를 참조했을 때 부모 타입의 멤버 또는 자식이 오버라이딩 한 대상에 대해서만 접근할 수 있습니다.) 

★ LinkedList<E>는 List<E>와 동시에 Queue<E>를 구현하는 컬렉션 클래스입니다.

따라서 어떠한 타입의 참조변수로 참조하느냐에 따라 ‘리스트’로도 ‘큐’로도 동작합니다. 

 

인터페이스를 구현한 결과 중 하나가 LinkedList, 리스트를 구현한 것입니다.

인터페이스는 다중상속이 가능합니다.. 그러므로 LinkedList는 Queue<E>도, List<E>도 상속한 것. 

   que.offer("Box");
   que.offer("Toy");
   que.offer("Robot");

   // 무엇이 다음에 나올지 확인
   System.out.println("next: " + que.peek());

   // 첫 번째, 두 번째 인스턴스 꺼내기
   System.out.println(que.poll());
   System.out.println(que.poll());

   // 무엇이 다음에 나올지 확인
   System.out.println("next: " + que.peek());

   // 마지막 인스턴스 꺼내기
   System.out.println(que.poll());

}

---

 

 

● 스택Stack 의 구현 

상기, 맨 위에서 설명한 덱Deque을 기준으로 스택을 구현하는 것이 자바의 원칙입니다. 

덱에서 앞을 막거나, 뒤를 막는 구조로 스택의 입출 방향을 정합니다. 

 

 

그러므로 Deque<E> 인터페이스의 메소드들을 확인해보아야 하는데요. 

Deque<E> 인터페이스의 메소드들은 다음과 같습니다. 

• 앞으로 넣고, 꺼내고, 확인하기   boolean offerFirst(E e)   넣기, 공간 부족하면 false 반환   E pollFirst()   꺼내기, 꺼낼 대상 없으면 null 반환   E peekFirst()   확인하기, 확인할 대상 없으면 null 반환   void addFirst(E e)   넣기   E removeFirst()   꺼내기   E getFirst()   확인하기

• 뒤로 넣고, 꺼내고, 확인하기   boolean offerLast(E e)   넣기, 공간이 부족하면 false 반환   E pollLast()   꺼내기, 꺼낼 대상 없으면 null 반환   E peekLast()   확인하기, 확인할 대상 없으면 null 반환 void addLast(E e)   넣기   E removeLast()   꺼내기   E getLast()   확인하기

 

스택 Stack에서 주로 쓰이는 메소드들을 확인해볼게요. 

 

pop : 스택의 가장 최상위(마지막)에 위치한 데이터를 추출한 후에 스택에서 삭제합니다.
push : 스택의 가장 최상위(마지막)에 데이터를 삽입합니다.
isEmpty : 스택이 empty 상태인지 확인합니다.
clear : 스택에 저장된 모든 데이터를 삭제하고 스택을 초기화합니다.
peek : 스택의 가장 최상위(마지막)에 위치한 데이터를 추출합니다. pop 메서드와는 달리 스택에서 데이터를 삭제하지 않습니다.

 

스택의 메소드들을 바탕으로 예제 코드를 하나 확인해볼게요. 

공부 자료의 출처 : https://freestrokes.tistory.com/82

/*
 * @ TITLE Stack (배열로 구현한 스택)
 */
interface Stack{
    boolean isEmpty();
    boolean isFull();
    void push(char item);
    char pop();
    char peek();
    void clear();
}
 
public class ArrayStack implements Stack {
    
    private int top;
    private int stackSize;
    private char stackArr[];
 
    // 스택을 생성하는 생성자
    public ArrayStack(int stackSize) {
        top = -1;    // 스택 포인터 초기화
        this.stackSize = stackSize;    // 스택 사이즈 설정
        stackArr = new char[this.stackSize];    // 스택 배열 생성
    }
    
    // 스택이 비어있는 상태인지 확인
    public boolean isEmpty() {
        // 스택 포인터가 -1인 경우 데이터가 없는 상태이므로 true 아닌 경우 false를 return
        return (top == -1);
    }
    
    // 스택이 가득찬 상태인지 확인
    public boolean isFull() {
        // 스택 포인터가 스택의 마지막 인덱스와 동일한 경우 true 아닌 경우 false를 return
        return (top == this.stackSize-1);
    }
    
    // 스택에 데이터를 추가
    public void push(char item) {
        if(isFull()) {
            System.out.println("Stack is full!");
        } else {             
            stackArr[++top] = item;    // 다음 스택 포인터가 가리키는 인덱스에 데이터 추가
            System.out.println("Inserted Item : " + item);
        }
    }
    
    // 스택의 최상위(마지막) 데이터 추출 후 삭제
    public char pop() {
        if(isEmpty()) {
            System.out.println("Deleting fail! Stack is empty!");
            return 0;
        } else { 
            System.out.println("Deleted Item : " + stackArr[top]);
            return stackArr[top--];
        }                
    }
    
    // 스택의 최상위(마지막) 데이터 추출
    public char peek() {
        if(isEmpty()) {
            System.out.println("Peeking fail! Stack is empty!");
            return 0;
        } else { 
            System.out.println("Peeked Item : " + stackArr[top]);
            return stackArr[top];
        }
    }
    
    // 스택 초기화
    public void clear() {
        if(isEmpty()) {
            System.out.println("Stack is already empty!");
        } else {
            top = -1;    // 스택 포인터 초기화
            stackArr = new char[this.stackSize];    // 새로운 스택 배열 생성
            System.out.println("Stack is clear!");
        }
    }
    
    // 스택에 저장된 모든 데이터를 출력
    public void printStack() {
        if(isEmpty()) {
            System.out.println("Stack is empty!");
        } else {
            System.out.print("Stack elements : ");
            for(int i=0; i<=top; i++) {
                System.out.print(stackArr[i] + " ");
            }
            System.out.println();
        }
    }
 
    public static void main(String args[]) {
        int stackSize = 5;
        ArrayStack arrStack = new ArrayStack(stackSize);
        
        arrStack.push('A');
        arrStack.printStack();
        
        arrStack.push('B');
        arrStack.printStack();
        
        arrStack.push('C');
        arrStack.printStack();
        
        arrStack.pop();
        arrStack.printStack();
        
        arrStack.pop();
        arrStack.printStack();
        
        arrStack.peek();
        arrStack.printStack();
        
        arrStack.clear();
        arrStack.printStack();
    }
    
}

---

아래는 Stack 의 사용 예시입니다.

 

public static void main(String[] args) {
   Deque<String> deq = new ArrayDeque<>();
   
    // 다음 문장도 구성 가능
	// Deque<String> deq = new LinkedList<>();

   // 앞으로 넣고
   deq.offerFirst("1.Box");
   deq.offerFirst("2.Toy");
   deq.offerFirst("3.Robot");

   // 앞에서 꺼내기
   System.out.println(deq.pollFirst());
   System.out.println(deq.pollFirst());
   System.out.println(deq.pollFirst());
}

 

★즉, LinkedList<E>는 List<E>,  Queue<E>, Deque<E> 를 구현하는 컬렉션 클래스이며, 

동시에 List<E>,  Queue<E>, Deque<E> 는 LinkedList가 구현하는 인터페이스입니다.