[section 2] 자료구조(2) - 스택, 큐

스택 Stack

LIFO: Last In First Out
후입선출 데이터 구조

특징

1. 후입선출 구조
2. 하나의 입출력 방향

연산

• push(data) : data 삽입
• pop() : 스택의 마지막 요소 제거 / 반환
• size() : 스택의 사이즈
• peek() : 스택의 마지막 요소 보기
• show() : 스택 보기
• clear() : 스택의 모든 요소 삭제

stack 클래스

import java.util.Stack;

Stack<Integer> stack = new Stack<>();
stack.push(1);	// stack: 1
stack.push(2);	// stack: 1 2
stack.push(3);	// stack: 1 2 3
stack.pop();	// stack: 1 2
stack.clear();	// stack: (비어있음)

---

큐 Queue

FIFO: First In First Out
선입선출 데이터 구조

특징

1. 선입선출 구조

2. 두 개의 입출력 방향

   • front: 삭제 연산
   • rear: 삽입 연산

3. 컴퓨터의 buffer

연산

• enqueue(data) : 큐의 rear에 data 삽입
• dequeue() : 큐의 front 요소 삭제
• size() : 큐의 사이즈
• peek() : 큐의 front 요소 보기
• show() : 큐 보기
• clear() : 큐의 모든 요소 삭제

queue 클래스

import java.util.LinkedList;
import java.util.Queue;

Queue<Integer> queue = new LinkedList<>();
queue.add(1);	// queue: 1
queue.add(2);	// queue: 1 2
queue.add(3);	// queue: 1 2 3
queue.poll();	// queue: 2 3
queue.clear();	// queue: (비어있음)

원형 큐와 덱

원형 큐 : 원 모양의 큐
(circular queue)

원형 큐 특징

선형 큐를 배열로 구현할 때, 선형 큐에서 요소를 삭제하면 다시 덮어쓰지 않기 때문에 심각한 저장공간의 낭비 발생
➡️ 낭비를 막기 위해 덮어써서 사용
➡️ 원형 큐
❗️front와 rear가 같아지는 상황을 막기 위해 한 칸을 비워놓고 사용
❗️rear = (rear + 1) % queue.size()

덱 : 양방향 삽입 삭제가 가능한 큐
(double-ended queue)

덱 연산

• addFirst(data) : 덱의 처음에 요소 삽입
• addLast(data) : 덱의 마지막에 요소 삽입
• pollFirst() : 덱의 처음 요소 삭제
• pollLast() : 덱의 마지막 요소 삭제

덱 클래스

import java.util.ArrayDeque;
import java.util.Deque;

Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);	// deque: 1
deque.addFirst(2);	// deque: 2 1
deque.addFirst(3);	// deque: 3 2 1
deque.addLast(10);	// deque: 3 2 1 10
deque.addLast(9);	// deque: 3 2 1 10 9
deque.addLast(8);	// deque: 3 2 1 10 9 8
deque.pollFirst();	// deque: 2 1 10 9 8
deque.pollLast();	// deque: 2 1 10 9