Stack
- 후입선출 (Last in First Out LIFO)
- 인터넷 브라우저 뒤로가기
- Ctrl + z
- 다시 되돌리기
먼저들어간게 먼저나간다.
Stack
- push : 데이터 추가
- pop : 데이터 제거
- top : 맨 위 데이터 가져오기
- peek : 맨 위 데이터 가져오기
Queue
- 선입선출 (First in Fast Out -FIFO)
- 순서가 보장된 처리
- 사용자가 몰린 서버
- 놀이공원
Queue
- push, offer, add : 큐 추가
- pop, poll : 큐 삭제
- peek : 큐 가져오기
Queue의 구조
Queue는 배열로 구현한다면,,, 매우 비효율적이다
- 값을 하나만 삭제해도 모든 원소들을 앞으로 당겨야 하기 때문에 (O (n))
- Linked List 기반으로 만들어야 한다.
- 아니면 배열로 만들고 싶으면 서클러 큐로 만들면 된다.
원형 큐
- 배열을 이용한 원형 큐 구현
rear는 값이 push 될때마다 1씩 증가, front 는 pop 마다 인덱스 1씩 증가
rear와 front가 비어있는 경우 = 둘이 인덱스가 같은 경우
가득 찬 경우 : rear + 1 = front 인덱스와 같은 경우
원형 큐 단점
- 고정된 크기의 배열임
원형 큐 구현시 가장 중요한 것은
- modulo 연산자.
'자료구조&알고리즘' 카테고리의 다른 글
| 탐색과 정렬 알고리즘 (이진 탐색, 버블 정렬, 삽입 정렬, 합병 정렬, 퀵 정렬) (0) | 2022.04.08 |
|---|---|
| HASH와 HASH Collision 그리고 Chaining (해시 자료구조) (0) | 2022.04.07 |
| Double Linked List (이중 연결 리스트) (0) | 2022.04.07 |
| 리스트 - LinkedList (0) | 2022.04.07 |
| 자료구조 & 알고리즘을 왜 공부해야 할까? (0) | 2022.04.07 |