티스토리 뷰
1. 스택 (Stack)
📌 스택의 특징
📝 스택은 가장 최근에 들어온 것이 가장 먼저 나가는 후입선출(LIFO) 자료구조이다.
스택의 입출력은 맨 위에서만 일어나고, 중간에서는 삭제를 할 수 없다.
데이터가 들어오는 과정을 push, 나가는 과정이 pop이라고 일반적으로 정의한다.
가장 최근에 들어온 자료는 TOP라 한다.
스택이 비어있을 때 POP을 하면, 스택 언더 플로우 발생하고,
반대로 꽉 차있을 때 PUSH을 하면 스택 오버 플로우가 발생한다.
📌 스택의 활용
애플리케이션 뒤로가기, ctrl+Z
후위 표기법 계산
재귀적 알고리즘
JAVA에서 지역변수, 리턴값 등을 저장하는 메모리 구조
괄호 검사 알고리즘
미로 탐색 프로그램 등
2. 큐 (Queue)
📌 큐의 특징
📝 큐는 TOP에서만 데이터의 삽입, 삭제가 이루어지는 스택과는 다르게
Rear(뒤) 부분에서 삽입이루어진다.
Front(앞) 부분에서 삭제가 이루어지는 선입선출 (FIFO) 자료 구조이다.
JAVA를 예를 들면, 삽입을 offer() 혹은 add()로 표현하고, 삭제는 poll()을 사용한다.
스택과 마찬가지로 큐가 비어있을 때 삭제나 탐색을 하면 큐 언더플로우가 발생하고,
큐가 꽉 차있을 때 삽입을 하면 큐 오버플로우가 발생한다.
오버플로우를 방지하기 위해 나온 것이 원형 큐 (Circular Queue) 이다.
📌 큐의 활용
CPU 스케쥴링 : 간단한 형태의 선입선출 처리 스케쥴링 정책
버퍼를 사용하는 것들 : 프린터 출력 등
교통 관리 시스템 같은 일반적인 대기열을 사용하는 상황
BFS : 너비우선탐색
📌 원형 큐 (Circular Queue)
📝 마지막 위치와 시작 위치가 연결되는 원형쿠조를 띠는 큐이다. 선입선출 구조를 지닌다는 점에서 동일하며,
포화인 큐에서 삽입을 하면 오버플로우가 발생하는 선형 큐를 보완한 자료구조이다.
enqueue : 값 삽입 (rear 포인터가 앞으로 이동)
dequeue : 값 삭제 (front 포인터가 앞으로 이동)
공백 상황 : front 포인터와 rear 포인터가 같은 값인 인덱스 0을 가리킬 때.
포화 상황 : front 포인터의 값과 rear 포인터의 값의 차가 1일때.
📝 front 포인터 혹은 rear 포인터와 큐의 사이즈를 나머지연산을 이용하여
인덱스를 계속 순환하도록 하여 오버플로우가 발생하지 않도록 함.
enqueue(20) -> rear = ((rear+1) % 5(size) = 2) 에 삽입.
dequeue() -> front = ((front+1) % 5 = 1)
3. 덱(Deque)
📌 덱의 특징
📝 덱은 앞, 뒤 양쪽에서 데이터의 삽입, 삭제가 가능한 자료구조이다. 이러한 특징으로 스택보다는 큐 형태로 사용이 가능하다.
구현이 어려운 것이 특징이나, 원하는 요소에 바로 스택, 큐보다 빠르게 접근이 가능하다는 이점이 있다.
4. 시간 복잡도
삽입 | 삭제 | 읽기, 탐색 | |
스택 | O(1) | O(1) | O(n) |
큐 | O(1) | O(1) | O(n) |
덱 | O(1) | O(1) | O(n) |
'CS > 자료구조' 카테고리의 다른 글
[자료구조] 비선형 자료구조 3탄 : 힙 트리, 우선순위 큐 (0) | 2023.08.12 |
---|---|
[자료구조] 비선형 자료구조 2탄 : 그래프 (0) | 2023.08.12 |
[자료구조] 비선형 자료구조 1탄 : 트리 (0) | 2023.08.06 |
[자료구조] 선형 자료구조 1탄 : 배열 / 연결리스트 (0) | 2023.07.22 |
[자료구조] 자료구조 / 시간 복잡도 (0) | 2023.07.22 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 채팅기능개발
- TiL
- 과정중간회고
- boj
- 데이터베이스
- 패스트캠퍼스강의
- 국비지원캠프
- 백엔드부트캠프
- springboot
- 야놀자X패스트캠퍼스부트캠프
- 그룹스터디
- 스터디후기
- 카카오API
- 야놀자
- 프로젝트후기
- qjzl
- 커리어멘토링
- 그룹스터디워크샵
- 부트캠프
- 백엔드개발자
- 국비지원
- Java
- 백준
- 자료구조
- 자료구조 #스택 #큐 #덱 #선형자료구조
- #국비지원취업
- 백엔드
- 패스트캠퍼스
- 국비지원취업
- be
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
글 보관함