[Note] 스택(Stack)과 큐(Queue)

Stack

스택은 쉽게 바구니를 떠올리면 된다. 바구니에 물건을 담고 다시 꺼낼 때에는 마지막에 담았던 물건을 먼저 꺼낸다.

---

후입선출(LIFO : Last In First Out)

• 데이터를 한 뱡향으로만 저장할 수 있고, Top으로 정한 곳의 데이터만 조회/삽입/삭제를 할 수 있다.

---

주요 메서드

• isEmpty() : 스택이 비어있는지 boolean 타입으로 리턴한다. (비어있으면 true, 비어있지 않으면 false)
• isFull() : 스택이 가득찼는지 boolean 타입으로 리턴한다. (가득 차있으면 true, 가득 차있지 않으면 false)
• push() : 스택에 새로운 원소를 삽입한다.
• peek() : 가장 마지막에 삽입한 데이터를 읽는다.
• pop() : 가장 마지막에 삽입한 데이터를 읽고 해당 데이터를 삭제한다.

---

Queue

큐는 빨대를 생각하면 된다. 먼저 빨대에 들어간 음료수가 먼저 나온다.

---

선입선출(FIFO : First In First Out)

• 프론트로 정한 곳에서 조회 및 삭제 기능을 수행하고, 리어(Rear)로 정한 곳에서 삽입 기능이 수행된다.
• 선언은 다음과 같이 하면 된다.

Queue<String> stringQueue = new LinkedList<>();

---

주요 메서드

• isEmpty() : 큐가 비어있는지 boolean 타입으로 리턴한다. (비어있으면 true, 비어있지 않으면 false)
• isFull() : 큐가 가득찼는지 boolean 타입으로 리턴한다. (가득 차있으면 true, 가득 차있지 않으면 false)
• add() : 큐에 새로운 원소를 삽입한다. (리어에서 수행됨)
• peek() : 프론트의 데이터를 읽는다.
• poll() : 프론트의 데이터를 읽고, 해당 데이터를 삭제한다.

---

데크(Deque : Double-Ended Queue)

데크는 스택과 큐를 동시에 사용해야할 때 사용할 수 있는 자료구조이다.

양 끝 모두에서 데이터를 삽입하거나 출력이 가능한 자료구조이다.

---

주요 메서드

• append() : 데크의 오른쪽 끝에 삽입한다.
• appendleft() : 데크의 왼쪽 끝에 삽입한다.
• pop() : 데크의 오른쪽 끝의 데이터를 읽고 해당 데이터를 삭제한다.
• popleft() : 데크의 왼쪽 끝의 데이터를 읽고 해당 데이터를 삭제한다.
• extend(arr) : 배열 arr를 순환하면서 데크의 오른쪽에 추가한다.
• extendleft(arr) : 배열 arr를 순환하면서 데크의 왼쪽에 추가한다.
• remove(x) : 데크에서 x를 찾아 제거한다.
• rotate(num) : 데크를 num만큼 회전한다. (양수 => 오른쪽, 음수 => 왼쪽)