[JAVA]Queue와 LinkedList

 

Queue
: FIFO (First In First Out)
먼저 저장한 것을 먼저 꺼낸다.

 

Queue는 인터페이스라서 구현타입으로 적을 수 없습니다.

 

Queue의 구현클래스 중 대표적인 LinkedList로 적을 수 있습니다.

 

• 은행 창구의 차례 대기열 등에서 사용됩니다.
  
  
• 데이터를 넣는 작업은 인큐 enqueue 라 하고, 데이터를 꺼내는 작업을 디큐 dequeue 라 합니다.
  
  
• 데이터를 꺼내는 쪽을 프런트 front , 데이터를 넣는 쪽을 리어 rear 라 합니다.
  
  
• 배열로 queue를 만든 코드(참고용, 실제로 Queue라는 데이터타입이 있으므로)

  import java.util.Arrays;
  
  public class IntAryQueue {
      private int max;    //queue size
      private int num;    //number of elements
      private int[] que;  //que array
  
      // Exception: Queue is empty
      public class EmptyQueueException extends RuntimeException {
          public EmptyQueueException() { }
      }
  
      // Exception: Queue is full
      public class overflowQueueException extends RuntimeException {
          public overflowQueueException() { }
      }
  
      public IntAryQueue() { }
  
      public IntAryQueue(int capacity) {
          num = 0;
          max = capacity;
          try {
              que = new int[max];
          } 
          catch (OutOfMemoryError e) {
              max = 0;
          }
      }
  
      public int enque(int x) throws overflowQueueException{
          if (num >= max) {
              throw new overflowQueueException();
          }
          return que[num++] = x;
      }
  
      public int deque() throws EmptyQueueException {
          if (num <= 0) {
              throw new EmptyQueueException();
          }
          int dequeued = que[0];
          que = Arrays.copyOfRange(que, 1, max);
          num--;
          return dequeued;
      }
  
      public int peek() throws EmptyQueueException {
          if (num <= 0) {
              throw new EmptyQueueException();
          }
          return que[max];
      }
  
      public int indexOf(int x) {
          for (int i = num - 1; i >= 0; i--) {    // Search from top
              if (que[i] == x) {
                  return i;
              }
          }
          return -1;                              // x not found
      }
      
      public void clear() {
          num = 0;
      }
      
      public int capacity() {
          return max;
      }
  
      public int size() {
          return num;
      }
      
      public boolean isEmpty() {
          return num <= 0;
      }
      
      public boolean isFull() {
          return num >= max;
      }
  
      public void dump() {
          if (num <= 0) {
              System.out.println("Stack is empty.");
          } 
          else {
              for (int i = 0; i < num; i++) {
                  System.out.print(que[i] + " ");
              }
              System.out.println();
          }
      }
      
  }

 

---

 

LinkedList

 

LinkedList의 코드. 그냥 참고만 하세요.

 

• 데이터들을 Node라는 곳에 담아 하나씩 기차처럼 연결한다.
  → 노의의 위치를 연결된 양 옆의 노드들만 안다.
  
  
• 데이터를 삭제할 때 배열처럼 덮어씌우는 게 아니라 연결만 바꾼다.
  
  
• 추가할 때도 새로운 노드를 만들어 연결만 해주면 된다.
  
  

※ 장점 : 새로운 데이터 추가/삭제가 빠르다.
※ 단점 : 접근성. 데이터를 가져오는 속도가 느리다.

따라서 중간에 값을 추가/삭제할 경우에는 LinkedList가 좋다. 그렇지 않은 경우 ArrayList가 좋다.

 

---

 

사용법은 ArrayList와 거의 일치합니다.

 

**First나 **Last 같음 메서드들이 있고 자주사용된다는 차이 정도..

 

ArrayList 메서드

2024.11.19 - [☕ 자바 JAVA/☕ 변수와 자료형 Variables & Data Type] - [JAVA]ArraList

 

---

참조영상