스택

Last In First Out 개념을 가진 선형 자료구조가 스택이다.

(참고) 콜스택

함수가 호출되며 생성되는 지역변수, 매개변수가 저장되는 메모리 영역을 스택 메모리라고 한다. 즉, 함수 호출은 스택 자료구조를 통해 메모리에 기억되고 저장된다.

자바스크립트 엔진은 자바스크립트 코드를 실행하는 프로그램 또는 인터프리터이다.
이는 Memory Heap & Call Stack 으로 구성되어 있다. 자바스크립트는 단일 스레드 (sigle thread) 프로그래밍 언어인데, 이 의미는 Call Stack이 하나라는 것이다. (하나의 스레드 당 하나의 스택 메모리를 사용)

---

위 코드가 Call Stack 영역과 Heap 영역에서 어떻게 동작하는지 알아보도록 하겠습니다.

const a = 'Hello World!';
const b = [1, 2, 3];
const c = { id:'yoy', password:1234 };
const d = function(){ console.log() };

우선 각 변수 a, b, c, d는 call stack의 실행컨텍스트 렉시컬환경이라는 곳에 { name : value } 형태로 저장됩니다. 비록 초기화 단계에서는 { 변수이름 : undefined } or { 함수이름 : function() object } 로만 저장되지만, 그래도 해당 변수의 이름을 식별할 수 있게됩니다. 우리는 이것을 식별자 해결 이라고 부릅니다.

• 원시타입 ( a )
  콜스택 메모리에는 단순 변수와 같은 원시 타입 데이터가 저장되는데, 자바스크립트에서 원시타입이란 string, number, boolean, null, undefined 을 말합니다. 변수 a는 콜스택 영역에 있는 a의 주소를 읽고, 그 콜스택 영역에 그대로 'Hello World'라는 값 자체가 저장되어 있습니다.
  
  
• 참조타입 ( b, c, d)
  반면 복잡한 객체와 같은 참조타입 데이터는 힙 영역에 저장되고, 자바스크립트에서 참조타입으로는 Array, Object, Function 등이 있습니다.
  참조타입 변수들도 원시타입과 마찬가지로 콜스택에 각각의 주소를 읽고 있는데, 그 주소에 적혀있는 것은, 배열이나 객체와 같은 데이터가 아니라 힙 영역의 주소들이 들어있습니다.
  const는 선언시에 반드시 값을 작성해주어야하고, 값을 변경하지 않을 때 사용하는 변수이다.
  
  

let vs. const
데이터 값이 변경될 가능성이 있을 때는 let, 변경되지 않을 때는 const 사용
참조하고 있는 주소를 바꿀 수 없는 것이지, 그 주소가 가르키고 있는 데이터는 바꿀 수는 있다.
ex) Object의 property값, 배열의 요소의 값

const c = { id: 'yoy', pw: 1234 };
c.gender = 'F';
console.log(c);	// {id: 'yoy', pw: 1234, gender: 'F'}

const로 선언된 c의 데이터가 변경되었는데도 에러가 발생하지 않고 정상적으로 작동합니다.
❓ 변경 유무는 데이터의 값이 아니라, 콜스택의 값을 기준으로 판단하기 때문입니다. 그렇기 때문에 가르키고 있는 원시타입의 데이터 or 힙영역의 주소는 변경할 수 없지만, 실제 참조되고 있는 값은 바뀔 수 있습니다.

---

1. 배열로 스택 표현하기

배열의 단점인 중간 요소 추가, 삭제 로직이 사용되지 않으므로 스택을 배열로 표현하는 것은 매우 유리한 방식이다. 특히 자바스크립트에서는 배열의 크기가 자동으로 증감되도록 설계되었기 때문에 더욱 유리하다.
자바스크립트의 배열에는 push, pop 메소드가 존재하므로 그냥 배열을 사용하면 된다.

stack = []

stack.push(1)
stack.push(2)
stack.push(3)
console.log(stack) // [1,2,3]

stack.pop() // 3
stack.pop() // 2
console.log(stack) // [1]

2. 연결리스트로 스택 표현하기

C, java와 같은 언어에서는 스택의 크기가 고정되지 않은 경우, 배열 대신 연결리스트를 사용하여 구현하는 경우가 많다. 이 경우 연결리스트의 head가 top이 된다.
기존 연결리스트 코드에서 head를 top으로 지정하고 제거 로직은 오직 top을 제거하는 방식으로 구현하면 된다.

class Node{
  constructor(value){
    this.value = value
    this.next = null
  }
}

