728x90
반응형
스택
데이터의 모음 -> 압축적인 데이터 구조 LIFO(Last In First Out) 후입 선출
- Undo/Redo 기능
-인터넷 방문 기록
Big O
*Insertion - O(1)
*Removal - O(1)
Searching - O(N)
Access - O(N)
class Node{
constructor(value){
this.value=value
this.next=null
}
}
class Stack{
constructor(){
this.first=null;
this.last=null;
this.size=0
}
push(val){
var newNode=new Node(val)
if(!this.first){
this.first=newNode
this.last=newNode
}else{
var temp=this.first
this.first=newNode
this.first.next=temp
}
return ++this.size
}
pop(){
if(this.size===0) return null
var temp=this.first
if(this.size===1) {
this.last=null
}
this.first=this.first.next
this.size--
return temp.value
}
}
큐
FIFO(First In First Out) 선입 선출 (추가 - enqueue 제거 - dequeue)
- 접속 대기
- 줄
- 업로드
- 프린트 대기열
- 업무 처리할때 유리
Big O
*Insertion - O(1)
*Removal - O(1)
Searching - O(N)
Access - O(N)
class Node {
constructor(value){
this.value = value;
this.next = null;
}
}
class Queue {
constructor(){
this.first = null;
this.last = null;
this.size = 0;
}
enqueue(val){
var newNode = new Node(val);
if(!this.first){
this.first = newNode;
this.last = newNode;
} else {
this.last.next = newNode;
this.last = newNode;
}
return ++this.size;
}
dequeue(){
if(!this.first) return null;
var temp = this.first;
if(this.first === this.last) {
this.last = null;
}
this.first = this.first.next;
this.size--;
return temp.value;
}
}
728x90
반응형
'알고리즘(Algorithm)' 카테고리의 다른 글
해시 테이블(HASH TABLES) (0) | 2022.08.30 |
---|---|
힙 + 우선 순위 큐 (0) | 2022.08.26 |
트리 (0) | 2022.08.22 |
트리 순회 (1) | 2022.08.22 |
이중 연결 리스트 (0) | 2022.08.16 |