자료구조 - Stack vs Queue || Shallow/Deep Copy

	Stack	Queue
특징	- First In Last Out : FILO  - Last In First Out : LIFO  - 마지막에 들어온 것을 먼저 처리	- First In First Out : FIFO  - Last In Last Out : LILO  - 먼저 들어온 것은 먼저 처리
응용	- 웹 브라우저 방문 내역  - 브레드 크럼 (bread Crumb)  - 인터럽트 처리  - 수식 계산  - 서브루틴 복귀 번지 저장  - 부프로그램(sub p/g) 호출 + 함수호출 순서 제어	- 메신저  - 예매 사이트  - 운영 체제 작업 스케줄링  - 키보드 버퍼 이용 시  - 스풀 이용 시

 

---

Stack

public class Stack<E> implements Cloneable {
  
  /* field */
  
  private static final int DEFAULT_CAPACITY = 10;
  Object[] elementData;
  int size;

  /* constructor */
  
  public Stack() {
    this.elementData = new Object[DEFAULT_CAPACITY];
    this.size = 0;
  }
  
  /* add */

  public void push(E value) {
    if (this.size == elementData.length) {
      grow();
    }
    this.elementData[size++] = value;
  }
  
  /* get */

  @SuppressWarnings("unchecked")
  public E pop() {
    if (this.empty()) 
      return null;
    E value = (E) this.elementData[--this.size];
    this.elementData[this.size] = null;
    return value;
  }

  private void grow() {
    this.elementData = Arrays.copyOf(this.elementData, newCapacity());
  }

  private int newCapacity() {
    int oldCapacity = elementData.length;
    return oldCapacity + (oldCapacity >> 1);
  }

  public boolean empty() {
    return this.size == 0;
  }
  
  @SuppressWarnings("unchecked")
  @Override
  public Stack<E> clone() {
    try {
    
      Stack<E> temp = (Stack<E>)super.clone();
      Object[] arr = new Object[this.size];
      for(int i = 0 ; i < this.size ; i++) {
        arr[i] = this.elementData[i];
      }
      temp.elementData = arr;
      return (Stack<E>)temp;
      
    } catch (CloneNotSupportedException e) {
      System.out.println(e);
      return null;
    }
    
  }
}

---

Queue

public class Queue<E> extends LinkedList<Object> implements Cloneable{

  /* add */
  
  public void offer(E value) {
    this.add(value); //
  }

  /* get */
  
  @SuppressWarnings("unchecked")
  public E poll() {
    return (E) this.remove(0);
  }
 
  /* clone overriding */
  
  @Override
  public Queue<E> clone() {
    Queue<E> temp = new Queue();
    for (int i = 0 ; i < this.size() ; i++) {
      temp.offer((E) this.get(i));
    }
    return temp;
  }

---

Shallow Copy (얕은 복사)

• 참조에 의한 복사
• 원본이나 복사된 것 중에 하나라도 변경되면 연쇄적으로 변경된다
• Object의 clone은 얕은 복사

/* Stack */
  @Override
  public Stack clone() {
    return (Stack)super.clone();
  }
  
  

  /* Queue */
  @Override
  public Queue clone() {
    return (Queue)super.clone();
  }

Deep Copy (깊은 복사)

• 새로운 객체를 만들어 값은 같지만 다른 참조를 가지는 완전한 복사

/* Stack : Array의 깊은 복사 */
  
  public Stack<E> clone() {
    Stack<E> temp = (Stack<E>)super.clone(); // shallow copy : 인스턴스 변수 복제
    Object[] arr = new Object[this.size]; // elementData 배열 복제 -> 배열에 저장된 객체는 복제 X
    
    for(int i = 0 ; i < this.size ; i++) { // 복제한 인스턴스 변수가 새로 만든 배열 가리키도록 함
      arr[i] = this.elementData[i];
    }
    
    temp.elementData = arr;
    return (Stack<E>)temp;
  }
  
  
  
  /* Queue : LinkedList의 깊은 복사 */
  
  public Queue<E> clone() {
    Queue<E> temp = new Queue();
    for (int i = 0 ; i < this.size() ; i++) {
      temp.offer((E) this.get(i));
    }
    return temp;
  }