Stack과 Queue

Stack<E> 클래스

• 특징
  • List 컬렉션 클래스의 Vector 클래스를 상속받아 전형적인 스택 메모리 구조의 클래스를 제공한다.
  • 후입선출 (LIFO : Last In First Out) 구조
    • 먼저 들어온 데이터가 나중에 빠져나가는 구조
  • 단방향 입출력 구조
    • 데이터의 들어오는 방향과 나가는 방향이 같다.
  • 데이터를 하나씩만 넣고 뺄 수 있다.
  • 깊이 우선 탐색(DFS)에 이용된다.
  • 재귀 함수의 동작 흐름과 같은 구조를 가진다.
  • 더욱 복잡하고 빠른 스택을 구현하고 싶다면 Deque 인터페이스를 구현한 ArrayDeque 클래스를 사용하면 된다.
• 메소드
  • empty()
    • 해당 스택이 비어 있으면 true를, 비어 있지 않으면 false를 반환한다.
  • peek()
    • 해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환한다.
  • pop()
    • 해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환하고, 해당 요소를 스택에서 제거한다.
  • push(E item)
    • 해당 스택의 제일 상단에 전달된 요소를 삽입한다.
  • search(Object o)
    • 해당 스택에서 전달된 객체가 존재하는 위치의 인덱스를 반환한다.
    • 인덱스는 제일 상단에 있는(제일 마지막으로 저장된) 요소의 위치부터 0이 아닌 1부터 시작한다.
• 사용 예시

Stack<Integer> st = new Stack<Integer>(); // 스택의 생성
//Deque<Integer> st = new ArrayDeque<Integer>();

//push() 메소드를 이용한 요소의 저장
st.push(4);
st.push(2);
st.push(3);
st.push(1);

//peek() 메소드를 이용한 요소의 반환
System.out.println(st.peek());
System.out.println(st);

//pop() 메소드를 이용한 요소의 반환 및 제거
System.out.println(st.pop());
System.out.println(st);

//search() 메소드를 이용한 요소의 위치 검색
System.out.println(st.search(4));
System.out.println(st.search(3));

//값 모두 제거
stackInt.clear();

Queue<E> 인터페이스

• Java에서 큐 메모리 구조는 별도의 인터페이스 형태로 제공된다.
• 선형 메모리 공간에 데이터를 저장한다.
• 선입선출 (FIFO : First In First Out) 구조
  • 먼저 들어온 데이터가 먼저 빠져나가는 구조
• 더욱 복잡하고 빠른 큐를 구현하고 싶다면 Deque 인터페이스를 구현한 ArrayDeque 클래스를 사용하면 된다.
• Java SE 6부터 지원되는 ArrayDeque 클래스는 스택과 큐 메모리 구조를 모두 구현하는데 가장 적합한 클래스다.
• 하위 인터페이스
  • Deque<E>
  • BlockingDeque<E>
  • BlockingQueue<E>
  • TransferQueue<E>
• 메소드
  • add(E e)
    • 해당 큐의 맨 뒤에 전달된 요소를 삽입한다.
    • 만약 삽입에 성공하면 true를 반환하고, 큐에 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생시킨다.
  • element()
    • 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환한다.
  • offer(E e)
    • 해당 큐의 맨 뒤에 전달된 요소를 삽입한다.
  • peek()
    • 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환한다.
    • 만약 큐가 비어있으면 null을 반환한다.
  • poll()
    • 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환하고, 해당 요소를 큐에서 제거한다.
    • 만약 큐가 비어있으면 null을 반환한다.
  • remove()
    • 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 제거한다.
• 사용 예시

LinkedList<String> qu = new LinkedList<String>(); // 큐의 생성
//Deque<String> qu = new ArrayDeque<String>();

//add() 메소드를 이용한 요소의 저장
qu.add("넷");
qu.add("둘");
qu.add("셋");
qu.add("하나");

//peek() 메소드를 이용한 요소의 반환
System.out.println(qu.peek());
System.out.println(qu);

//poll() 메소드를 이용한 요소의 반환 및 제거
System.out.println(qu.poll());
System.out.println(qu);

//remove() 메소드를 이용한 요소의 제거
qu.remove("하나");
System.out.println(qu);