CS - Data Structure - 스택 (Stack) & 큐 (Queue)

[ 1. Stack ]

 

 

• 선형 자료 구조이며 후입선출(Last-In-First-Out: LIFO)을 따른다.
• 가장 나중에 저장된 데이터가 가장 먼저 나온다. = 후입 선출
• 큐 와는 다르게 데이터 저장, 제거가 한 부분에서 이루어진다. (큐는 front, rear)
• 스택의 가장 위 요소를 가리키는 top pointer 한 개를 가진다.
• 스택의 top이라는 부분 한 곳에서만 데이터가 삽입되고 제거되는 컨테이너라고 볼 수 있다.

활용

• 웹 브라우저 뒤로가기
• 문서작업에서 Ctrl + Z
• 역순 문자열 만들기
• 후위 표기법 계산
• 재귀적 알고리즘

[ 2. Queue ]

 

 

 

• 선형 자료 구조이며 데이터를 한쪽에서만 삽입하고 한쪽에서만 제거할 수 있는 자료구조
• 먼저 들어간 데이터가 먼저 제거되는 선입선출(First-In-First-Out:FIFO) 자료구조
• Rear 에서 데이터 삽입. Front에서 데이터 제거
• 데이터 삽입을 Enqueue. 데이터 제거를 Dequeue 라고 부른다.

활용

• 은행창구 번호표 대기
• 프린터 출력
• 컴퓨터 운영체제의 테스크 스케줄링
• 너비 우선 탐색 (BFS)