Queue 구현해보기

Queue

• 배열을 사용해서 한번
• ListNode를 사용해서 한번

---

queue는 기본적인 자료구조의 한가지로 먼저 넣은 데이터가 먼저 나오는 선입선출 FIFO(First In First Out) 구조로 저장하는 구조이다. 영어에서 queue는 무언가를 사러 일렬로 서 있는 줄을 말한다. 후입선출에 스택과는 반대되는 개념이다.

구현

public class ArrayQueue {  
  private final int MAX_SIZE = 10;  
 private int[] data;  
 private int head;  
 private int tail;  

 public ArrayQueue() {  
  this.data = new int[MAX_SIZE];  
 this.head = 0;  
 this.tail = 0;  
  }  

  /**  
 * head의 위치가 MAX_SIZE에 이르면 호출하여 배열을 리셋  
  */  
  public void reset() {  
  for (int i = head, j = 0; i <= tail;) {  
  data[j++] = data[i++];  
  }  
  tail -= head;  
  head = 0;  
  }  

  public int[] extend() {  
  int[] newQueue = new int[data.length + MAX_SIZE];  
 for (int i = 0; i < data.length; i++) {  
  newQueue[i] = data[i];  
  }  
  return newQueue;  
  }  

  public void push(int data) {  
  if (tail + 1 == this.data.length) {  
  this.data = extend();  
  }  
  this.data[tail++] = data;  
  }  

  public int pop() {  
  if (head == tail) {  
  return -1;  
  }  
  if (head > MAX_SIZE) {  
  reset();  
  }  
  return data[head++];  
  }  

  public int size() {  
  return this.tail - this.head;  
  }  
}

테스트

class ArrayQueueTest {  

  @Test  
  void 푸시() {  
  ArrayQueue queue = new ArrayQueue();  

  queue.push(10);  
  queue.push(20);  
  queue.push(30);  
  queue.push(40);  
  queue.push(50);  

  assertEquals(5, queue.size());  
  }  

  @Test  
  void 팝() {  
  ArrayQueue queue = new ArrayQueue();  

  queue.push(10);  
  queue.push(20);  
  queue.push(30);  
  queue.push(40);  
  queue.push(50);  

  assertEquals(10, queue.pop());  
  assertEquals(20, queue.pop());  
  assertEquals(3, queue.size());  
  }  

}

참고
https://blog.naver.com/hsm622/222159930944
https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)