자료구조에서 스택과 큐는 자료구조를 처음 접했을 때 등장하는 개념에 속합니다. 그 만큼 자주 쓰인다는 뜻이기도 합니다. 이번에는 스택과 큐의 개념과 차이점에 대해서 알아보겠습니다.
스택과 큐(Stack, Queue) 개념
스택
입구와 출구가 같은 자료구조로 Last in, First out(LIFO)의 특징을 가지고 있다.
큐
입구와 출구가 다른 자료구조로 First in, First out(FIFO)의 특징을 가지고 있다.
스택과 큐(Stack, Queue) 장단점, 시간복잡도, 이해하기
스택
장점) 데이터 접근, 삽입, 삭제 등이 빠르다.
단점) top으로만 접근이 가능하기 때문에 탐색을 하려면 모든 데이터를 꺼내 확인해야 한다.
시간복잡도) O(1)
스택 이해하기) 스택은 입구와 출구가 같기 때문에 top을 통해서 삭제와 삽입 모두 이루어진다.
push : 원소 삽입
pop : 가장 위의 원소 꺼내기
top : 가장 위에 있는 원소 확인
size : 스택의 크기 확인
큐
장점) 데이터 접근, 삽입, 삭제 등이 빠르다.
단점) 스택과 마찬가지로 탐색이 어렵다.
시간복잡도) O(1)
큐 이해하기) 큐는 양쪽 끝에서 데이터의 삽입과 삭제가 각각 이루어진다.
push : 원소 삽입
pop : 원소 추출
Enquque : 입구
Dequeue : 출구
Front : 맨 앞 요소를 가리킴(데이터가 제거되는 곳)(출구 쪽)
Rear : 맨 뒤 요소를 가리킴(데이터가 삽입되는 곳) (Front==Rear인 경우라면 queue is empty)
큐의 다른 종류 : 원형큐(Circular Queue), 우선순위 큐(Priority Queue)
'CS > 자료구조' 카테고리의 다른 글
| [자료구조] 자료구조 면접 질문 모음 (0) | 2023.01.21 |
|---|