.gif&blockId=11b00c82-b138-8050-a58b-dcbceda2ef8f)
스택
•
쌓아올리는 것
•
밑에는 막혀있는 컵 구조
•
같은 구조와 크기의 자료를 정해진 방향으로 쌓을 수 있다.
구조 & 연산
•
후입선출(LIFO:Last In, First Out), 선입후출(FILO:First In Last Out) 구조
나중에 넣은 걸 먼저 뺀다.
먼저 넣은 건 나중에 뺀다.
•
연산 방식
◦
삭제 (pop()) : 스택에서 가장 위에 있는 항목을 제거한다. [O(1)]
◦
삽입 (push(item)) : item 하나를 스택의 가장 윗부분에 추가한다. [O(1)]
◦
읽기 (peek()) : 스택의 가장 위에 있는 항목을 반환한다. [O(1)]
특징
•
데이터를 저장하고 검색하는 프로세스가 매우 빠름
후입선출 구조로 데이터를 조회할 때 최상위 블록(Top)만 확인하면 되기 때문
•
데이터는 하나씩 넣고 뺄 수 있음
•
하나의 입출력 방향을 가지는 제한적 접근 형태
•
저장되는 데이터는 유한하고 정적 → 스택의 크기는 제한적
활용
•
웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
•
역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
•
실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
•
후위 표기법 계산
•
재귀함수
오버플로우 & 언더플로우
•
오버플로우 : 스택이 모두 차서 데이터가 더 이상 못 들어가는 현상
•
언더플로우 : 스택이 비어있을 때 데이터를 꺼내려 하여 발생하는 현 상
큐
•
쌓아올리는 것
•
밑에는 막혀있는 컵 구조
•
같은 구조와 크기의 자료를 정해진 방향으로 쌓을 수 있다.
구조 & 연산
•
선입선출(FIFO:First In, First Out), 후입후출(LILO:Last In Last Out) 구조
먼저 넣은 걸 먼저 뺀다.
나중에 넣은 건 나중에 뺀다.
•
연산 방식
◦
Enqueue : 큐에 데이터를 넣는 것
◦
Dequeue : 큐에서 데이터를 꺼내는 것
삽입 (Enqueue()) : 큐 맨 뒤에 어떠한 요소를 추가 [O(1)]
삭제 (Dequeue()) : 큐 맨 앞쪽의 요소를 삭제 [O(1)]
기 (peek()) : front에 위치한 데이터를 읽음 [O(n)]
•
삭제되는 데이터는 앞에 삽입되는 데이터는 뒤에 위치
활용
•
대기 번호표
•
물품 진열
•
BFS 구현
•
프린터 출력 처리
•
콜센터 고객 대기시간
특징
•
선입선출의 구조 덕에 데이터가 입력된 순서대로 연산을 처리할 때 사용
•
스택처럼 데이터는 하나씩 삽입, 방출 가능
•
두 개의 입출력 방향을 가지며 데이터의 입력과 출력 방향 상이
힙
•
완전 이진트리의 일종
•
우선순위 큐를 위해 만들어진 자료구조
우선 순위 큐
- 데이터들이 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 방출
- CPU 작업 스케줄링, 시뮬레이션 시스템에서 사용
•
최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
종류
•
최대 힙(max heap)
◦
부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
◦
key(부모 노드) ≥ key(자식 노드)
•
최소 힙(min heap)
◦
부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리
◦
key(부모 노드) ≤ key(자식 노드)
구조 & 연산
•
힙을 저장하는 표준적인 자료구조는 배열이다.
•
중복 값을 허용한다.
•
반 정렬 상태를 유지한다.
•
연산 방식
◦
삽입
▪
힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입
▪
새로운 노드를 부모 노드들과 교환
◦
삭제
▪
최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제됨 (최대 힙에서 삭제 연산은 최대값 요소를 삭제하는 것)
▪
삭제된 루트 노드에는 힙의 마지막 노드를 가져옴
▪
힙을 재구성
