Stack
스택이란 자료구조는 사전적 정의인 '쌓다' '더미' 와 같습니다. 쉽게 설명하자면, 밑이 막힌 상자를 생각하시면 됩니다. 밑이 막혔으니 위로만 물건을 집어 넣을 수 있고, 뺄 수가 있겠죠? 이러한 구조 때문에 먼저 들어온 물건은 나중에 나갈 수 있고, 나중에 들어온 물건은 먼저 나갈 수 있게 됩니다. 이러한 구조를 '선입후출' '후입선출' 이라고 합니다.
자료구조를 공부하는 데 있어 코드로 구현하는 것도 중요하지만, 그보다 중요한 것은 자료구조를 어떻게 사용할지 아는 것이 더 중요합니다. 모든 자료구조는 [삽입],[삭제],[읽기]를 기본으로 가집니다. 따라서 앞으로 자료구조의 사용법은 이 세가지 위주로 알아보겠습니다.
스택 용도 및 예제
우리가 많이 사용하는 브라우저를 생각해봅시다. 인터넷 서핑을 하다가 뒤로가고 싶을 때, 뒤로가기 버튼을 사용합니다. '뒤로가기'버튼이 바로 스택으로 구현된 메쏘드(method) 중 하나입니다.
앞서 스택은 밑이 막힌 상자라고 하였습니다. 상자에 들어 갈 물건들은 그 동안 서핑하였던 인터넷 페이지들 입니다. 그러면 제일 마지막에 봤던 페이지는 가장 위에 쌓여져 있겠지요? (참고로, 우리 눈에 보여지는 페이지는 가장 위에 있는 페이지입니다.) 상자에 들어있는 물건을 빼는 것이 '뒤로가기'입니다. 즉 물건을 빼면 가장 최근에 본 페이지가 빠지겠지요. 그럼 가장 위에 쌓여져 있는 물건은 그 전에 봤던 페이지입니다. 따라서 '뒤로가기'버튼을 누르면 지금 보고 있는 페이지(스택의 최상위)가 빠져나가면서, 이전에 봤던 페이지가 보여지게 됩니다. 이렇게 '뒤로가기' 버튼은 스택의 구조로 구성되어 있습니다.
스택 사용법
push(element)- 요소를 스택의 최상단에 추가합니다.pop()- 스택의 최상단에서 요소를 제거하고 반환합니다.size()- 스택의 현재 요소 개수를 반환합니다.
스택 method 구현하기
class Stack {
constructor() {
this.storage = {};
this.top = 0;
}
size() {
//스택에 현재 몇개의 접시가 있는지 확인하는 로직
if(this.top <= 0) {
return 0;
} else {
return this.top;
}
}
push(element) {
if(this.top <= 0) {
this.top = 0; //0보다 작을 경우 , 0으로 세팅
this.storage[this.top] = element;
this.top ++;
}
else {
this.storage[this.top] = element;
this.top ++;
}
}
pop() {
if(this.top < 0) {
return;
}
delete this.storage[this.top];
this.top--;
return this.storage[this.top];
}
}
module.exports = Stack;Queue(큐)의 개념
- 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식
- Stack(스택)과 반대되는 개념
- 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용
Queue(큐)의 종류
- 선형(큐)
- 크기 제한
- 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮김
- 원형(큐)
- 선형 큐의 문제점을 보완
- front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결하는 방식
Queue(큐)의 메소드
배열을 이용한 큐
- getSize() : 큐의 크기를 반환
- isEmpty() : 큐가 비어있으면 true, 비어있지 않으면 false 반환
- isFull() : 큐가 가득 차있으면 true, 그렇지 않으면 false 반환
- enqueue() : ((rear+1) % size)번째 인덱스에 데이터 추가
- dequeue() : ((front+1) % size)번째 인덱스의 데이터 반환
- toString() : 큐의 모든 데이터를 반환
- clear() : 큐의 모든 데이터를 삭제
연결리스트를 이용한 큐
- isEmpty() : 큐가 비어있으면 true, 비어있지 않으면 false 반환
- enqueue() : 큐가 비어있으면 새로운 노드를 front와 rear로 선언, 비어있지 않으면 새로운 노드를 rear 노드의 next로 선언한 후 새로운 노드를 rear로 선언
- dequeue() : front 노드의 데이터 반환 후 front 노드의 next를 front 노드로 선언
- toString() : 큐의 모든 데이터를 반환
- clear() : 큐의 모든 데이터를 삭제
Queue(큐) 메소드 구현
class Queue {
constructor() {
this.storage = {};
this.front = 0;
this.rear = 0;
}
size() {
if(this.front === this.rear) {
return 0;
} else {
return this.rear - this.front;
}
}
enqueue(element) {
//storage 제일 마지막 인덱스로 추가하는 함수
this.storage[this.rear] = element;
this.rear++;
}
dequeue() {
//요소를 큐의 앞에서 제거하고 반환합니다.
if(this.front === this.rear) {
return this.storage;
}
let deleteEl = this.storage[this.front];
delete this.storage[this.front];
this.front++;
return deleteEl;
}
}
module.exports = Queue;