Data Structure(1) Stack (스택), Queue (큐)

스택(Stack), 그리고 큐(Queue)는 모두 '자료구조'의 한 종류이다. 처리해야할 데이터가 많아졌을 때, 어떤 순서로 저장하고 처리해야할 지를 정해둔 방식이라고 할 수 있다. 간단히 말하면 스택은 가장 마지막에 쌓인 데이터를 먼저 처리하고, 큐는 가장 먼저 쌓인 데이터를 먼저 처리한다는 점에서 차이가 있다. 이렇게 데이터들을 임시 저장하는 가장 기본적인 자료구조인 스택(Stack), 큐(Queue)에 대해 좀 더 알아보자!

 

스택(Stack)

---

스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO — Last In First Out)으로 되어 있다.

스택(Stack)은 번역하면 '쌓다'라는 뜻이다. 뷔페에 가면 쌓여있는 접시들을 떠올려보면 이해하기 쉽다. 접시를 새로 쌓을 때는 맨 위에 올려놓고, 가져갈 때도 맨 위부터 가지고 가야한다. 이렇게 가장 마지막에 쌓인 데이터부터 가져갈 수 있고, 새로 저장할 때도 가장 마지막 부분에 쌓아야하는 데이터 구조를 '스택(Stack)' 이라고 한다. 스택 구조는 자료가 들어오고 나가는 입구가 딱 한 곳이고, 한 번에 하나의 데이터만 처리할 수 있다. 후입선출(LIFO, Last In First Out) 방식이라고 줄여부를 수도 있다.

 

 

 

메서드(Method)

1. push : 가장 위에 데이터를 쌓음 (할당된 공간이 꽉 차면 더이상 push 불가 = stack over flow)

2. pop : 가장 위에 있는 데이터를 삭제

3. size : 데이터의 개수를 알려줌

 

class Stack {
  constructor() {
    this.storage = {}; // 데이터들이 저장될 장소
    this.top = 0; // 가장 위에있는 데이터
  }

  push(data) {
    // this.storage 마지막data 뒤에 새data 추가
    // this.top은 새로운 data가 됨
  }

  pop() {
    // 마지막data를 다른 변수에 저장해둠
    // this.storage 마지막 data 삭제
    // this.top은 마지막 data 바로 앞의 data가 됨
    // 저장해둔 마지막data 반환
  }

  size() {
    // this.storage의 key나 value들이 담긴 배열 길이 반환
  }
}

 

스택의 push, pop, size 메서드

시간 복잡도 (Big-O)

✔️ 가져오기 : O(n)

✔️ 추가, 삭제 : O(1)

 

스택에 데이터를 추가하거나 삭제하는 데 걸리는 시간은 모두 O(1)이다. 맨 위에 있는 요소를 꺼내고 맨 위에 데이터를 쌓기 때문에 따로 요소들을 하나씩 확인할 필요가 없기 때문이다.

 

하지만 데이터를 가져오려면 O(n)의 시간이 걸린다. 빅오 표기법은 최악의 경우를 계산하는 방법인데, 스택에서 최악의 경우는 제일 아래있는 (가장 먼저 들어온) 데이터를 가져오는 경우이기 때문이다. 다시말해 위에 쌓인 모든 데이터를 꺼내야 가장 아래있는 데이터를 가져올 수 있어서 n개의 데이터를 하나씩 스캔해야 한다.

 

추가로 스택은 재귀와도 관련이 깊은데, 지난번 글에 재귀 함수를 사용할 때 스택에 어떤 변화가 생기는 지 정리해둔 글이 있으니 참고하자.

 

 

 

큐(Queue)

---

큐(Queue)는 맛집 앞에 줄을 서있는 사람들을 떠올리면 이해하기 쉽다. 제일 먼저 온 손님부터 선착순으로 입장하는 경우와 마찬가지로, 가장 먼저 들어온 데이터를 가장 먼저 처리하는 방식을 큐(Queue)라고 한다. 스택과는 달리 자료가 들어오고 나가는 곳이 두 군데나 있다. 선입선출(FIFO, First In First Out) 방식이라고도 한다. 큐는 이처럼 어떤 작업을 순서대로 실행하거나, 사용을 위해 대기를 시켜야 하는 경우에 사용한다.

 

큐의 enqueue, dequeue 메서드

 

메서드(Method)

1. enqueue : 데이터 저장 (가장 최근에 저장된 값(rear) 바로 뒤에)   

2. dequeue : 데이터 꺼내기 (가장 오래전에 저장된 값(front)부터)

3. size : 데이터의 개수를 알려줌

 

class Queue {
  constructor() {
    this.storage = {}; // 데이터들이 저장될 장소
    this.front = 0; // 가장 오래전에 저장된data의 인덱스
    this.rear = 0; // 가장 최근에 저장된data의 인덱스
  }

  enqueue(data) {
    // this.storage 마지막data 뒤에 새data 추가
    // this.rear은 새로운 data가 됨
  }

  dequeue() {
    // front의 data를 다른 변수에 저장해둠
    // front data 삭제
    // front 바로 뒤에있던 data가 새로운 front가 됨
    // 저장해둔 front data 반환
  }

  size() {
    // this.storage의 key나 value들이 담긴 배열 길이
  }
}

 

시간 복잡도 (Big-O)

✔️ 가져오기 : O(n)

✔️ 추가, 삭제 : O(1)

 

큐(Queue)의 시간 복잡도는 스택(Stack)과 똑같다. 추가, 삭제는 맨앞이나 맨뒤에서만 진행되기 때문에 O(1)의 시간이 걸리고, 데이터를 가져올 땐 최악의 경우 n개의 데이터를 스캔해야 하기 때문에 O(n)이 걸리게 된다.

 

맨 마지막 데이터 뒤에 맨 앞 데이터가 연결되는 원형 큐(Circular Queue), enque시 데이터에 우선순위를 부여해 추가하고 dequeue할 때도 우선순위에 따라 데이터를 꺼내는 우선순위 큐(Priority Queue) 등 기본적인 큐를 응용한 다양한 형태의 큐가 존재하기도 한다.

 

(왼) 원형큐  (오) 우선순위 큐

 

 

 

이어서는 크기가 동적으로 변하는 연결리스트(Linked List), 키, 값 쌍을 함께 저장하는 해시테이블(Hash Table) 구조에 대해 소개하려고 한다.