18주차 (1)

15. Stack과 Queue 비교 설명

Stack과 Queue는 데이터를 저장하고 관리하는 자료구조이며, 각각 고유한 방식으로 데이터를 처리합니다.

1) Stack (스택)

• 정의: Stack은 LIFO(Last In, First Out, 후입선출) 원칙을 따르는 자료구조입니다.
• 특징:
  • 데이터를 한쪽 끝(Top)에서만 추가(push)하고 제거(pop)할 수 있음.
  • 재귀 함수 호출, 수식 계산(예: 후위 표기법), 브라우저 뒤로 가기 등의 기능에 사용됨.
• 주요 연산:
  • push(item): 데이터를 스택의 맨 위(Top)에 추가.
  • pop(): 스택의 맨 위 데이터를 제거하고 반환.
  • peek(): 스택의 맨 위 데이터를 확인하지만 제거하지 않음.
  • isEmpty(): 스택이 비어 있는지 확인.

2) Queue (큐)

• 정의: Queue는 FIFO(First In, First Out, 선입선출) 원칙을 따르는 자료구조입니다.
• 특징:
  • 데이터를 한쪽 끝(Rear)에서 추가(Enqueue)하고 반대쪽 끝(Front)에서 제거(Dequeue).
  • 운영체제의 프로세스 스케줄링, 프린터 작업 대기열, 네트워크 패킷 전송 등에 사용됨.
• 주요 연산:
  • enqueue(item): 데이터를 큐의 끝(Rear)에 추가.
  • dequeue(): 큐의 앞(Front) 데이터를 제거하고 반환.
  • peek(): 큐의 앞(Front) 데이터를 확인하지만 제거하지 않음.
  • isEmpty(): 큐가 비어 있는지 확인.

3) Stack과 Queue의 차이점

구분 Stack (스택) Queue (큐)

원칙	LIFO (후입선출)	FIFO (선입선출)
데이터 추가	Top에서 추가 (push)	Rear에서 추가 (enqueue)
데이터 제거	Top에서 제거 (pop)	Front에서 제거 (dequeue)
사용 예시	함수 호출, 브라우저 뒤로 가기	프로세스 스케줄링, 프린터 대기열

---

16. 그래프(Graph)와 트리(Tree) 설명 및 차이점

1) 그래프(Graph)

• 정의: 그래프는 정점(Vertex, 노드)과 간선(Edge)으로 이루어진 자료구조로, 여러 개의 노드가 서로 연결되어 있음.
• 특징:
  • 방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)가 있음.
  • 가중치 그래프(Weighted Graph)에서는 간선마다 가중치(Weight)가 부여됨.
  • 주로 지도, 네트워크 연결, SNS 관계 등을 모델링할 때 사용됨.
• 구성 요소:
  • Vertex(노드): 그래프 내의 개별적인 점.
  • Edge(간선): 노드를 연결하는 선.
  • Adjacency List(인접 리스트): 각 노드에 대해 연결된 노드를 리스트로 저장.
  • Adjacency Matrix(인접 행렬): 2차원 배열로 노드 간 연결 관계를 표현.

2) 트리(Tree)

• 정의: 트리는 사이클이 없는 그래프의 한 종류로, 계층적 구조를 가짐.
• 특징:
  • 노드(Node)와 간선(Edge)으로 구성됨.
  • 루트 노드(Root Node)에서 시작해 자식 노드(Child Node)로 확장됨.
  • 부모-자식 관계(Parent-Child)가 존재하며, 사이클(Cycle)이 없음.
  • 이진 트리(Binary Tree), 이진 탐색 트리(BST), AVL 트리 등 다양한 형태가 존재함.
• 주요 개념:
  • Root Node(루트 노드): 트리의 최상위 노드.
  • Leaf Node(리프 노드): 자식이 없는 노드.
  • Depth(깊이): 루트에서 특정 노드까지의 거리.
  • Height(높이): 특정 노드에서 가장 깊은 노드까지의 거리.

3) 그래프와 트리의 차이점

구분 그래프 (Graph) 트리 (Tree)

방향성	방향 그래프/무방향 그래프 존재	항상 방향성이 있음 (부모 → 자식)
사이클 존재	사이클 가능	사이클 없음
루트 존재	루트 개념 없음	루트 노드 존재
연결성	일부 노드가 분리될 수 있음	모든 노드가 연결됨
예시	지도, SNS 관계	조직도, 파일 시스템

이와 같이 Stack, Queue, Graph, Tree의 개념과 차이점을 정확히 이해하면 면접에서 좋은 답변을 할 수 있습니다!

 

https://www.notion.so/teamsparta/1a42dc3ef51480d58fa9f50148990fcc

위치 업데이트 | Notion