728x90
- 스택(Stack)의 개념
- 한 쪽으로만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조
- 메모리의 스택영역은 함수의 호출과 관계되는 지역변수외 매개변수가 저장되는 영역
- 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸.
- 컴퓨터의 시간지역성(최근에 참조된 자료가 다시 참조될 확률이 높다는 원리)을 활용할 수 있는 추상적 자료구조
- 스택(Stack)의 연산
- pop: 스택에서 가장 마지막에 입력된 항목을 활용하고 제거한다.
- push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
- peek(top): 스택의 가장 위에 있는 항목을 활용한다(삭제 ㄴㄴ).
- empty(): 스택이 비어 있을 때에 true를 반환한다.
- full : 스택이 다 차있으면 true반환
- size : 스택의 크기를 리턴 (O(n)시간복잡도)
- 스택(Stack)의 사용 사례
- 재귀 알고리즘
- 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
- 재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다.
- 스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다.
- 또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
- 웹 브라우저 방문기록 (뒤로가기)
- 실행 취소 (undo)
- 역순 문자열 만들기
- 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
- Ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기
- 후위 표기법 계산
- 재귀 알고리즘
- 큐(Queue)의 개념
- 데이터의 입력과 출력이 다른 자료구조.
- 먼저 집어 넣은 데이터가 먼저 나오는 선입선출, FIFO(First In First Out)구조로 저장하는 형식
- 큐(Queue)의 연산
- add(item): item을 리스트의 끝부분에 추가한다.
- delete: 리스트의 첫 번째 항목을 제거한다.
- front : queue의 맨 앞을 가리킴 데이터를 꺼낼 수 있는 위치.
- rear : queue의 맨 뒤를 가리킴, 데이터를 넣을 수 있는 위치.
- 큐(Queue)의 사용 사례
- 너비 우선 탐색(BFS, Breadth-First Search) 구현
- 처리해야 할 노드의 리스트를 저장하는 용도로 큐(Queue)를 사용한다.
- 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다.
- 노드를 접근한 순서대로 처리할 수 있다.
- 캐시(Cache) 구현
- 우선순위가 같은 작업 예약 (인쇄 대기열)
- 선입선출이 필요한 대기열 (티켓 카운터)
- 콜센터 고객 대기시간
- 프린터의 출력 처리
- 윈도우 시스템의 메시지 처리기
- 프로세스 관리
- 너비 우선 탐색(BFS, Breadth-First Search) 구현
728x90
'기술면접 대비' 카테고리의 다른 글
[자료구조] 힙이란?(heap) (0) | 2021.09.21 |
---|---|
[자료구조] Tree란? (0) | 2021.09.19 |
메모리구조 (0) | 2020.10.11 |