Stack
Stack은 데이터를 순서대로 쌓는 선형 자료구조로, 한 쪽이 막힌 원통, 프링글스 통을 생각하면 된다.
Stack의 특징
- 입력과 출력이 하나의 방향, 즉 스택의 최상단에서만 데이터를 넣고 뺄 수 있음
- LIFO(Last In First Out), 후입선출의 구조로 되어있음
- 데이터는 하나씩 넣고 뺄 수 있음
Stack은 대표적으로 브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때 활용된다.
Stack 구현하기
멤버 변수
- 데이터를 저장할 Object 타입의 storage
- 마지막에 들어온 데이터를 가리키는 Number 타입의 포인터 top
메서드
- size(): 스택에 추가된 데이터의 크기를 리턴
- push(): 스택에 데이터를 추가
- pop(): 가장 나중에 추가된 데이터를 스택에서 삭제하고 삭제한 데이터를 리턴
Code
class Stack {
constructor() {
this.storage = {};
this.top = -1; // 스택의 가장 상단(데이터의 끝)을 가리키는 포인터 변수를 초기화 (의미 없는 값으로)
}
size() {
return this.top + 1; // 스택 크기는 top에 1을 더한 값
}
// 스택에 데이터를 추가 할 수 있어야 함
push(element) {
this.top += 1;
this.storage[this.top] = element; // 0 부터 top 인덱스 순서에 ele을 넣어주기
}
// 가장 나중에 추가된 데이터(top)가 가장 먼저 추출되어야 함
pop() {
// 빈 스택에 pop 연산을 적용해도 에러가 발생하지 않아야 합니다 (예외 처리)
// top이 음수이면(-1) 스택이 비어있는 것. 스택 비어있을 때 return; 구문으로 아무 처리 X
// 위에서 정의한 size 메서드 활용 가능 => if (this.size() <= 0)
if (this.top < 0) {
return;
}
// 순서 잘 지켜서 작성!
const result = this.storage[this.top]; // 1. 최상단 데이터를 변수 result에 할당
delete this.storage[this.top]; // 2. 최상단 데이터를 스토리지에서 삭제
this.top -= 1; // 3. top 한 칸 내려주기
return result; // 삭제한 데이터를 리턴
}
}Queue
Queue는 데이터가 대기열에 줄을 선 모습과 흡사한 선형 자료구조로, 양 쪽이 뚫린 원통이나 고속도로의 톨게이트를 생각하면 된다.
데이터(data)가 입력된 순서대로 처리할 때 주로 사용한다.
Queue의 특징
- FIFO(First In First Out), 선입선출의 구조로 되어있음
- 입력의 방향과 출력의 방향이 각각 고정되어 있으며, 데이터를 넣을 땐 큐의 끝에서, 뺄 땐 맨 앞에서 진행됨
- Queue에 데이터를 넣는 것은
enqueue, 데이터를 꺼내는 것은dequeue
- Queue에 데이터를 넣는 것은
- 데이터는 하나씩 넣고 뺄 수 있음
Queue는 대표적으로 컴퓨터와 연결된 프린터에서 여러 문서를 순서대로 인쇄할 때 등 컴퓨터 장치들 사이에서 데이터를 주고받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위한 임시 기억장치의 자료구조로 활용된다.
원형 큐
원형 큐(Circular Queue)는 일반적인 큐(Queue)와 유사하지만, 배열의 처음과 끝이 연결되어 있는 구조를 가지고 있는 자료구조이다. 원형 큐에서는 큐의 마지막 요소 다음에 첫 번째 요소가 위치하게 된다.
원형 큐의 특징
배열의 처음과 끝이 연결되어 있기 때문에, 큐의 front(맨 앞)와 rear(맨 뒤)가 움직일 때 배열의 끝까지 도달하지 않고도 다시 배열의 처음부터 원형적으로 이어질 수 있다. 이는 큐의 크기가 고정되어 있는 경우 큐를 더욱 효율적으로 활용할 수 있게 만들어준다.
원형 큐에서는 front와 rear의 초기값이 모두 0으로 설정되고, 요소를 추가할 때 rear를 증가시키고 요소를 삭제할 때 front를 증가시킨다. 만약 rear가 배열의 끝에 도달하면, 다시 배열의 처음으로 이동하여 새로운 요소를 추가한다. 마찬가지로, front가 배열의 끝에 도달하면 다시 배열의 처음으로 이동하여 요소를 삭제한다.
하지만, 원형 큐에서는 큐가 가득 찬 경우와 큐가 비어 있는 경우를 구분하기 위해 추가적인 변수를 사용해야 한다. 예를 들어, 원형 큐가 배열의 크기보다 하나 작은 경우, 큐가 가득 찬 상태는 front와 rear가 한 요소 차이로 존재하는 경우이다. 이와 같은 추가적인 변수 사용으로 인해 원형 큐의 구현이 복잡해질 수 있지만, 효율적인 메모리 사용과 더욱 효율적인 큐 연산을 가능하게 해준다.
Queue 구현하기
멤버 변수
- 데이터를 저장할 Object 타입의 storage
- 큐의 가장 앞을 가리키는 Number 타입의 포인터 front
- 큐의 가장 뒤를 가리키는 Number 타입의 포인터 rear
메서드
- size(): 큐에 추가된 데이터의 크기를 리턴
- enqueue(): 큐에 데이터를 추가
- dequeue(): 가장 먼저 추가된 데이터를 큐에서 삭제하고 삭제한 데이터를 리턴
Code
class Queue {
constructor() {
this.storage = {};
this.front = 0;
this.rear = 0;
}
size() {
return this.rear - this.front; // 큐의 크기는 rear(뒷쪽)에서 front(앞쪽)을 뺀 값
}
// 큐에 데이터를 추가
enqueue(element) {
this.storage[this.rear] = element;
this.rear += 1;
}
// 가장 먼저 추가된 데이터가 가장 먼저 추출(FIFO)
dequeue() {
// 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않아야 함
if (this.front === this.rear) { // 추가 시 rear++, 추출 시 front++ 되므로, 둘이 같은 경우 비어있는 것 => size() 메서드 활용 가능
return;
}
const result = this.storage[this.front]; // 1. 가장 앞의 데이터를 변수 result에 할당
delete this.storage[this.front]; // 2. 가장 앞의 데이터를 스토리지에서 삭제
this.front += 1; // 3. front 1 증가 시키기(다음 순서 인덱스 값을 가리키도록)
return result;
}
}