[C#/자료구조]스택 , 큐

[eBook] 자료구조와 알고리즘 with C# - 3장. 스택 및 큐

 

1. 스택

1) 정의

- 한 쪽 끝(상단)에서만 항목을 추가하고 제거할 수 있는 요소의 모음 

- 후입선출(LIFO) : 스택에 마지막으로 추가된 요소가 가장 먼저 제거

- 예 : 책 (가장 위에 있는 책이 가장 먼저 제거)

- 사용 예시 : 구문 분석(텍스트의 문자열을 분석하여 문법 구조 파악, 지금까지 처리된 텍스트의 기호 추적), 재귀 알고리즘 구현, 산술 표현식 평가, 프로그램 메모리에 호출 프레임 저장 등 

 

2) 연산

- Push : 스택의 맨 위에 요소를 추가

- Pop : 스택에서 가장 위에 있는 요소를 제거 

- Peek : 스택에서 가장 위에 있는 요소를 제거하지 않고 반환

- Count : 스택의 요소 수를 반환

- Contains : 특정 요소가 스택에 있는지 여부를 확인 

 

3) 알고리즘

- 재귀 함수

- 깊이 우선 탐색 (DFS)

- 백트래킹

- 포스트픽스 표기법

 

 

2. 큐

1) 정의

- 한 쪽 끝(후면)에서 항목을 추가하고 다른 쪽 끝(앞면)에서 항목을 제거할 수 있는 요소의 모음 

- 선입선출(FIFO) : 큐에 가장 먼저 추가된 요소가 가장 먼저 제거 

- 예 : 티켓을 기다리는 사람들 (가장 먼저 줄을 선 사람이 가장 먼저 티켓을 받을 수 있음) 

- 사용 예시 : 티켓팅 시스템, 레스토랑 대기 줄 시뮬레이션, 작업 예약(운영체제), 데이터 버퍼링(네트워크)

 

2) 연산 

- Enqueue : 큐 끝에 요소를 추가 

- Dequeue : 큐에서 첫 번째 요소를 제거

- Peek : 큐에서 첫 번째 요소를 제거하지 않고 반환

- Count : 큐의 요소 수를 반환

- Contains : 특정 요소가 큐에 있는지 여부를 확인 

 

3) 알고리즘

- 너비 우선 탐색 (BFS)

- 작업 스케줄링 

 

3. 비교

1) 주요 차이점

	스택	큐
순서	LIFO	FIFO
삽입 및 삭제	위쪽	앞쪽, 뒤쪽 각각
액세스	상단 요소	전면 요소, 후면 요소 전부 가능
사용 시기	역순으로 작업 수행 ex. 수학 식 구문 분석, 텍스트 편집기에서 작업 실행 취소	추가한 순서대로 처리 ex. 이벤트 루프에서 이벤트 처리, 작업 스케줄러에서 작업 예약

 

2) C# 메소드

	스택	큐
요소 추가	Push	Enqueue
요소 제거	Pop	Dequeue
제거 x, 값 가져오기	Peek
요소 수 구하기	Count
특정 요소 포함되어 있는지 확인	Contains
모든 요소 제거	Clear