스택(Stack)
스택은 무엇일까?
쌓아올린 더미를 자료구조로 표현- 데이터의 삽입과 삭제가 한쪽 끝(TOP)에서만 일어나는 특별한 형태의 리스트
어떻게 동작?
- 후입선출 (Last In First Out === LIFO)
- 마지막으로 삽입된 데이터가 가장 먼저 나옴
스택의 활용
- 웹 브라우저 뒤로가기 기능
- 문서 작업에서 되돌리기 기능
- JS 실행 컨텍스트
- 후위 표기법 계산
js코드로 스택 구현
구현 해야할 메소드
| 기본연산 | 설명 |
|---|---|
| init | 스택을 초기화 한다 |
| push | 스택에 새로운 데이터를 하나 삽입한다 |
| pop | 스택의 탑에 있는 데이터를 없애고, 그 값을 반환한다 |
| peek | 스택에 탑에 있는 데이터의 값을 반환한다 |
| getSize | 현재 스택에 들어가 있는 데이터의 수를 반환한다 |
| isEmpty | 현재 스택이 비어 있는지를 확인한다 |
linkedList로 구현
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Stack {
constructor() {
this.init();
}
// 스택을 초기화합니다.
init() {
this.top = null;
this._size = 0;
}
// 스택에 요소를 추가합니다.
push(value) {
const newNode = new Node(value);
newNode.next = this.top;
this.top = newNode;
this._size++;
}
// 스택에서 요소를 제거하고 반환합니다.
pop() {
if (this.isEmpty()) return undefined;
const value = this.top.value;
this.top = this.top.next;
this._size--;
return value
}
// 스택의 맨 위 요소를 반환합니다.
peek() {
if (this.isEmpty()) return undefined;
return this.top.value;
}
// 스택의 크기를 반환합니다.
getSize() {
return this._size;
}
// 스택이 비어있는지 확인합니다.
isEmpty() {
return this._size === 0;
}
}
array method로 구현
class Stack {
constructor() {
this.init();
}
// 스택을 초기화합니다.
init() {
this.items = [];
}
// 스택에 요소를 추가합니다.
push(element) {
this.items.push(element);
}
// 스택에서 요소를 제거하고 반환합니다.
pop() {
if (this.isEmpty()) return undefined;
return this.items.pop();
}
// 스택의 맨 위 요소를 반환합니다.
peek() {
if (this.isEmpty()) return undefined;
return this.items[this.items.length - 1];
}
// 스택의 크기를 반환합니다.
getSize() {
return this.items.length;
}
// 스택이 비어있는지 확인합니다.
isEmpty() {
return this.items.length === 0;
}
}
큐(Queue)
큐는 무엇일까?
기다리는 줄을 자료구조로 표현- 한쪽 끝(Rear)에서는 데이터의 삽입만, 또 다른 끝(Front)에서는 데이터의 삭제만 하도록 제한되어 있는 유한순서 리스트
어떻게 동작?
- 선입선출 (First In First Out === FIFO)
- 먼저 삽입된 데이터가 가장 먼저 나옴
큐의 활용
- 콜센터 고객 대기시간
- 우선순위가 같은 작업 ex) 프린터 대기열, 패킷
- 은행 업무
js코드로 큐 구현
구현 해야할 메소드
| 기본연산 | 설명 |
|---|---|
| init | 큐를 초기화 한다 |
| enqueue | 큐에 새로운 데이터를 하나 삽입한다 |
| dequeue | 큐의 탑에 있는 데이터를 없애고, 그 값을 반환한다 |
| peek | 큐에 가장 앞에 있는 데이터의 값을 반환한다 |
| getSize | 현재 큐에 들어가 있는 데이터의 수를 반환한다 |
| isEmpty | 현재 큐가 비어 있는지를 확인한다 |
linkedList로 구현
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Queue {
constructor() {
this.init();
}
// 큐를 초기화합니다.
init() {
this.front = null;
this.rear = null;
this._size = 0;
}
// 큐에 요소를 추가합니다.
enqueue(value) {
const newNode = new Node(value);
if (this.rear) this.rear.next = newNode;
else this.front = newNode;
this.rear = newNode;
this._size++;
}
// 큐에서 요소를 제거하고 반환합니다.
dequeue() {
if (this.isEmpty()) return undefined;
const value = this.front.value;
this.front = this.front.next;
if (!this.front) this.rear = null;
this._size--;
return value;
}
// 큐의 맨 앞 요소를 반환하지만 제거하지는 않습니다.
peek() {
if (this.isEmpty()) return undefined;
return this.front.value;
}
// 큐의 크기를 반환합니다.
getSize() {
return this._size;
}
// 큐가 비어있는지 확인합니다.
isEmpty() {
return this._size === 0;
}
}
array method로 구현
class Queue {
constructor() {
this.init();
}
// 큐를 초기화합니다.
init() {
this.items = [];
}
// 큐에 요소를 추가합니다.
enqueue(element) {
this.items.push(element);
}
// 큐에서 요소를 제거하고 반환합니다.
dequeue() {
if (this.isEmpty()) return undefined;
return this.items.shift();
}
// 큐의 맨 앞 요소를 반환합니다
peek() {
if (this.isEmpty()) return undefined;
return this.items[0];
}
// 큐의 크기를 반환합니다.
getSize() {
return this.items.length;
}
// 큐가 비어있는지 확인합니다.
isEmpty() {
return this.items.length === 0;
}
}
배열 큐의 문제점
-
표류현상
- 삽입, 삭제에 따라 큐의 내용이 점차 오른쪽으로 흘러가는 현상
- Front 인덱스의 왼쪽 부분은 비어있어도 사용하지 못함 -
해결방법
1. 큐의 데이터가 하나 제거 될 때 마다 모든 데이터 왼쪽으로 이동
2. Rear 인덱스가 오른쪽 끝에 와서 더 이상 증가시킬수 없을 때 큐의 모든 데이터 빈 공간만큼 왼쪽 이동
3.원형 배열을 사용자바스크립트의 배열은 일반적인 배열의 동작을 흉내 낸 특수한 객체이기 때문에 해당사항 없음
자바스크립트의 배열은 내부적으로 해쉬 테이블
끄적끄적 🖋️