스택, 큐, 덱에 저장..💪

📖 스택, 큐, 덱이란?

• 데이터 값의 저장하는 기본적 구조
• 일차원의 선형(linear) 자료구조
• 배열/리스트와 유사하게 값을 저장하는 연산과 저장된 값을 꺼내는 연산 제공
• 제한적인 규칙(LIFO, FIFO) 등이 따름
  
  

---

1. 스택(Stack)

스택 : 한 쪽 끝에서만 접근 가능한 자료구조(LIFO)

• push : 마지막에 자료 추가
• pop : 마지막에 넣은 데이터 추출
• peek : 마지막에 넣은 데이터 확인, 추출X

• LIFO: Last In First Out
• 쌓여 있는 접시와 같다고 이해하면 쉬움
• 맨 위(가장 최근에 넣은) 데이터에만 접근할 수 있음
• 데이터가 없을 때 pop하는 오류 stack underflow
• 스택 크기 이상의 자료를 push하는 오류 stack overflow
• +) 데이터의 삽입과 삭제가 빠름
• -) 맨 위의 데이터만 접근 가능하기 때문에 탐색 시 데이터를 하나하나 꺼내서 옮겨야 함
• 활용) 인터넷 이전 페이지, 다음 페이지 / 깊이우선탐색(DFS)

---

2. 큐(Queue)

큐 : 양쪽 끝에서 접근 가능한 자료구조(FIFO)

• add : 마지막에 자료 추가
• poll : 가장 먼저 넣은 데이터 추출
• peek : 가장 먼저 넣은 데이터 확인, 추출X

• FIFO: First In Firest Out
• 데이터가 삽입(put) 되는 곳 front, 제거(get) 되는 곳 rear
• +) 데이터의 삽입/삭제가 빠름
• -) 큐 중간에 위치한 데이터로 접근이 어려움
• 활용) 프린터 인쇄 대기열 / 너비우선탐색(BFS)

---

3. 덱(Deque, Double Ended Queue)

덱 : 큐와 유사하지만, 양쪽 끝에서 삭제와 삽입이 모두 가능한 자료구조 (스택+큐)

• addFirst : 앞쪽에 데이터 추가
• addLast : 뒷쪽에 데이터 추가
• pollFirst : 앞쪽 데이터 추출
• pollLast : 뒷쪽 데이터 추출
• peekFirst : 앞쪽 데이터 확인
• peekLast : 뒷쪽 데이터 확인

• 큐는 일방향 데이터 삽입/추출만 가능함에 반해, 덱은 양방향 데이터 삽입/추출 가능
• 크기가 가변적(선언 후 변경 가능)
• +) 데이터의 삽입/삭제가 빠름
• +) 크기가 가변적임
• +) index로 임의 원소 접근 가능
• -) 여전히 덱 중간에서의 삽입 삭제가 어려움
• -) 구현이 어려움
• 활용) 앞, 뒤에서 삽입/삭제가 빈번한 경우 / 데이터 개수가 가변적인 경우