4월 4일 화요일 TIL 회고록

스택

---

스택의 개념

스택(Stack)이란 어떠한 자료를 쌓아서 올려놓은 형태의 자료구조

책상의 쌓여있는 책들이나 싱크대의 접시를 예시로 들 수 있다.

스택의 특징

• 스택은 위의 그림과 같이 아래에서 위로 쌓이는 형태이며 가장 최근의 들어온 자료를 top이라 부른다.
• 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가지고 있다
• 이러한 스택의 구조를 후입선출(LIFO, Last-In-First-Out) 구조라고 한다.
• 스택의 경우 자료의 삽입과 삭제는 한 곳(top)에서만 이루어진다.
• 스택이 비어있을 때 자료를 꺼내려고 시도를 하면 스택 언더플로우(Stack Underflow)가 발생하게 된다.
• 반대로 스택이 꽉 차있을때 자료를 넣으려고 하면 스택 오버플로우(Stack Overflow)가 발생하게 된다.

스택의 활용 예시

• 웹 브라우저 뒤로 가기 : 가장 나중에 열린 페이지부터 뒤로 가기를 실행한다.
• 문서작업에서 Ctrl + Z : 가장 나중에 수정한 내역부터 되돌린다.
• 역순 문자열 만들기 : 맨 끝에 문자열부터 차례대로 만들어진다.
• 후위 표기법 계산
• 재귀적 알고리즘

---

큐

---

큐의 개념

큐는 쉽게 말해 데이터들이 일렬로 줄 서서 기다리는 것을 뜻한다.

놀이기구를 기다리는 줄, 음식점 번호표를 예시로 들 수 있다.

큐의 특징

• 정해진 곳(top)에서만 자료의 삽입과 삭제가 이루어지는 스택과는 달리 큐는 Rear 부분에서 자료의 삽입, Front 부분에서 자료의 삭제가 이루어진다.
• 사전적 의미는 (무엇을 기다리는 사람, 자동차 등의) 줄, 혹은 줄을 서서 기다리는 것을 의미한다. 따라서 일상생활에서 놀이동산에서 줄을 서서 기다리는 것처럼 선입선출 (FIFO, First-In-First-Out) 구조를 가지고있다.

큐의 활용 예시

• 은행 창구 번호표 대기 : 빠른 번호표를 가진 사람이 먼저 업무를 볼 수 있다.
• 프린터 출력 : 가장 먼저 대기열에 오른 프린트가 먼저 출력된다.
• 컴퓨터 운영체제의 테스크 스케줄링 : 가장 간단한 형태의 선입선출 처리 스케줄링 정책
• 너비 우선 탐색(BFS) 알고리즘

---

스택

---

스택의 개념

스택(Stack)이란 어떠한 자료를 쌓아서 올려놓은 형태의 자료구조

책상의 쌓여있는 책들이나 싱크대의 접시를 예시로 들 수 있다.

스택의 특징

• 스택은 위의 그림과 같이 아래에서 위로 쌓이는 형태이며 가장 최근의 들어온 자료를 top이라 부른다.
• 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가지고 있다
• 이러한 스택의 구조를 후입선출(LIFO, Last-In-First-Out) 구조라고 한다.
• 스택의 경우 자료의 삽입과 삭제는 한 곳(top)에서만 이루어진다.
• 스택이 비어있을 때 자료를 꺼내려고 시도를 하면 스택 언더플로우(Stack Underflow)가 발생하게 된다.
• 반대로 스택이 꽉 차있을때 자료를 넣으려고 하면 스택 오버플로우(Stack Overflow)가 발생하게 된다.

스택의 활용 예시

• 웹 브라우저 뒤로 가기 : 가장 나중에 열린 페이지부터 뒤로 가기를 실행한다.
• 문서작업에서 Ctrl + Z : 가장 나중에 수정한 내역부터 되돌린다.
• 역순 문자열 만들기 : 맨 끝에 문자열부터 차례대로 만들어진다.
• 후위 표기법 계산
• 재귀적 알고리즘

---

큐

---

큐의 개념

큐는 쉽게 말해 데이터들이 일렬로 줄 서서 기다리는 것을 뜻한다.

놀이기구를 기다리는 줄, 음식점 번호표를 예시로 들 수 있다.

큐의 특징

• 정해진 곳(top)에서만 자료의 삽입과 삭제가 이루어지는 스택과는 달리 큐는 Rear 부분에서 자료의 삽입, Front 부분에서 자료의 삭제가 이루어진다.
• 사전적 의미는 (무엇을 기다리는 사람, 자동차 등의) 줄, 혹은 줄을 서서 기다리는 것을 의미한다. 따라서 일상생활에서 놀이동산에서 줄을 서서 기다리는 것처럼 선입선출 (FIFO, First-In-First-Out) 구조를 가지고있다.

큐의 활용 예시

• 은행 창구 번호표 대기 : 빠른 번호표를 가진 사람이 먼저 업무를 볼 수 있다.
• 프린터 출력 : 가장 먼저 대기열에 오른 프린트가 먼저 출력된다.
• 컴퓨터 운영체제의 테스크 스케줄링 : 가장 간단한 형태의 선입선출 처리 스케줄링 정책
• 너비 우선 탐색(BFS) 알고리즘