class Stack{
  constructor(){
    this.top = null
    this.next = null
  }

  push(value){
    var node = new Node(value)
    this.next = this.top
    this.top = node
  }

  pop(){
    var value = this.top.value
    this.top = this.top.next
    return value 
  }
}

var stack = new Stack()
stack.push(1)
stack.push(2)
stack.push(3)
console.log(stack) // [1,2,3]
console.log(stack.pop()) // 3

---

큐

First In First Out 개념을 가진 선형 자료구조가 큐이다. Linear Queue & Circular Queue가 존재한다.
Circular Queue는 front와 rear가 이어져있는 큐로 이를 연결리스트를 구현했을 때 이점이 없다.

자바스크립트에서는 배열이 자유롭게 증감되므로 enqueue를 못하는 문제는 없지만, front or rear 인덱스 값이 무한정 커질 수 있다. 따라서 요소를 앞당기는 작업이 필요한데 이 작업에 선형시간 O(n)이 소요된다. 이 문제를 해결하기 위해 큐를 연결리스트로 구현할 수 있다. 연결리스트는 배열과 다르게 인덱스에 대해 고민할 필요가 없다.

Linear Queue 구현

1. 배열 구현

class Queue{
  constructor(){
    this.queue = []
    this.front = 0   // 인덱스 변수 
    this.rear = 0    // 인덱스 변수
  }

  enqueue(value){
    this.queue[this.rear++] = value 
  }

  dequeue(){
    var value = this.queue[this.front]
    delete this.queue[this.front]
    this.front += 1   // 인덱스가 커지는 문제가 생길 수 있음   
    return value 
  }

  size(){
    return this.rear - this.front // rear index - front index 
  }
}

var que = new Queue()
que.enqueue(1)
que.enqueue(2)
que.enqueue(4)
console.log(que.size()) // 3
console.log(que.dequeue()) // 1

❗shift 함수로 queue 구현 (X)
자바스크립트 배열에서 shift는 선형시간 O(n)이 소요되므로 큐에서 기대하는 로직이 수행되지 않는다.

---

2. 연결리스트 구현

class Node{
  constructor(value){
    this.value = value
    this.next = null
  }
}

class Queue{
  constructor(){
    this.front = null
    this.rear = null
  }

  enqueue(value){
    var node = new Node(value)
    if (this.front == null){
      this.front = this.rear = node 
    }
    else{
      this.rear.next = node 
      this.rear = node 
    }
  }

  dequeue(){
    var value = this.front.value
    this.front = this.front.next
    return value 
  }
}

var linear_que = new Queue()
linear_que.enqueue(1)
linear_que.enqueue(2)
linear_que.enqueue(3)
console.log(linear_que.dequeue()) // 1

Circular Queue 구현

1. 원형 큐는 큐의 크기가 지정되어 있어야 한다. (max size)
2. 큐에 데이터를 넣기 위해서 rear의 다음 위치를 계산해야 한다. rear에 1을 더하고 큐의 크기(max size)로 나눈 나머지 값이 rear의 다음 위치이다.
   큐의 크기로 나눈 나머지 값을 사용하는 이유는 rear, front가 큐의 크기를 벗어날 경우 다시 0번 인덱스부터 시작되도록 하기 위함이다.

class Queue{
  constructor(max_size){
    this.max_size = max_size // max size를 통해 큐의 크기를 제한 
    this.queue = []
    this.front = 0   // 인덱스 변수 
    this.rear = 0    // 인덱스 변수
    this.size = 0
  }

  enqueue(value){
    if (this.is_full()){
      console.log("queue is full")  // 큐가 꽉차면 값 추가 x 
      return 
    }
    this.queue[this.rear] = value 
    this.rear = (this.rear + 1) % this.max_size
    this.size += 1
    }

  dequeue(){
    const value = this.queue[this.front]
    delete this.queue[this.front]
    this.front = (this.front + 1) % this.max_size
    this.size -= 1
    return value 
  }

  is_full(){  // circular 큐가 꽉찼는지 확인하는 함수가 필요하다. 무한정 enqueue를 막음 
    return this.size === this.max_size  // true or false 
  }
}

const circular_que = new Queue(4)

circular_que.enqueue(1)
circular_que.enqueue(2)
circular_que.enqueue(4)
circular_que.enqueue(8)
circular_que.enqueue(16)  // queue is full

console.log(circular_que) // {max_size: 4, queue: Array(4) [1, 2, 4, 8], front: 0, rear: 0, size: 4} 

circular_que.dequeue() // 1
circular_que.dequeue() // 2
console.log(circular_que.size) // 2