자바 자료구조#16. Stack/Queue

Stack/Queue

• 선형 자료구조에서 출력에 규칙을 적용
  앞에서부터 꺼내기 => Queue (FIFO) => 들어간 순서대로 처리
  뒤에서부터 꺼내기 => Stack (LIFO) => 들어간 반대로 처리
• 값을 순차적으로 꺼낼 때 적합. 인덱스를 사용해서 중간의 데이터를 조회, 삽입, 제거 등의 작업을 할 때는 적합하지 않음.

---

List를 통해 Stack/Queue 기능 구현

• Queue (index의 값을 꺼내면 값이 없어지게 됨)

List<Integer> List = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);

list.remove(0); // [2, 3]
list.remove(0); // [3]
list.remove(0); // null

• Stack (index의 값을 꺼내면 값이 없어지게 됨)

List<Integer> List = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);

list.remove(0); // [1, 2]
list.remove(0); // [1]
list.remove(0); // null

---

Stack/Queue 기본함수

Queue

• Interface 로만 제공됨
• LinkedList : Queue를 implements 하는 대표적 클래스
• 값 추가 : add(e), offer(e)
• 값 꺼내기(제거) : remove(), poll()
• (맨 앞의) 값 조회 : element(), peek()
• 앞의 함수는 동작하지 못하면 Exception 발생, 뒤의 함수는 null or special value 리턴
• Queue 선언

Queue<Integer> queue = new LinkedList<>();

• Queue 값 추가 및 꺼내기, 값 확인

// 추가
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);

// 꺼내기
queue.poll(); // [2, 3, 4]
queue.poll(); // [3, 4]
queue.poll(); // [4]

// 값 확인
queue.peek(); // 4 (꺼내지는 않고 꺼낼 차례인 값 확인만)

Stack

• Stack은 Class를 직접 제공
• Vector를 상속 받음
• 값 추가 : push(e)
• 값 꺼내기(제거) : pop()
• (맨 앞의) 값 조회 : peek()
• Stack 선언

Stack<Integer> stack = new Stack<>();

• Stack 값 추가 및 꺼내기, 값 확인

// 추가
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);

// 꺼내기
stack.pop(); // [1, 2, 3]
stack.pop(); // [1, 2]
stack.pop(); // [1]

// 값 확인
stack.peek(); // 1 (꺼내지는 않고 꺼낼 차례인 값 확인만)

---

Deque

• 양방향 Queue
• 값을 앞, 뒤 양쪽에서 모두 꺼낼 때 사용 (Stack + Queue)
• Interface 로만 제공됨
• LinkedList 로 구현
• 앞 먼저 : offerFirst(e), pollFirst(), peekFirst()
• 뒤 먼저 : offerLast(e), pollLast(), peekLast()
• Queue 선언

Deque<Integer> deque = new LinkedList<>();

• Queue 값 추가 및 꺼내기, 값 확인

// 추가
deque.offerFirst(1); // [1]
deque.offerLast(2);  // [1, 2]
deque.offerFirst(3); // [3, 1, 2]
deque.offerLast(4);  // [3, 1, 2, 4]

// 3 꺼내기
deque.pollFirst(); // [1, 2, 4]

// 4 꺼내기
deque.pollLast(); // [1, 2]