Queue 구현

1. Queue 특징

---

• 민 앞에서 자료 꺼내거나 삭제, 맨 뒤에서 자료 추가함
• First In First Out
• jdk: ArrayList

 

 

 

2. 연결 리스트 사용 Queue구현

2.1 QueueInterface

---

• 연결 리스트로 구현 이유
  • Arrary로 구현하는 경우, Queue에서 data를 꺼내면 모든 data를 옮겨줘야 한다.
  • Linked List로 구현하면 연결만 변경해 주면 된다. 훨씬 간단함.

public interface MyQueue {

    void enQueue(String data);
    String deQueue();
    void printQueue();
}

 

2.2 MyQueue

---

public class MyLinkedQueue extends MyLinkedList implements MyQueue {

    MyListNode front;
    MyListNode rear;

    @Override
    public void enQueue(String data) {

        MyListNode newNode;
        if (isEmpty()){
            newNode = addElement(data);
            front = newNode;
            rear = newNode;
        }else {
            newNode = addElement(data);
            rear = newNode;
        }

       // System.out.println(newNode.getData() + "added");
    }

    @Override
    public String deQueue() {

        if (isEmpty()){
            throw new IllegalArgumentException("Queue is empty");
        }

        String ret = front.getData();
        removeElement(0);

        front = front.getNext();
        if(front == null){
            rear = null;
        }

        return ret;
    }

    @Override
    public void printQueue() {
        printAll();
    }


}

 

3. Test

---

class MyLinkedQueueTest {

    MyLinkedQueue myLinkedQueue;
    int cnt = 5;

    @BeforeEach
    void setUp() {

        myLinkedQueue = new MyLinkedQueue();

        for (int i = 0; i < cnt; i++){
            myLinkedQueue.enQueue(Integer.toString(i));
        }

    }

    @AfterEach
    void tearDown() {
        myLinkedQueue.clear();
    }

    @Test
    void enQueue() {
        //given

        //when
        myLinkedQueue.enQueue("A");

        //then
        assertEquals(myLinkedQueue.getCount(), cnt+1);
    }

    @Test
    void deQueue() {
        //given
        MyListNode front = myLinkedQueue.front;

        //when
        String result = myLinkedQueue.deQueue();

        //then
        assertEquals(result, Integer.toString(0));
        assertEquals(result, front.getData());
        assertEquals(cnt-1, myLinkedQueue.getCount());
    }
}

 

 

4. GitHub: 211024 Queue 구현

---

GitHub - bsh6463/dataStructure