javascript 자료구조 기초(1)

#Javascript를 위한 자료구조

Stack 📌

• LIFO (Last In, First Out) 구조를 가진댜.

const stack = [];
// push 값을 스택에 할당한다.
stack.push(1);
stack.push(2);
stack.push(3);

stack[stack.length-1]; // peek : 3 -마지막에 삽입된 값
stack.pop(); // 3
stack.pop(); // 2
stack.pop(); // 1
//삽입순서와 반대순서로 값을 뺀다

Queue 📌

• FIFO (First In, First Out) 구조를 가진다.

const queue = [];

queue.push(1); // enqueue 1
queue.push(2); // enqueue 2
queue.push(3); // enqueue 3

queue.shift(); // dequeue 1
queue.shift(); // dequeue 2
queue.shift(); // dequeue 3
// 삽입순서와 같은 순서로 값을 뺀다.

Linked List 📌

• 객체를 참조하는 방식으로 구현 가능하다.

function Node(val) {
  this.val = val;
  this.next = null;
}
let head = new Node(0);
let node1 = new Node(1);
let node2 = new Node(2);

head.next = node1;
node1.next = node2;

• 이중연결리스트도 구현가능하다. prev를 추가해서 양방향으로 참조하도록 구현한다.

function Node(val) {
  this.val = val;
  this.next = null;
  this.prev = null;
}
let head = new Node(0);
let node1 = new Node(1);
let node2 = new Node(2);

head.next = node1;
node1.next = node2;
node1.prev = head;
node2.prev = node1;

Map 📌

• O(1)의 접근성을 가진다 -> 시간복잡도를 줄이는데 결정적인 영향을 끼친다.
• ES6부터는 Map 자료구조가 추가되어 편리하게 사용가능하다.

const map = new Map();
map.set('p1', 1);
map.set('p2', 2);

map.get('p1'); // 1
map.get('p2'); // 2

Set 📌

• Map과 비슷하지만, 중복된 값을 허용하지 않는다.
• ES6 기준 문법

const set = new Set();
set.add(1);
set.add(2);

set.has(1); // true
set.has(2); // true
set.has(3); // false