[TIL] 자료구조 : 스택(Stack) / 큐 (Queue)

1. 스택 (Stack)

---

후입선출(Last In First Out—LIFO) 특성을 가지는 자료구조 -> 입력과 출력이 한 방향으로 제한

1-1 . 스택의 용어

• 데이터 삽입 : push () 데이터를 스택의 최상위에 추가
• 데이터 삭제 : pop () 스택에서 최상위 데이터를 삭제
• 데이터 읽기 : peek() 스택의 최상위 항목을 반환
• 스택이 비어있는지 확인 : isEmpty() 스택이 비어있을때 True를 반환
• 스택이 가득차있는지 확인 : isFull()
• Stack Over Flow : 꽉 찬 스택에 요소를 삽입 할 때 흘러 넘쳐서 에러가 발생 하는 것

1-2. 스택의 시간복잡도 (Big O)

• Insertion O(1)
  
• Deletion O(1)
  • 삭제나 삽입시 맨 위에 데이터를 삽입하거나 삭제하기 때문에 시간복잡도는 늘 O(1) 의 시간복잡도를 가짐.
• Search O(n)
  • 하지만 특정 데이터를 찾을 때는 특정 데이터를 찾을 때까지 수행을 해야하므로 O(n) 의 시간 복잡도를 가짐.

1-3. 스택의 사용 예시

1. 재귀 알고리즘
2. 웹 브라우저 방문기록 (뒤로가기)
3. 실행 취소 (undo) - 흔히 쓰는 ctrl+z
4. 역순 문자열 만들기
5. 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사) - vscode에서 많이 쓰는
6. 후위 표기법 계산

1-4. 배열(Array)과 비교

• 문제의 종류에 따라 배열(Array)보다 스택에 데이터를 저장하는 것이 더 적합할 수 있음.

• 배열과 달리 스택은 상수 시간의 i번째 항목에 접근할 수 없다.

• 하지만 스택에서 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능.

• 배열처럼 원소들을 하나씩 옆으로 밀어 줄 필요가 없다.

• 스택(Stack)은 연결리스트 로 구현할 수 있다. 연결리스트의 같은 방향에서 아이템을 추가하고 삭제하도록 구현한다.

  

2. 큐(Queue)

---

선입선출(First In First Out—FIFO) 특성을 가지는 자료구조 -> 입력과 출력을 한 쪽 끝(front, rear)으로 제한

• 줄을 서는 행위와 유사하다.
• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조

2-1. 큐의 용어

• 큐의 가장 첫 원소 = front | 끝 원소 = rear
• Enqueue : 큐에 데이터를 넣는 기능
• Dequeue : 큐에서 데이터를 꺼내는 기능

2-2. 큐의 시간복잡도 (Big O)

• Insertion O(1)
• Deletion O(1)
• Search O(n)

2-3. 큐의 사용 예시

1. 티켓팅 (기차, 공연 등) 대기열, 콜센터 고객 대기시간, 게임 대기열 등
2. 프린터의 출력 처리
3. 캐시(Cache) 구현
4. 너비 우선 탐색(BFS, Breadth-First Search) 구현 : 처리해야 할 노드의 리스트를 저장하는 용도로 사용

참고 자료(References)

---

https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html
https://namu.wiki/w/%EC%8A%A4%ED%83%9D(%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0)#fn-1
https://www.fun-coding.org/DS&AL1-5.html
https://velog.io/@sbinha/%EC%8A%A4%ED%83%9D-%ED%81%90