[자료구조] Stack과 Queue-3

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.: https://github.com/ejImDev/data_structure_study.git

큐를 배열로 구현한 ArrayQueue 만들기

ArrayQueue 클래스

public class ArrayQueue<E>{
 private E[] q;
 private int front, rear, size;
 public ArrayQueue(){
     q = (E[])new Object[2];
     front = rear = size = 0;
 }
 public int size() { return size; }
 public boolean isEmpty() { return (size == 0); }
 ...
}

구현 메소드

add (큐 삽입 메소드)

public void add(E newItem){
 if((rear+1)%q.length == front){
   resize(2*q.length);
 }
 rear = (rear+1)%q.length;
 q[rear] = newItem;
 size++;
}

remove (큐 삭제 연산)

public E remove(){
  if(isEmpty()){
      throw new NoSuchElementException();
  }
  front = (front+1)%q.length;
  E item = q[front];
  q[front] = null;
  size--;
  if(size>0 && size==q.length/4){
      resize(q.length/2);
  }
  return item;
}

resize (큐의 배열크기 조절)

public void resize(int newSize){
  Object[] t = new Object[newSize];
  for(int i=1, j=front+1; i<size+1; i++, j++){
      t[i] = q[j%q.length];
  }
  front=0;
  rear=size;
  q=(E[])t;
}

큐를 연결리스트로 구현한 ListQueue 만들기

ListQueue 클래스

public class ListQueue <E>{
 private Node<E> front,rear;
 private int size;
 public ListQueue(){
     front = rear = null;
     size = 0;
 }
 public int size() { return size; }
 public boolean isEmpty() { return (size == 0); }
 ...
}

구현 메소드

add (큐 삽입 연산)

public void add(E newItem){
 Node newNode = new Node(newItem, null);
 if(isEmpty()){
   front = newNode;
 } else {
   rear.setNext(newNode);
 }
 rear = newNode;
 size++;
}

remove (큐 삭제 연산)

public E remove(){
  if(isEmpty()){
      throw new NoSuchElementException();
  }E frontItem = front.getItem();
  front = front.getNext();
  if(isEmpty()){
      rear = null;
  }
  size--;
  return frontItem;
}

print (큐의 항목 출력)

public void print(){
  if(isEmpty()){
      System.out.print("큐가 empty임");
  } else {
      for(Node p=front; p!=null; p=p.getNext()){
          System.out.print(p.getItem()+"\t ");
      }
      System.out.println();
  }
}

A,B 정리

배열로 구현한 큐의 add와 remove 연산은 각각 O(1)시간이 소요
배열 크기를 확대 또는 축소시키는 경우에 쿠의 모든 item들을 새 배열로 복사해야하므로 O(N)시간 소요
상각분석 : 각 연산의 평균 수행시간은 O(1)
단순연결리스트로 구현한 큐의 add와 remove 연산은 각각 O(1)시간, 삽입 또는 삭제 연산이 rear과 front로 인해 연결리스트의 다른 노드들을 일일이 방문할 필요 없기 때문
배열과 단순연결리스트로 구현한 큐의 장단점은 2장의 리스트를 배열과 단순연결리스트로 구현하였을 때의 장단점과 동일

데크

양쪽 끝에서 삽입과 삭제를 허용하는 자료구조
스택과 큐 자료구조를 혼합한 자료 구조. 둘을 동시에 구현하는데 사용
ex) 스크롤, 문서 편집기 등의 undo 연산, 웹 브라우저의 방문 기록 등
이중연결리스트로 구현하는 것이 편리
수행시간
- 데크를 배열이나 이중연결리스트로 구현한 경우, 스택과 큐의 수행시간과 동일
- 양 끝에서 삽입과 삭제가 가능하므로 프로그램이 다소 복잡
- 이중연결리스트로 구현한 경우에는 더 복잡함
- 자바 SE7은 java.util 패키지에서 데크 인터페이스를 제공, Queue 클래스에서 상속됨

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/rhTFC8grZsM

IM

큐를 배열로 구현한 ArrayQueue 만들기

큐를 연결리스트로 구현한 ListQueue 만들기

A,B 정리

데크