그렇다면 대표적인 자료구조들을 몇 개 정리해보고자 한다.
먼저 stack과 queue는 영구적으로 데이터를 저장하기 보다는 알고리즘처리 과정에서
임시로 데이터를 저장하는 역할을 하는 자료구조이다.
Stack
쌓여있는 형태의 자료구조이다. (LIFO : last in, first out)
좀 더 구체적인 비유를 들자면, 쌓여있는 책을 생각하면 된다.
즉 나중에 쌓인 책이 가장 먼저 그 쌓인 더미에서 읽히게 되는 것이다.
스택의 시작을 bottom이라고 하고, 스택의 끝을 top이라고 한다.
이는 쌓여있는 책에 스택을 비유한 것을 떠올려 스택을 그려보면 이해하기 쉬울 것이다.
stack의 연산
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;
}stack의 시간복잡도
insertion(삽입) : O(1) / deletion(삭제): O(1) / search : O(n)
삽입이나 삭제를 할 때, 스택은 “항상" 맨 위에 데이터를 삽입하거나 맨 위의 데이터를 삭제한다.
즉 새로운 데이터가 추가되어도 변함없이 맨 위의 데이터에 대해 연산이 수행된다.
매번 동일한 작업이 수행된다는 의미이다.
자료의 검색의 경우에는, 자료 내에 데이터 하나하나를 순차적으로 검색하고 찾아야 한다.
즉 최대 데이터의 갯수만큼 연산이 수행되므로 O(n) 시간복잡도를 가진다.
Queue
사람들이 맨 끝에 줄을 서고, 맨 앞에서부터 놀이기구에 탑승하는 것과 같은 자료구조이다.
(FIFO: first in, first out).
stack과 달리 한 쪽에서만 자료가 쌓였다가 없어지는 구조가 아니라,
양쪽에서 자료가 쌓이고 순차적으로 다른 쪽부터(먼저 쌓인 쪽부터) 자료가 사용되는 구조이다.
queue의 연산
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;
}queue의 시간복잡도
insertion(삽입) : O(1) / deletion(삭제) : O(1) / search(검색) : O(n)
스택과 동일한 시간복잡도를 가진다.
