자료구조 - 스택(Stack)과 큐(Queue)

1. 스택(Stack)이란 무엇인가?

어떤 데이터의 구체적인 구현 방식은 생략한 채, 데이터의 추상적 형태와 그 데이터를 다루는 방법만을 정해놓은 것을 가지고 ADT(Abstract Data Type) 혹은 추상 자료형이라고 한다. 그 중 널리 사용되는 스택(Stack) 과 큐(Queue)가 있다.

이 두 자료구조는 자바스크립트(JavaScript)에 내장되어 있기 않지만, 배열(Array)과 내장함수들을 이용하여 스택(Stack)과 큐(Queue)를 흉내낼 수 있다.

대부분의 알고리즘 문제를 풀어야할 경우 배열을 이용하더라도 통과하는 편이지만, 시간 복잡도를 매우 세세하게 관리한다던가, 데이터의 양이 매우 큰 경우에는 이 같은 방식으로는 통과할 수 없는 경우가 있다. 이럴 경우에는 연결리스트(Linked list)로 직접 구현해야 할 수도 있다.

들어가기 전에 알아두기

• shift: 배열의 가장 첫 번째 원소를 제거하고 제거된 요소를 반환
• unshift: 배열의 앞쪽에 데이터를 삽입하고 삽입 된 배열의 길이를 반환
• pop: 배열의 가장 마지막 원소를 제거하고 제거된 요소를 반환
• push: 배열의 뒷쪽에 데이터를 삽입하고 삽입 된 배열의 길이를 반환

 

1) 스택(Stack)이란?

• LIFO(Last in, Last out)원칙으로 만들어진 선형 자료구조 - 나중에 들어온 데이터가 먼저 나간다.   
• 함수 실행 콘텍스트들이 쌓이는 Call stack과 브라우저의 방문 기록이 쌓이는 History stack이 대표적이다.
• 주로 함수 호출과 관련된 작업이나 임시 데이터 저장 등에 활용된다.
• 스택의 시간복잡도는 주로 삽입(push)과 삭제(pop)이기 때문에 O(1)이다. 
• Stack underflow는 스택이 비어있을 때 pop()을 시도할 때 발생하며, stack overflow는 스택이 가득 차 있을 때 push()를 시도할 때 발생다. 스택이 넘치는 상태를 나타내며, 이는 스택이 가득 차서 더 이상 요소를 추가할 수 없는 상태를 의미한다.

2) 메소드

• top : 스택 맨 위의 아이템
• push : 스택의 맨 위에 아이템을 삽입한다
• pop : 스택 맨 위의 아이템을 제거하고 그 아이템을 반환한다
• contains : 해당 아이템이 스택에 존재하는지 확인한다
• size : 현재 스택에 있는 아이템의 총 개수를 반환한다

3) 사용 사례

• 함수 실행 콘텍스트들이 쌓이는 Call stack
• 브라우저의 방문 기록이 쌓이는 History stack -> 웹 브라우저 방문기록 (뒤로가기)
• 재귀 알고리즘 -> 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다. -> 재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다. -> 스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다. 또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
• 실행 취소 (undo)
• 역순 문자열 만들기
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
  Ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기
• 후위 표기법 계산

 

4) 구현 방법

(1) 배열로 스택 (Stack)구현 - push, pop

class Stack {
  constructor() {
    // item들을 받을 배열 생성
    this.items = [];
  }

  push(item) {
    this.items.push(item);
  }

  pop() {
    return this.items.pop();
  }

  peek() {
    if (this.items.length === 0) {
      return null;
    }
    // items 배열의 마지막 item만 가져와준다. pop()과 다르게 배열에서 아이템이 빠지는 것이 아닌 유지된 채로 마지막 값만 받아와줌
    return this.items[this.items.length - 1];
  }

  getSize() {
    return this.items.length;
  }

  isEmpty() {
    return this.getSize() === 0;
  }
}

