스택 (STACK)이란?

스택(stack)이란 쌓아 올린다는 것을 의미한다.
책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다.

스택의 특징

• LIFO(Last In First Out, 후입선출) == FILO(First In Last Out, 선입 후출) 구조

• 단방향 입출력 구조 : 데이터의 들어오는 방향과 나가는 방향이 같다.

• 데이터를 하나씩만 넣고 뺄 수 있다.

• 깊이 우선 탐색(DFS)에 이용된다.

• 재귀 함수의 동작 흐름과 같은 구조를 가진다.

Stack 클래스 메서드

• push(), add()
  데이터를 스택에 추가하고, 해당 값을 반환한다.
  스택의 크기가 정해져 있고 꽉 차 있다면 stack overflow 발생.

• peek()
  스택의 마지막 요소를 반환하며, 스택에는 변화를 주지 않는다.
  즉, 스택에 가장 먼저 사용될 요소를 반환한다.
  만약, 스택이 비어있을 경우 peek() 메서드 호출 시 NoSuchElementException 예외가 발생한다.

• pop(), remove()
  스택의 마지막 요소 제거함과 동시에 해당 값을 반환한다.
  스택이 비어있다면 stack underflow 발생.

• isEmpty()
  스택이 비어있는지의 여부를 반환한다. 비어있을 경우 true, 비어있지 않을 경우 false를 반환한다.

• size()
  스택의 크기를 반환한다.

• contains(찾는 값)
  스택에 찾는 값이 있으면 true, 없으면 false를 반환한다.

• search(찾는 값)
  스택에서 검색하여 해당 위치를 반환한다.
  여기서 위치는 인덱스가 아닌 빠져나오는 순서를 뜻한다.
  만약 해당 인자가 여러 개일 경우, 마지막 위치를 반환한다.

  • 찾는 값이 스택에 없을 경우 -1을 반환한다.

• clear()
  스택의 모든 값 삭제(초기화)

스택 활용 예시

• 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
• 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
• 후위 표기법 계산
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

스택 시간 복잡도

	Average	Worst
Access	O(n)	O(n)
Search	O(n)	O(n)
Insert(push)	O(1)	O(1)
Delete(pop)	O(1)	O(1)

---

큐 (QUEUE)란?

Queue 의 사전적 의미는 줄(무엇을 기다리는 사람, 자동차 등의) , 혹은 줄을 서서 기다리는 것을 의미한다.

큐의 특징

• 디큐(dnQueue) : 큐의 앞부분(가장 첫 원소)은 front는 삭제 연산만 수행

• 인큐(enQueue) : 큐의 뒷부분(가장 끝 원소)은 rear는 삽입 연산만 수행

• 입력 순서대로 데이터 처리가 필요할 때 사용

Queue 메서드

메서드	설명
boolean add(Object)	큐에 데이터 추가성공하면 true 반환. 저장공간이 부족하면 IllegalStateExcepetion 발생
Object remove()	큐에서 객체를 꺼내 반환. 비어있으면 NoSuchElementException 발생
Object element()	삭제없이 요소를 읽어옴.비어있으면 NoSuchElement 발생
boolean offer(value)	큐에 데이터 추가성공하면 true, 실패하면 false 반환
Object poll()	큐에서 객채를 꺼네 반환. 비어있으면 null 반환.
Object peek()	삭제 없이 요소를 읽어옴. 비어있으면 null 반환

큐 사용 시 예외발생이 나지 않으려면 add, remove, elemant 대신 offer, poll, peek을 사용하는게 좋다!

큐의 활용 예시

• 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리 (Message Queue)
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 캐시(Cache) 구현

큐 시간 복잡도

Operation	Average	Worst
Access	O(n)	O(n)
Search	O(n)	O(n)
Insert (add)	O(1)	O(1)
Delete (remove)	O(1)	O(1)