스택 (Stack)
: 마지막에 들어온 요소가 먼저 나가는 LIFO(Last In First Out) 자료구조
- Top : 가장 맨 위에 있는 요소
x5 - 스택의 크기는 제한되어 있다.
힙(heap)에 비해 스택의 크기는 제한되어 있으므로, Stack Overflow와 같은 에러가 자주 발생한다. - 스택에 저장되는 데이터는 유한하고 정적이어야 한다.
스택의 연산
스택의 기본적인 연산으로는 push와 pop이 있다.
- Push : 스택의 맨 위에 요소를 추가한다.
- Pop : 맨 위에 있는 요소를 삭제하고 반환(return)한다.
스택의 상태를 확인하기 위해 추가적인 함수도 제공한다.
- Peek : 맨 위에 있는 요소를 삭제하지 않고 반환한다.
- isEmpty : 스택이 비어있는지 확인한다.
- isFull : 스택이 꽉 찼는지 확인한다.
➡️ 스택 구조는 조회가 필요하지 않으므로, 데이터를 저장하고 검색하는 프로세스가 매우 빠르며, 최상위 블록에서 데이터를 저장하고 검색하면 된다는 장점이 있다.
스택의 사용
- 재귀 프로그래밍에서 함수 호출을 구현하는 데 사용된다.
(예시는 재귀를 이용해 팩토리얼을 구하는 코드)
- 스택 메모리에 사용된다.
*스택 메모리 : 함수가 호출되면 생성되는 지역변수, 매개변수가 저장되는 메모리 영역
➡️ 함수 호출은 스택 자료구조를 통해 메모리에 기억되고 제거된다.
)
- 브라우저의 뒤로 가기, 앞으로 가기 기능에 사용된다.
배열로 스택 구현하기
const stack = [];
// Push
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack); // [1, 2, 3]
// Pop
stack.pop();
console.log(stack); // [1, 2]
// Get Top
console.log(stack[stack.length - 1]); // 2연결 리스트로 스택 구현하기
...
큐(Queue)
: 먼저 들어온 요소가 먼저 나가는 FIFO(First In First Out) 자료구조
- Front : 맨 앞에 있는 요소
x1 - Rear : 맨 뒤에 있는 요소
x5
큐의 연산
- Enqueue : 큐에 요소를 추가한다.
- Dequeue : 큐에서 요소를 뺀다.
- Peek : 가장 앞의 요소를 삭제하지 않고 반환한다.
큐의 사용
- 멀티스레딩(multithreading)에서 스레드를 관리하는 데 사용된다.
- 대기열 시스템에 사용된다. (e.g. 우선순위 대기열)
- 동영상 스트리밍 앱에서 데이터를 Queue에 모아두었다가, 동영상을 재생하기에 충분한 양의 데이터가 모였을 때 동영상을 재생한다.
- 프린터를 사용할 때, 인쇄 작업을 위한 임시 기억 장치에 사용된다.
컴퓨터 장치들 사이에서 데이터(data)를 주고받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간의 차이를 극복하기 위해, 임시 기억 장치의 자료구조로 Queue를 사용한다.
이것을 통틀어 버퍼(buffer)라고 한다.
버퍼링(buffering)
대부분의 컴퓨터 장치에서 발생하는 이벤트는 불규칙적으로 발생한다. 이에 비해 발생한 이벤트를 처리하는 장치(CPU)는 일정한 처리 속도를 가진다.
➡️ 이때 CPU는 불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼(buffer)를 사용한다.
컴퓨터와 프린터 사이의 데이터(data) 통신을 정리하면,
- 프린터는 속도가 느리지만, CPU는 프린터보다 데이터를 처리하는 속도가 빠르다.
- 따라서 CPU는 빠른 속도로 인쇄에 필요한 데이터를 만든 다음, 인쇄 작업 Queue에 저장하고 다른 작업을 수행한다.
- 프린터는 인쇄 작업 Queue에서 데이터(data)를 받아 일정한 속도로 인쇄한다.
큐의 종류
1. Linear Queue(선형 큐)
배열로 선형 큐 구현하기
class Queue {
constructor() {
this.queue = []; // 요소를 넣을 배열 변수
this.front = 0; // 각각 front와 rear를 나타내기 위한 index 변수
this.rear = 0;
}
}
// Enqueue
enqueue(value) {
this.rear++;
this.queue[rear] = value;
// rear index를 1 증가시키고, 값을 넣는다.
}
// Dequeue
dequeue() {
const value = this.queue[this.front];
delete this.queue[this.front];
this.front++;
return value;
// front index에 해당하는 값을 반환하고, front index를 1 증가시킨다.
}
// Peek
peek() {
return this.queue[this.front];
// front index에 해당하는 값을 반환한다.
}
// 큐의 길이 구하기
size() {
return this.rear - this.front;
// rear index에서 front index를 뺀다.
}
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.dequeue()); // 1
queue.enqueue(4);
console.log(queue.size()); // 3
console.log(queue.peek()); // 2큐를
shift()로 구현하면 안되는 이유맨 앞의 요소를 삭제하기 위해
shift()를 사용하는 것은 선형 시간O(n)이 걸린다. 삭제되는 위치 이후의 요소들을 모두 앞으로 한 칸씩 당겨줘야 하기 때문이다.
같은 이유로 맨 앞에 요소를 추가하는unshift()역시 선형 시간O(n)이 걸린다.반면에, 맨 끝의 요소를 추가/삭제하는
pop(),push()는 상수 시간O(1)만 소요된다.
연결 리스트로 선형 큐 구현하기
// Node 클래스
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
// Queue 클래스
class Queue {
constructor() {
this.head = null; // 생성자에서는 head와 tail을 null로 지정한다.
this.tail = null;
this.size = 0;
}
// 요소를 추가하기 위한 enqueue 함수
enqueue(newValue) {
const newNode = new Node(newValue); // 값을 받아 새로운 노드를 생성한다.
if(this.head === null) { // head가 비어있는 경우, head와 tail에 생성한 노드를 넣어준다.
this.head = this.tail = newNode;
} else { // head가 비어있지 않은 경우,
this.tail.next = newNode; // 꼬리 부분에 next에 생성한 노드를 넣어준다.
this.tail = newNode; // 새로 추가된 노드가 꼬리가 되도록 설정해준다.
}
this.size++;
}
// 요소를 빼기 위한 dequeue 함수
dequeue() {
const value = this.head.value; // head의 값을 별도의 변수에 담아두고,
this.head = this.head.next; // 리스트에서 head를 제거한다.
this.size--;
return value; // 앞서 담아둔 head의 값을 반환한다.
}
// head의 값을 그대로 리턴하는 peek 함수
peek() {
return this.head.value;
}
}2. Circular Queue(환형 큐)
: Front와 Rear가 이어져있는 큐
Circular Queue는 연결 리스트로 구현했을 때 이점이 없다.
배열로 환형 큐 구현하기
...
❔ 학습 후 궁금한 점
- 연결리스트로 스택, 큐 구현하기
개발 공부 기록 블로그