(2) 배열을 이용하지 않고 연결리스트(Linked List)방식으로 구현

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

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

  isEmpty() {
    return this.top === null;
  }

  push(data) {
    // 새로운 데이터를 받은 노드생성,
    const newNode = new Node(data);
    // 현재 최상위 노트(현재의 this.top노드) 기 새로 노드의 next가됨
    newNode.next = this.top;
    // 그리고 최상위 노드는 새로 들어온 newNode가 된다.
    this.top = newNode;
  }

  pop() {
    if (this.isEmpty()) return;
    // 최상단 노드가 pop()되면서 최상단 밑에있던 노드가 최상단 노드(this.top)가 된다.
    this.top = this.top.next;
  }

  peek() {
    if (this.isEmpty()) return -404;
    return this.top.data;
  }

  display() {
    if (this.isEmpty()) return;
    let curr = this.top;
    process.stdout.write("(TOP) ");
    while (curr.next) {
      process.stdout.write(`${curr.data} ---> `);
      curr = curr.next;
    }
    process.stdout.write(`${curr.data}\n`);
  }
}

 

 

2. 큐(Queue)란 무엇인가?

1) 큐(Queue)란?

• FIFO(First In First Out) 원칙으로 만들어진 선형 자료구조 - 선입선출, 먼저 집어넣은 데이터가 먼저 나온다. 
• 주로 작업 대기열, 데이터 버퍼링 등에 활용된다.
• 데이터를 집어넣는 enqueue, 데이터를 추출하는 dequeue 등의 작업을 할 수 있다.
• 큐의 시간복잡도는 shift()를 사용할 경우, 배열의 탐색이 필요하므로 최대 O(n)이다. 때문에 데이터량이 1000건 이하일 때는 shift()를 사용해도 무방하나 초과될 경우 Queue 알고리즘을 직접 구현하여 사용하는 것이 좋다.
• 스택 과 달리 항목은 대기열의 끝 (즉, 대기열 끝 )에 추가되고, 항목은 대기열의 시작 (즉, 대기열 시작) 에서 제거된다 . 항목은 제거될 기간이 되거나 제거되기 전에 모든 항목이 될 때까지 기다려야 한다.

2) 메소드

• first : 큐 맨 앞의 아이템
• dequeue : 큐 맨 앞의 아이템을 제거하고 및 그 아이템을 반환한다(shift)
• enqueue : 큐에 아이템을 추가한다(push)
• contains : 해당 아이템이 큐에 존재하는지 확인한다
• size : 현재 큐에 있는 아이템의 총 개수를 반환한다

3) 사용 사례

• 큐는 순서대로 처리해야 하는 작업을 임시로 저장해두는 버퍼(buffer)로서 많이 사용된다.
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 처리해야 할 노드의 리스트를 저장하는 용도로 큐(Queue)를 사용한다. -> 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다. -> 노드를 접근한 순서대로 처리할 수 있다.
• 캐시(Cache) 구현
• 우선순위가 같은 작업 예약 (인쇄 대기열)
• 선입선출이 필요한 대기열 (티켓 카운터)
• 콜센터 고객 대기시간
• 프린터의 출력 처리
• 윈도 시스템의 메시지 처리기
• 프로세스 관리

 

4) 구현 방법

(1) 배열로 큐(Queue) 구현 - shift, push

• dequeue()에서 shift() 를 사용해 간단히 구현할 수 는 있다. 하지만 shift()특성상 배열 맨 앞의 요소(0번째 요소) 를 삭제하게 되면 배열의 길이(length)만큼 기존 요소들을 앞으로 당겨줘야하므로 시간복잡도가 O(n)이 되어버린다. 정석대로의 큐(Queue)라면 시간복잡도가 O(1)이 되어야한다. 

class Queue {
  constructor() {
    // item들을 받을 배열 생성
    this.items = [];
  }

  enqueue(item) {
    this.items.push(item);
  }

  dequeue() {
    return this.items.shift();
  }

  peek() {
    return this.items[0];
  }

  getSize() {
    return this.items.length;
  }

  isEmpty() {
    return this.getSize() === 0;
  }
}

 

(2) 배열을 이용하지 않고 연결리스트(Linked List)방식으로 구현

• 따라서 성능을 신경써야 하는 경우라면, 선입선출(FIFO) 원칙을 따르면서 시간 복잡도를 O(1)로 유지하기 위해서 배열 대신 직접 연결 리스트(Linked List)를 사용하여 큐를 구현하는 것이 일반적이다.

class Queue {
  constructor() {
    this.queue = [];
    this.first = 0;
    this.last = 0;
  }
  enqueue(item) {
    this.queue[this.last] = item;
    this.last++;
  }

  dequeue() {
    if (this.first === this.last) {
      this.queue;
      return null;
    }
    let temp = this.queue[this.first];
    this.first++;
    return temp;
  }
}

 

 

