stack
- 자료의 입력과 출력을 한 곳(방향)으로 제한한 자료구조.
- LIFO (Last In First Out)
- 삽입: push / 삭제:pop
queue
- 자료의 입력과 출력을 한 쪽 끝(front, rear)으로 제한한 자료구조.
- FIFO (First In First Out) - 선착순
- 삽입: push / 삭제:pop -> push통해 쌓은 자료는 가장 먼저 들어온 자료부터 pop연산으로 꺼냄
- bfs, 컴퓨터 버퍼에서 주로 사용. 많은 양의 정보가 입력되어 처리를 못할 때, 버퍼(큐)를 만들어 대기 시킴.
- 일반적 큐의 단점: 큐에 빈 메모리가 남아 있어도 꽉 차있다고 판단할 수 있음(rear가 배열 끝에 도달했을 경우)
-> 개선된 원형 큐가 나옴. 메모리 공간의 효율적 활용 가능 but 이 또한 큐의 크기가 제한되는 단점이 존재
-> 링크드리스트로 큐가 나옴 (큐의 크기 제한 X, 삽입/삭제 용이)
deque
- 자료의 입력/출력을 양 쪽 끝에서 가능하게 한 자료구조.
- appendleft & popleft /append & pop
Reference
https://jeong-pro.tistory.com/97
공부방