A LIFO(Last In First Out) data structure
The last element added to the stack will be the first element removed from the stack
1. 클래스 선언
class Node {
constructor(value) {
this.value = value;
this.next = next;
}
}
class Stack {
constructor() {
this.first = null;
this.last = null;
this.size = 0;
}
}
2. push() 구현
pseudocode
class Stack {
constructor() {
this.first = null;
this.last = null;
this.size = 0;
}
push(val){
let newNode = new Node(val);
if(!this.first){
this.first = newNode;
this.last = newNode;
} else {
let temp = this.first;
this.first = new Node;
this.first.next = temp;
}
return ++this.size;
}
}
3. pop() 구현
pseudocode
class Stack {
constructor() {
this.first = null;
this.last = null;
this.size = 0;
}
push(val){
let newNode = new Node(val);
if(!this.first){
this.first = newNode;
this.last = newNode;
} else {
let temp = this.first;
this.first = new Node;
this.first.next = temp;
}
return ++this.size;
}
}
Big O of Stack
Insertion - O(1)
Removal - O(1)
Searching - O(N)
Access - O(N)
A FIFO(First in First Out) data structure
// 1. push() & shift()
let Q = [];
Q.push(1); // 1 인덱스 리턴
Q.push(2); // 2 인덱스 리턴
Q.push(3); // 3 인덱스 리턴
Q; // [1,2,3]
Q.shift(); // 1 value 리턴
Q.shift(); // 2 value 리턴
Q.shift(); //3 value 리턴
// 2 unshift() & pop()
let Q = [];
Q.unshift(1); // 1 배열의 길이 리턴
Q.unshift(2); // 2
Q.unshift(3); // 3
Q.pop(); // 1 value 리턴
Q.pop(); // 2 value 리턴
Q.pop(); // 3 value 리턴
배열을 사용하는 건 편리하지만 인덱싱 과정이 추가되어 메모리를 더 많이 사용한다. 인덱싱이 필요하지 않다면 Queue클래스를 따로 생성해 사용할 수 있다.
1. 클래스 선언
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Queue {
constructor() {
this.first = null;
this.last = null;
this.size = 0;
}
2.enqueue() 구현 == push()
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Queue {
constructor() {
this.first = null;
this.last = null;
this.size = 0;
}
enqueue(val){
let newNode = new Node(val);
if (!this.first) {
this.first = newNode;
this.last = newNode;
} else {
this.last.next = newNode;
this.last = newNode;
}
return ++this.size;
}
}
3.dequeue() 구현 == shift()
class Queue {
constructor() {
this.first = null;
this.last = null;
this.size = 0;
}
dequeue(){
if (!this.first) return null;
let temp = this.first;
if (this.first === this.last) {
this.last = null;
}
this.first = this.first.next;
this.size--;
return temp.value;
}
}
Big O of Queue
Insertion - O(1)
Removal - O(1)
Searching - O(N)
Access - O(N)