✅ 알게된 점

1) 링키드 리스트 = 연결 리스트(Linked List)는 데이터 요소들을 노드(Node)라고 불리는 객체로 연결하여 데이터를 구조화하는 선형 자료구조다. 연결 리스트는 주로 데이터의 추가 및 삭제가 빈번한 상황에서 유용하게 활용된다. 다음과 같은 특징이 있다.

• 데이터 구조: 연결 리스트는 데이터 요소를 노드로 표현하며, 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성된다. 맨 처음 노드를 헤드(Head)라고 하며, 맨 마지막 노드의 포인터는 보통 null이 된다.
• 동적 크기: 연결 리스트는 동적으로 크기를 조정할 수 있다. 배열과 달리 연결 리스트의 크기는 데이터 요소의 추가 및 제거에 따라 자동으로 조정된다.
• 삽입 및 삭제: 연결 리스트는 데이터의 삽입 및 삭제가 비교적 빠르게 이루어진다. 데이터의 추가 및 삭제시에는 해당 위치에 새로운 노드를 생성하거나 이전 노드의 링크를 조정하여 구현한다.
• 메모리 사용: 연결 리스트는 데이터 요소들이 메모리 상에서 불연속적으로 저장되기 때문에 메모리 공간을 더 효율적으로 활용할 수 있다. 그러나 각 노드마다 포인터가 필요하므로 추가적인 메모리 사용이 필요하다.

 

2) slice와 splice의 시간 복잡도는 최악의 경우 O(N) 이다.

몇일 전에 알고리즘 풀이에 slice와 splice를 사용했었는데, 시간 초과가 발생했었다. 이 부분을 다른 방식의 코드로 수정하니 성공했다. 알고보니 slice와 splice의 시간 복잡도는 최악의 경우 O(N) 이라고 한다.

예를 들어, 배열의 중간에 요소를 삽입하거나 삭제하는 경우, 해당 위치 이후의 모든 요소를 이동시켜야 하기 때문에 작업량이 배열의 길이에 비례하여 증가한다. 또 배열 내부적으로 빈 공간을 줄이기 위해 배열 내부의 최적화 기술과 인덱싱 방식이라는 최적화 기술을 사용하는데, 배열의 크기보다 실제 저장된 요소의 개수가 적을 때, 메모리를 효율적으로 사용하기 위해 빈 공간을 제거하는 것을 의미한다. 이 최적화 기술을 사용하면 배열의 인덱싱 속도가 느려질 수 있다. 인덱스를 찾는 과정이 더 복잡해지기 때문이다.

정리하자면 주로 쓰이는 배열 메소드의 시간 복잡도는 다음과 같다.

• push -> O(1)
• pop -> O(1)
• shift -> O(N)
• slice -> O(N)
• splice -> O(N)

JavaScript runtime complexity of Array functions

 

3) 자바스크립트 배열은 전통적인 자료구조 배열과는 다르다.

(1) 자바스크립트 배열은 다이나믹하고 동적이다. 전통적인 배열은 동적이지 않으며, 배열의 크기도 미리 정해 놓고 공간을 변경시키지 않는다. 그에 비해 자바스크립트 배열은 동적인 크기를 가지고 있다. 자바스크립트 배열은 동적(dynamic)으로 크기가 조절되며, 배열의 크기를 미리 정해 놓지 않고도 요소를 추가하거나 제거할 수 있습니다. 이러한 특성은 배열을 다루는데 유연성을 제공하며, 필요에 따라 배열의 크기를 동적으로 조절할 수 있게 합니다.

(2) 자바스크립트는 배열 내부 요소의 타입도 변경 가능하고 undefined로 초기화도 가능하다. 여러가지 타입의 요소들을 담을 수 있다. 전통적인 배열의 경우 배열 내부의 타입 또한 변경 불가능 하다.

정리하자면, 정통적인 배열은 배열을 생성할 때 특정한 데이터 타입과 크기를 지정하며, 이후에는 그 크기와 요소의 타입을 변경할 수 없다. 반면에 자바스크립트 배열은 배열의 크기와 요소의 타입을 동적으로 조절할 수 있다. 이로 인해 자바스크립트 배열은 더 유연하게 데이터를 다룰 수 있지만, 동시에 타입의 변화나 크기의 변경이 예기치 않게 발생할 수 있어서 주의가 필요하다.