Chapter1. 자료구조
Chapter2. Stack과 Queue
2-1 Stack
2-2 Queue
2-3 원형 큐(Circular Queue)
Chapter1. 자료구조
자료구조 : 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 뜻함
자료구조를 많이 아는 개발자 = 데이터를 체계적으로 저장, 효율적으로 활용할 줄 아는 개발자 = 알고리즘 로직을 잘 짜는 개발자
📌 자료구조
- 여러 데이터의 묶음을 저장하고 사용하는 방법을 정의한 것
- 데이터(data) : 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값
- 그 자체만으로 어떤 정보를 가지진 않음
- 분석하고 정리하여 활용해야만 의미를 가짐
- 데이터 사용 목적에 따라 형태를 구분, 분류하여 사용한다.
✨ 자료구조의 분류
- 단순구조 : 자료값을 사용하기 위한 기본 형태
- 선형구조 : 자료들간의 관계가 1:1인 자료
- 비선형구조 : 계층구조나 망구조를 갖는 자료구조
- 파일구조 : 서로 관련있는 필드로 구성된 레코드 집합인 파일에 대한 자료구조. 보조기억장치에 데이터가 실제로 기록되는 형태
✨ 자료구조의 특징
- 특정한 상황에 놓인 문제를 해결하는 데에 특화되어 있다.
- 따라서 많은 자료구조를 알아두면, 문제가 생겼을 때 적합한 자료구조를 적용해 해결할 수 있다.
- 이는 문제해결력을 필요로 하는 알고리즘 테스트와 밀접한 연관이 있다.
- 따라서 많은 자료구조를 알아두면, 문제가 생겼을 때 적합한 자료구조를 적용해 해결할 수 있다.
자료구조를 시각화한 사이트
Chapter2. Stack과 Queue
📌 Stack
Stack : 쌓다, 쌓이다, 포개지다
데이터를 순서대로 쌓는 자료구조
✨ Stack의 구조
프링글스
가장 먼저 들어간 감자칩이 가장 나중에 나온다.
- 프링글스 통 : 자료구조 Stack
- 감자칩 : 데이터(data)
✨ Stack의 특징
-
입력과 출력이 하나의 방향으로 이뤄지는 제한적 접근 구조
-
1. LIFO(Last In First Out) & FILO(First In Last Out) : 먼저 들어간 데이터는 제일 나중에 나오는 후입선출의 구조
- Stack에 데이터를 삽입하는 연산 :
push - 데이터를 삭제하는 연산 :
pop
예1) 1, 2, 3, 4를 스택에 차례대로 넣는다. stack.push(데이터) --------------------------- 1 <- 2 <- 3 <- 4 --------------------------- 1번이 제일 먼저, 4번이 마지막으로 들어가게 된다. 예2) 스택이 빌 때까지 데이터를 전부 빼낸다. stack.pop() --------------------------- --------------------------- 4, 3, 2, 1 제일 마지막에 있는 데이터부터 차례대로 나온다.- 이러한 특성으로 스택 구조는 조회가 필요하지 않음.
- 장점 : 데이터를 저장하고 검색하는 프로세스가 매우 빠르며 최상위 블록에서 데이터를 저장하고 검색하면 된다.
- Stack에 데이터를 삽입하는 연산 :
-
2. 저장되는 데이터는 유한하고 정적이어야 한다.
-
ex. 콜 스택(Call Stack) : 콜 스택 내부에 함수 실행 데이터는 스택의 프레임(해당 기능에 필요한 데이터가 저장되는 공간)으로 저장되며, 함수가 새로운 변수를 선언하면 스택의 최상위 블록으로 push되는 구조다. 즉, 함수가 종료될 때마다 최상위 블록이 지워지는 후입선출 구조이므로 여기에 저장된 데이터는 정적 특성을 가져야지만이 컴파일 시간이 결정된다.
-
-
3. 스택의 크기는 제한되어 있다.
- 힙(heap)에 비해 스택의 크기가 제한되어 있으므로 스택 오버플로 에러가 자주 발생한다.
-
✨ Stack의 실사용 예제
- 브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때
- 새로운 페이지로 접속할 때 : 현재 페이지를 Prev Stack에 보관
- 뒤로가기 버튼을 눌러 이전 페이지로 돌아갈 때 : 현재 페이지를 Next Stack에 보관, Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져옴
- 앞으로 가기 버튼을 누르면 : Next Stack의 가장 마지막으로 보관된 페이지를 가져옴
- 마지막으로 현재 페이지를 Prev Stack에 보관함
- 그외 : 실행취소(undo), 역순 문자열 만들기, DFS 알고리즘, 재귀 알고리즘
✨ Stack 구현
class Stack {
//stack constructor를 생성
constructor() {
this.storage = {};
this.top = 0;
}
// stack의 사이즈 구하기
// this.top은 스택이 쌓일 때마다 하나씩 증가하기 때문에 top으로 size를 구할 수 있다.
// this.top : 스택에 새롭게 추가될 요소의 인덱스. 0부터 1씩 증감하며 표현하기 때문에 전체 요소의 개수를 나타낼 수 있다
size() {
return this.top;
}
//stack에 element를 추가
//새롭게 추가될 요소의 인덱스를 나타내는 this.top을 키로, 요소를 값으로 하여 storage에 할당한다. this.top은 다음 인덱스를 가리키게 하여 새로운 요소에 대비합니다.
push(element) {
this.storage[this.top] = element;
this.top += 1;
}
// stack에서 element를 제거한 뒤 해당 element를 반환
// 만약 size가 0이라면 아무 일도 일어나지 않음
// top-1로 최상단을 설정한 후 변수에 저장하고, 스택에서 삭제
// 하나를 제거했으니 top도 감소한다.
pop() {
if (this.size() <= 0) {
return;
}
const result = this.storage[this.top - 1];
delete this.storage[this.top - 1];
this.top -= 1;
return result;
}
}📌 Queue
Queue : 줄을 서서 기다리다, 대기행렬
✨ Queue의 구조
고속도로의 톨게이트 : 자동차가 진입한 순서대로 통행료를 내고 톨게이트를 통과한다.
- 톨게이트 : Queue 자료구조
- 자동차 : 데이터
✨ Queue의 특징
-
자료구조 Queue는 데이터(data)가 입력된 순서대로 처리할 때 주로 사용한다.
-
입력과 출력의 방향이 고정되어 있으며, 두 곳으로 접근이 가능하다
-
1. FIFO(First In First Out) & LILO(Last In Last Out) : 먼저 들어간 데이터(data)가 먼저 나오는 선입선출 구조
- Queue에 데이터를 삽입하는 연산 :
enqueue - 데이터를 삭제하는 연산 :
dequeue
예1) 1, 2, 3, 4를 큐에 차례대로 넣는다. queue.enqueue(데이터) 출력 방향 <---------------------------< 입력 방향 1 <- 2 <- 3 <- 4 <---------------------------< 들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어간다. 예2) 큐가 빌 때까지 데이터를 전부 빼낸다. queue.dequeue(데이터) 출력 방향 <---------------------------< 입력 방향 <---------------------------< 1, 2, 3, 4 제일 첫 번째 있는 데이터부터 차례대로 나온다. - Queue에 데이터를 삽입하는 연산 :
-
2. 데이터는 하나씩 넣고 뺄 수 있다.
- 데이터가 많이 있어도 하나씩 넣고 뺀다.
-
3. 두 개의 입출력 방향을 가진다.
- Queue 자료구조는 데이터의 입력, 출력 방향이 다르다.
-
✨ Queue의 실사용 예제
-
큐는 주로 데이터가 입력된 시간 순서대로 처리해야할 때 사용함
- 컴퓨터와 연결된 프린터에서 여러 문서를 순서대로 인쇄하기
- 출력 버튼을 누르면 해당 문서는 인쇄작업(임시 기억 장치의)Queue에 들어간다.
- 프린터는 인쇄 작업 Queue에 들어온 문서를 순서대로 인쇄한다.
- 컴퓨터와 연결된 프린터에서 여러 문서를 순서대로 인쇄하기
-
각 장치 사이에 존재하는 속도, 시간차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용한다. 이것을 통틀어 버퍼(buffer)라고 한다.
- 버퍼(buffer) : 불규칙적으로 발생한 이벤트를 규칙적으로 처리할 때 사용
-
그 외 : 은행업무, 콜센터 고객 대기시간, 프로세스 관리, BFS 알고리즘, 캐시(Cache) 구현
✨ Queue 용어
| 용어 | 설명 |
|---|---|
| getBuffer() | 데이터 전체 반환 |
| enQueue() | 데이터 추가 rear + 1 |
| deQueue() | 데이터 삭제 front + 1 |
| front() | 첫 번째 데이터 조회 |
| isFull() | Queue가 Full 상태인지를 확인 rear = n-1 rear 값이 마지막 데이터값을 나타내면 Full 상태이다. |
| isEmpty() | Queue가 empty 상태인지를 확인 front = rear : 데이터가 없다는 뜻 |
| dataSize() | Queue 안의 데이터 개수 확인 |
| clear() | Queue 초기화 |
✨ Queue 구현
class Queue {
//가장 앞에 있는 요소를 front,
//가장 뒤에 있는 요소를 rear.
constructor() { //queue constructor 생성
this.storage = {};
this.front = 0;
this.rear = 0;
}
// queue의 사이즈를 구하기
// queue는 추가될 때, rear의 값이 커지고 삭제 될 때, front가 변경이 때문에, 각 값을 알아야 size를 구할 수 있음.
size() {
return this.rear - this.front;
}
// queue에 element를 추가
// 새롭게 추가될 요소의 인덱스를 나타내는 this.rear를 키로, 요소를 값으로 하여 storage에 할당
// this.rear : 다음 인덱스를 가리키게 하여 새로운 요소에 대비
enqueue(element) {
this.storage[this.rear] = element;
this.rear += 1;
}
// queue에서 element를 제거 -> 해당 element를 반환
// 만약 size가 0 : 아무 일 X
// this.front+1로 가장 앞에 있는 요소를 다시 설정한 후 변수에 저장하고, 큐에서 삭제한다.
dequeue() {
if (this.size() === 0) {
return;
}
const result = this.storage[this.front];
delete this.storage[this.front];
this.front += 1;
return result;
}
}📌 원형 큐(Circular Queue)
- 탄생 배경
- Queue 구조 : 데이터를 넣는 위치(rear)와 데이터를 가져오는 위치(front)가 다르다. 이를 반복하다보면 데이터를 넣을 수 없는 상태가 발생한다.
→ 이러한 문제점을 해결한 것이 원형 큐
원형 큐 : 데이터를 넣고 가져오는 방향이 없는 구조
- 단, 큐의 크기가 지정되어 있어야 하며
- front, rear의 위치 계산을 위해 빈 공간이 있어야됨
- 즉, 실제 사용할 수 있는 큐의 크기 = 전체 큐의 크기 -1
- 위의 원형 큐의 크기는 6이지만 실제 데이터가 저장되는 크기는 5다.
- 큐는 front와 rear의 위치가 -1이지만, 원형 큐는 front와 rear의 위치가 0이다.
셀 병합 어떻게 ... ?
| 자료구조 | 삽입 연산 | 삭제 연산 | ||
|---|---|---|---|---|
| 연산자 | 삽입위치 | 연산자 | 삭제 위치 | |
| 스택 | push | top | pop | top |
| 큐 | enQueue | rear | deQueue | front |
블로그 이사했습니다 🧳