큐 (Queue)

선입선출(First in first out) - 큐

후입선출(Last in First out) - 스택

 

배열 큐 객체의 구조

필드

- queue[] - 큐의 원소들이 저장되는 배열

- numItems - 큐의 총 원소 수 저장

- front - 큐의 맨 앞 원소의 인덱스

- tail - 큐의 맨 뒤 원소의 인덱스

 

매소드

- enqueue(x) - 큐의 끝에 원소 x를 삽입한다. 

- dequeue() - 큐의 맨 앞에 있는 원소를 알려주고 삭제한다. 

- front() - 큐의 맨 앞에 있는 원소를 알려준다.

- isEmpty() - 큐가 비어 있는지 알려준다. 

- dequeueALL() - 큐를 깨끗이 청소한다. 

 

tail이 할당받은 배열 공간의 맨 끝에 오면 큐가 꽉 찬 상태라 여김 -> 공간의 비효율 생김

-> 배열을 원형으로 해석함으로 해결가능

 

나머지로 해석

tail <- (tail+1)%queue.length

front <-(tail+1)%queue.length

 

연결 리스트 큐의 구조

필드

- tail - 큐의 맨 뒤 원소의 인덱스

 

매소드

- enqueue(x) - 큐의 끝에 원소 x를 삽입한다. 

- dequeue() - 큐의 맨 앞에 있는 원소를 알려주고 삭제한다. 

- front() - 큐의 맨 앞에 있는 원소를 알려준다.

- isEmpty() - 큐가 비어 있는지 알려준다. 

- dequeueALL() - 큐를 깨끗이 청소한다. 

 

연결 리스트 큐의 구조 또한 원형으로 이루어져 있다 tail 이 가르키는 다음 노드가 front를 가르키고 있다. 

 

원소 삽입의 경우 -> tail 이 newnode를 가르키게 되며 그 노드가 front를 가르키게 된다. 

 

원소 삭제의 경우 -> tail 이 가르키는 노드가 front 노드 다음 노드를 가르키게 한다. 

 

클래스 LinkedList 상속

 

public class InheritedQueue<E> extends LinkedList<E>

  implements QueueInterface<E> {....

 

public InheritedQueue<> {

  super();

} 

 

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // LinkedList 선언
        LinkedList<String> list = new LinkedList<>();
        
        // 데이터 추가 (맨 뒤에 추가)
        list.add("A");
        list.add("B");
        list.add("C");
        
        // 리스트 출력
        System.out.println(list);  // 출력: [A, B, C]
        
        // 첫 번째에 데이터 추가
        list.addFirst("Start");
        
        // 마지막에 데이터 추가
        list.addLast("End");
        
        // 리스트 출력
        System.out.println(list);  // 출력: [Start, A, B, C, End]
        
        // 데이터 삭제
        list.remove(2);  // 인덱스 2의 요소(B) 삭제
        System.out.println(list);  // 출력: [Start, A, C, End]
        
        // 첫 번째 요소 가져오기
        System.out.println(list.getFirst());  // 출력: Start
        
        // 마지막 요소 가져오기
        System.out.println(list.getLast());  // 출력: End
    }
}

 

큐 응용: 좌우동형 문자열 체크

package queue;
import stack.LinkedStack;

public class Palindrom {
	private static boolean isPalindrom(String A) {
    	LinkedStack s = new LinkedStack();
        LinkedQueue q = new LinkedQueue();
        for(int i=0; i < A.length(); i++) {
        	s.push(A.charAt(i));
            q.enqueue(A.charAt(i));
        }
        while(!s.isEmpty() && s.pop() == q.dequeue()) {
        }
        if(s.isEmpty()) return true;
        else return false;
    }
    
    public static void main(String[] args) {
    	System.out.println("Palindrom Check!");
        String str = "lioninoil";
        boolean t = isPalindrom(str);
        System.out.println(str + " is Palindrom?: " + t);
    }
}