스택 (Stack)
스택은 LIFO (Last In, First Out, 후입선출) 방식의 자료구조로, 가장 나중에 삽입된 데이터가 가장 먼저 삭제되는 구조입니다.
특징
- 삽입(Push)과 삭제(Pop) 연산만 허용되며, 두 연산은 항상 스택의 최상단(Top)에서만 수행됩니다.
- 데이터 접근이 제한적이며, 가장 마지막에 추가된 데이터부터 접근 가능.
- 재귀(Recursion) 구현이나 DFS(깊이 우선 탐색) 등의 알고리즘에서 많이 사용됨.
시간복잡도
- 삽입(푸시) 및 삭제(팝): O(1) (항상 스택의 Top에서만 연산)
- 탐색: O(n) (순차적으로 접근해야 하기 때문)
큐 (Queue)
큐는 FIFO (First In, First Out, 선입선출) 방식의 자료구조로, 먼저 삽입된 데이터가 가장 먼저 삭제되는 구조입니다.
특징
- 삽입(Enqueue)은 뒤(Rear)에서 수행, 삭제(Dequeue)는 앞(Front)에서 수행됨.
- 순서대로 처리해야 하는 작업에서 유용하게 사용됨.
- BFS(너비 우선 탐색), 운영체제의 작업 스케줄링, 네트워크 패킷 처리 등에 사용됨.
시간복잡도
- 삽입(Enqueue) 및 삭제(Dequeue): O(1) (항상 고정된 위치에서 연산)
- 탐색: O(n) (순차적으로 접근해야 하기 때문)
힙 (Heap)
우선 순위 큐를 위해 만들어진 자료구조.
완전 이진 트리의 일종으로 최댓값(최대힙)이나, 최솟값(최소힙)을 빠르게 찾기 위하여 만들어짐
특징
- 반 정렬 상태를 유지한다. (우선 순위 지정에 따라 트리에서 상위 레벨, 하위 레벨이 구분됨)
- 중복된 값을 허용한다.
- 최대 힙, 최소 힙 등이 있다. (커스텀으로 우선 순위를 지정할 수도 있음)
- 완전 이진 트리이므로, 배열로 구현이 가능하다. (자식노드 접근시 * 2, *2 +1)
- 최소, 최대 값을 빠르게 얻거나, 다익스트라 알고리즘을 이용할 때 사용된다.
시간복잡도
- 삽입, 삭제 : O(log n)
- 최소, 최대 조회 : O(1)
예상 질문
- 스택과 큐의 차이점은?
- 스택: LIFO(후입선출), Top에서만 삽입/삭제 가능
- 큐: FIFO(선입선출), Front에서 삭제, Rear에서 삽입
- 스택과 큐를 배열과 연결 리스트로 구현하면 차이가 있을까?
- 배열: 크기가 고정되어 있으며, 특정 크기 이상 저장이 어렵다.
- 연결 리스트: 동적 할당이 가능해 크기 제한이 없지만, 추가적인 메모리(포인터) 사용이 필요함.
- 큐의 변형된 형태에는 어떤 것들이 있는가?
- 원형 큐(Circular Queue): 배열 기반 큐에서 빈 공간을 줄이기 위해 사용.
- 우선순위 큐(Priority Queue): FIFO가 아닌 특정 우선순위에 따라 먼저 처리.
- ex) python에서 heapq, java에서 PriorityQueue
- 덱(Deque, Double-ended Queue): 양쪽에서 삽입과 삭제가 모두 가능한 자료구조.
- 스택을 사용하는 시스템과 같은것이 무엇이 있나요?
- 웹 브라우저의 뒤로 가기 (Back 버튼)
- 사용자가 방문한 페이지가 스택에 저장됨.
- 뒤로 가기를 누르면 가장 마지막에 방문한 페이지가 먼저 제거되면서 이전 페이지로 이동
- 실행 취소 (Undo) 기능
- 텍스트 편집기, 그래픽 소프트웨어 등에서 사용자가 수행한 작업을 저장함.
- "Ctrl + Z"를 누르면 마지막 작업이 먼저 취소됨.
- 여러 번 취소하면 가장 최근의 작업부터 순서대로 되돌릴 수 있음.
- 웹 브라우저의 뒤로 가기 (Back 버튼)
- 힙과 이진 탐색 트리의 차이점은 무엇인가요?
- 힙은 완전 이진 트리로, 최대/최소값을 빠르게 찾기 위해 사용되며, 자식 노드 간의 대소 관계가 없고, 부모 노드와의 관계만 중요합니다.
- 반면 이진 탐색 트리는 탐색을 위해 만들어진 트리로, 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 큽니다.
반응형