스택

스택

스택은 LIFO(Last In First Out)의 개념의 선형 자료형이다.
맨 위에 있는 요소를 Top 맨 아래 요소를 Bottom이라 한다.

스택 메모리

function sum(a,b) {
  return a + b;
}

function print(result) {
  console.log(result);
}

print(sum(2,4));

코드는 위에서 부터 아래로 실행되기 때문에 맨 처음에 있는 sum함수가 실행되며 sum함수가 스택 메모리가 들어옵니다. stack 메모리에 push가 된다.
sum함수에는 지역 변수, 반환 주소 값, 매개 변수를 가지고 있다.
sum함수가 return을 통해 실행을 마치면 stack 메모리에서 pop이 된다.

이후 print함수가 실행된다. print함수 또한 스택 메모리에 push가 된다.
현재 스택 메모리에는 print함수가 있다. 이후 print함수 안에 있는 console.log가 실행되며 console.log가 스택 메모리에 push가 된다. console.log를 통해 값을 출력했으면 console.log는 pop이 실행되어 스택 메모리에는 print함수만 남게된다.
마지막으로 print도 함수 호출이 완료되면서 스택 메모리에서 pop이 된다.

배열로 Stack 구현

const stackArr = [];

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

stackArr.pop();
stackArr.pop();
console.log(stackArr) // [1]

// Top 구하기
console.log(stackArr[stackArr.length - 1]) // 1

연결 리스트로 Stack 구현

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

class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }
  
  push(value) {
    const node = new Node(value); // 새 연결리스트 생성
	node.next = this.top;
    this.top = node;
    this.size += 1;
  }
  
  pop() {
    const value = this.top.value;
    this.pop = this.top.next;
    this.size -= 1;
    return value
  }
  
  size() {
    return this.size;
  }
}

const stackList = new Stack();
stackList.push(1);
stackList.push(2);
stackList.push(3);
console.log(stackList); // 
console.log(stackList.pop()); // 3
stackList.push(4);
console.log(stackList.pop()); // 4
console.log(stackList.pop()); // 2

stackList 결과

연결리스트의 Head를 스택의 Top으로 만들어주고 pop의 경우 연결리스트의 Head만 수정하면 된다.