자료구조 #7 - 큐 구현

이 포스트는 FastCampus에 이 강의를 보고 포스팅되었습니다.
문제가 될 시 삭제될 예정입니다.

시작하기 전에 큐 특징 좀 다시 알려줘바

• 맨 앞에선 자료에 탐색과 삭제, 맨 뒤에서 추가를 하는 자료구조 입니다.
• 맨 앞을 Front, 맨 뒤를 rear라고 부릅니다.
• 전에 구현했던 스택과는 다르게 FIFO( First In First Out, 선입선출 ) 구조입니다.
• 가게에 먼저 줄을 선 손님이 먼저 들어가는 것으로 예를 들 수 있습니다.
• 순차적으로 들어오는 자료를 순서대로 처리하는데 많이 사용되는 자료구조입니다.

JDK 클래스에는 ArrayList가 있습니다.

뭘 구현할건데?

enQueue, deQueue를 구현해볼겁니다.

잠깐 이거 코드 여기에만 올라옴??

전편에도 말했지만 모든 코드는 깃허브에 올라갈 예정입니다.
링크

시작하기 전

이번에 할 스택 구현은 저번에 만든 연결리스트 클래스를 가져와서 구현합니다.
히히 재밌겠ㄷ22

인터페이스 생성

public interface IQueue {
    public void enQueue(String data);
    public String deQueue();
    public void printQueue();
}

인터페이스 구현 ( 사전 준비 )

구현하기 전, MyLinkedList 부분에 비었는지를 확인하는 코드를 추가합니다.

public boolean isEmpty() {
    if (head == null) return true; // head 값이 없을때 True를 반환
    else return false; // 하나라도 있을 경우 false
}

그리고 인터페이스를 구현해보죠.
일단 front와 rear를 선언해야 합니다.

public class MyLinkedQueue extends MyLinkedList implements IQueue{

    MyListNode front; // 맨 앞부분인 front
    MyListNode rear; // 맨 뒷부분인 rear}

인터페이스 구현 ( enQueue )

@Override
public void enQueue(String data) {
    MyListNode newNode;
    if(isEmpty()) { // 만약 비었으면
        newNode = addElement(data); // newNode를 만들어서 할당하고
        front = newNode
        rear = newNode; // front와 rear 둘다 newNode로 바꿉니다.
    } else { // 하나라도 있으면
        newNode = addElement(data); // 똑같이 newNode를 만들어서 할당하고
        rear = newNode; // rear만 newNode로 바꿔줍니다.
    }
}

인터페이스 구현 ( deQueue )

@Override
public String deQueue() {
    if (isEmpty()) { // 만약 비었다면?
        return null; // 아무것도 없으므로 null을 return합니다.
    }

    String data = front.getData(); // front 자료 값을 불러옵니다.
    front = front.next; // front를 front에 링크로 바꿉니다.

    if(front == null) { // front가 null이라면?
        rear = null; // 마지막인 rear도 null로 바꿔줍니다.
    }

    return data; // data를 return 합니다.
}

인터페이스 구현 ( printQueue )

@Override
public void printQueue() {
    printAll(); // 전에 만들었던 MyLinkedList에서 불러옵니다.
}

전체 구현 코드좀 줘봐

전체 구현 코드는 여기서도 확인 가능합니다.

마치며

이렇게 해서 선형 자료구조는 모두 구현이 끝났습니다.
시간이 남으면 비선형 자료구조도 구현해보겠지만, 일단 강좌를 봐야하기에 구현편은 여기까지 하겠습니다.
그럼 다음시간에 다시 보죠!