[자료구조] 선형구조(스택, 큐)

선형구조

스택 (Stack)

한쪽 끝 에서만 자료를 넣고 뺼 수 있는 자료구조이다.

이미지로 보는 스택(Stack)

• 가장 나중에 들어간 자료가 가장 먼저 빠져나오는 후입선출, LIFO(Last In First Out)라고도 부른다.
• 자바스크립트에서는 데이터 끝에 자료를 집어넣는 push()와 끝의 자료를 제거하는 pop()을 이용하여 스택을 구현할 수 있다.

자바스크립트 기본메소드를 사용하지 않고 구현하기

class Stack {
    constructor() {
        this.stack = [];
          this.index = 0;
    }
      push(ele) {
        this.stack[this.index++] = ele;
    }
      pop() {
        if (this.index <= 0) return null;
          const result = this.stack[--this.index];
          return result
    }
}

자바스크립트 기본 배열 메소드를 사용하여 구현하기

let stack = []

stack.push(1); // stack = [1]
stack.push(10); // stack = [1, 10];
stack.pop(); // stack = [1] 10 추출되어짐
stack.pop(); // stack = [] 1 추출되어짐

스택의 시간복잡도

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

 

큐

큐(queue) 구조

• 먼저 집어넣은 데이터가 먼저 나오는 선입선출, FIFO(First In First Out) 자료구조이다.
• 자바스크립트에서는 끝에 데이터를 집어넣는 push()와 처음 데이터를 꺼내오는 shift()를 사용하여 큐(queue)를 구현할 수 있다.

// 작성중

큐의 시간복잡도

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