[자료구조] 스택 stack 알아보기 With JavaScript

 

스택이란 ❓

그림 Stack

 

스택은 우리 실생활 속에서도 많이 사용되는 자료구조 중 하나입니다. 

 

예를 들면 웹 브라우저에서의 뒤로 가기, Ctrl+Z (Undo) 등 다양하게 쓰입니다.

 

스택은  "쌓다"라는 의미를 가집니다. 사전적 의미에서 알 수 있듯이 하나의 입구를 통해 push 하거나 pop 할 수 있습니다.

 

[그림 Stack]에서 볼 수 있듯이 메모리 stack 영역 맨 위에 데이터를 추가하는 것을 'push'라고 하고, 반대로 맨 위의 데이터를 하나씩 제거하는 것을 'pop'이라고 합니다.

 

즉 하나의 스택에 데이터를 계속 쌓는 형태이고, 가장 마지막 데이터가 먼저 나오는 Last-in First-Out(LIFO) 형태를 가지고 있습니다.

 

스택은 서로 관계가 있는 여러작업들을 연달아 수행하며 이전의 작업내용을 저장해 둘 필요가 있을 경우에 주로 사용됩니다.

 

Stack의 TOP & Bottom

 

TOP & Bottom은 스택의 특정 위치를 가리킵니다.

 

스택에 가장 최근에 push 된 데이터를 Top이라고 하며, 가장 처음에 스택에 push된 데이터는 Bottom이라고 합니다.

 

 

Stack의 Big-O

Insertion	O(1)
Deletion	O(1)
Search	O(n)

스택은 하나의 입구만 존재하기 때문에 삽입(push), 삭제(pop) 작업을 할 때 단 한 번만 하면 되기 때문에 시간복잡도는 항상 O(1)이 됩니다.

 

그러나 검색을 할 때는 스택의 맨 위(Top)에 원하는 데이터가 있다면 바로 찾을 수 있지만 맨 밑에 있다면 모든 자료를 검색해야 하기 때문에 시간 복잡도 Big-O는 O(n)으로 표현할 수 있습니다.

 

Hash Table 란 ❓

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

class Stack {
  constructor(){
    this.top = null;
    this.bottom = null;
    this.length = 0;
  }
  peek() {
    return this.top;
  }
  push(value){
    const newNode = new Node(value);
    
    if (this.length === 0) {
      this.top = newNode;
      this.bottom = newNode;
    } else {
      const holdingPointer = this.top;
      this.top = newNode;
      this.top.next = holdingPointer;
    }
    this.length++;
    return this;
  }
  pop(){
    if (!this.top) return null;
    if (this.top === this.bottom) {
      this.bottom = null;
    }
    this.top = this.top.next;
    this.length--;
    return this;
  }
}

const myStack = new Stack();
console.log(myStack);
myStack.push('A'); // 1
myStack.push('B'); // 2
myStack.push('C'); // 3
myStack.peek(); // 결과 : C
myStack.pop(); // 결과 : C
myStack.pop(); // 결과 : B
myStack.pop(); // 결과 : A