그렇다면 대표적인 자료구조들을 몇 개 정리해보고자 한다.
먼저 stack과 queue는 영구적으로 데이터를 저장하기 보다는 알고리즘처리 과정에서
임시로 데이터를 저장하는 역할을 하는 자료구조이다.
쌓여있는 형태의 자료구조이다. (LIFO : last in, first out)
좀 더 구체적인 비유를 들자면, 쌓여있는 책을 생각하면 된다.
즉 나중에 쌓인 책이 가장 먼저 그 쌓인 더미에서 읽히게 되는 것이다.
스택의 시작을 bottom이라고 하고, 스택의 끝을 top이라고 한다.
이는 쌓여있는 책에 스택을 비유한 것을 떠올려 스택을 그려보면 이해하기 쉬울 것이다.
class로 stack을 정의
class Stack {
constructor() {
this.storage = {};
this.top = 0;
}
}
size() : 스택이 가지고 있는 데이터 수를 반환한다.
size() {
return this.top;
}
//top 부분에서 stack이 가지고 있는 데이터의 갯수를 저장하고 있음.
push(item) : item을 스택의 가장 윗 부분에 추가한다.
push(element) {
this.storage[this.top] = element;
//storage 내에서 top의 인덱스 값을 출력
this.top++; // 그리고 this.top의 값을 증가.
}
pop() : 스택의 가장 윗부분을 꺼낸다.
pop() {
if(this.top === 0 ){
return ;
}
let topElement = this.storage[this.top-1];
//변수에 최상단 요소를 따로 선언해서 저장해두기.
//이때 최상단 요소의 인덱스 값이 this.top이 아니라 this.top-1인 이유는
//this.top의 값자체는 자료구조 내의 데이터 갯수이며, 최상단의 인덱스 값은
//데이터를 추가해서 갯수를++ 하기전의 인덱스 값이다.
//이는 위의 push 메소드를 함께보면 이해가 더 쉽다.
delete this.storage[this.top-1];
//최상단 요소를 제거하기
this.top--;
//return하기 전에 top-1 해주기
return topElement;
}
top(): 스택의 가장 위에 있는 항목을 반환한다.(peek()이라고도 한다.)
top() {
// return the top most element from the stack
// but does'nt delete it.
return this.storage[this.top - 1];
}
isEmpty(): 스택이 비어 있을 때에 true를 반환한다.
isEmpty(){
// return true if stack is empty
return this.items.length == 0;
}
insertion(삽입) : O(1) / deletion(삭제): O(1) / search : O(n)
삽입이나 삭제를 할 때, 스택은 “항상" 맨 위에 데이터를 삽입하거나 맨 위의 데이터를 삭제한다.
즉 새로운 데이터가 추가되어도 변함없이 맨 위의 데이터에 대해 연산이 수행된다.
매번 동일한 작업이 수행된다는 의미이다.
자료의 검색의 경우에는, 자료 내에 데이터 하나하나를 순차적으로 검색하고 찾아야 한다.
즉 최대 데이터의 갯수만큼 연산이 수행되므로 O(n) 시간복잡도를 가진다.
사람들이 맨 끝에 줄을 서고, 맨 앞에서부터 놀이기구에 탑승하는 것과 같은 자료구조이다.
(FIFO: first in, first out).
stack과 달리 한 쪽에서만 자료가 쌓였다가 없어지는 구조가 아니라,
양쪽에서 자료가 쌓이고 순차적으로 다른 쪽부터(먼저 쌓인 쪽부터) 자료가 사용되는 구조이다.
queue를 class를 통해 선언
class Queue {
constructor() {
this.storage = {};
this.front = 0;
this.rear = 0;
}
}
size() : queue의 데이터 수를 반환
size() {
//rear을 일종의 길이, 그리고 front는 빠져나간 데이터의 갯수로 정리하고 이해했다.
if(this.rear < this.front){
return 0;
}
return this.rear - this.front;
}
enqueue(item) : 자료의 맨 끝에 새로운 데이터를 추가
enqueue(element) {
//rear에 값을 추가
//rear 값 갱신
this.storage[this.rear] = element;
this.rear++;
}
dequeue() : 자료의 맨 앞에 있는 데이터를 제거
dequeue() {
// 값이 없는경우
if(this.rear === 0){
return;
}
// front 값을 저장해두고 ,제거한 뒤 front 값 갱신
let frontElement = this.storage[this.front];
delete this.storage[this.front];
this.front++;
return frontElement;
}
front() : 자료의 가장 앞에 있는 데이터의 타입을 반환
front(){
// returns the Front element of the queue without removing it.
if(this.isEmpty()){
return "No elements in Queue";
}
return this.items[0];
}
isEmpty(): 자료가 비어 있을 때에 true를 반환한다.(스택과 동일)
isEmpty(){
// return true if queue is empty
return this.items.length == 0;
}
insertion(삽입) : O(1) / deletion(삭제) : O(1) / search(검색) : O(n)
스택과 동일한 시간복잡도를 가진다.