728x90
728x90
Stack(스택)
삽입(push)과 삭제(pop)이 한쪽 끝(top)에서만 일어나는 자료구조다.
- top : 가장 상단에 위치한 원소를 가리키는 용어
- push() : top 위치에 데이터를 삽입하는 기능
- 시간복잡도 : O(1)
- 용량이 꽉 찬 스택에 push()를 시도하면 Stack Overflow 에러가 발생한다.
- pop() : top 위치의 데이터를 삭제/반환 하는 기능
- 시간복잡도 : O(1)
- 데이터가 없는 스택에 pop()을 시도하면 Stack Underflow 에러가 발생한다.
특징
- 후입선출 LIFO(Last In First Out)
- 특정 데이터를 찾기 위해서는 해당 값을 찾을 때 까지 pop()을 반복해야 한다 - O(N)
- JAVA 에서는 Stack 라이브러리를 제공한다.
Queue(큐)
삽입(enqueue)은 한 쪽(rear)에서, 삭제(dequeue)는 반대 쪽(front)에서 일어나는 자료구조
- front : 큐의 맨 앞 부분
- rear : 큐의 맨 뒷 부분
- enqueue() : 큐의 맨 뒤(rear) 위치에 데이터를 추가하는 기능
- 시간복잡도 : O(1)
- 용량이 꽉 찬 큐에 enqueue()를 시도하면 Queue Overflow 에러가 발생한다.
- dequeue() : 큐의 맨 앞(front) 위치의 데이터를 삭제/반환 하는 기능
- 시간복잡도 : O(1)
- 데이터가 없는 큐에 dequeue()을 시도하면 Queue Underflow 에러가 발생한다.
특징
- 선입선출 FIFO(First In First Out)
- 특정 데이터를 찾기 위해서는 해당 값을 찾을 때 까지 dequeue()을 반복해야 한다 - O(N)
- Java에서는 인터페이스 형태로 Queue 라이브러리를 제공한다.
- 주로 LinkedList를 사용해 구현한다.
Deque(데크)
Double Ended Queue의 약자로, 양방향 Queue 이다.
- 양쪽 끝 위치에서의 삽입/삭제/반환 모두 O(1)의 시간복잡도를 가진다.
참고
[Java(자바)] Deque(덱/데크) 자료구조
카프카의 소스코드를 보던 중 내부에서 Deque 클래스를 사용한 부분을 보게 되었다. Deque(덱 혹은 데크)은 Double-Ended Queue의 줄임말로 큐의 양쪽으로 엘리먼트의 삽입과 삭제를 수행할 수 있는 자료
soft.plusblog.co.kr
[스택] Stack 이란?
Stack 이란? 스택 (Stack) 특징을 가장 잘 나타내는 표현은 후입선출(Last In First Out, LIFO) 이다. ▶ 스택(Stack)은 삽입(push)과 삭제(pop)이 한쪽 끝에서만 일어나는 구조 가장 상단에 위치한 원소를 가리
zoosso.tistory.com
[큐] Queue란?
Queue란? 선입선출(First In First Out, FIFO)의 자료 구조 ▶ 큐(Queue)는 한쪽에서 삽입(Push, Enqueue) 하며, 다른 한쪽에서 빠져나오는(Pop, Dequeue) 구조 두 지점을 와 로 표현한다. (Front, Rear) ▶ C++ STL로 구현
zoosso.tistory.com
728x90
728x90
'Computer Science > Data Structure' 카테고리의 다른 글
Thread Safe 자료구조 (0) | 2023.03.09 |
---|---|
Heap(힙) (0) | 2023.03.09 |
트리, 이진트리, 이진탐색트리 (0) | 2023.03.08 |
Linked List(연결 리스트) (0) | 2023.03.08 |
시간복잡도 & 공간복잡도 (0) | 2023.02.24 |