[Algorithm] Stack & Queue: 스택과 큐에 대해 알아보자!

😃 오늘은 스택과 큐에 대해서 알아보겠습니다! 

 

먼저,

자료구조는 데이터의 표현과 저장 방법을 의미합니다. 

알고리즘은 저장된 데이터를 처리하는 과정입니다. 

그러므로, 자료구조를 알아야 알고리즘을 배울 수 있습니다. 

 

자료구조 중 하나로 배열이 있습니다!

자료구조에는 연결리스트, 스택, 큐 등이 있지만, 배열이 이것들을 모두 표현할 수 있습니다.

 

한 예로, 연결리스트에 대해서 이야기해보겠습니다. 

연결리스트는 여러 개의 노드로 이루어져 있으며, 각 노드에는 데이터와 다음 노드의 주소를 담고 있습니다. 

 

1->2->3->4->5 라는 연결리스트가 있다면, '1, 2, 3, 4, 5'는 데이터고 '->'는 주소를 가리킵니다. 

연결리스트는 데이터를 추가/찾거나/제거하는 기능도 있어야 합니다.

 

 

 

 

링크드 리스트 스택 (출처: https://blog.hexabrain.net/210)

 

 

 

 

자바스크립트 배열로 표현해보면, [1, 2, 3, 4, 5]로 나타낼 수 있습니다. 숫자는 데이터며, array[0], array[1] 등은 데이터가 담긴 위치를 가리킵니다. push 메서드로 데이터 추가, splice메서드로 데이터 제거를 할 수 있습니다.

 

 

이렇듯, 오늘 배워볼 스택과 큐도 배열을 이용하고 있습니다. 

 

 

---

 

1. 스택(stack)

스택은 연결리스트인데 뒤로 넣고 뒤로만 뺄 수 있습니다. push와 pop만 할 수 있으며,

스택은 실행이 되는 특정한 순서를 따르는 선형적 데이터 구조입니다.

 

위에서 스택은 연결리스트로 뒤로 넣고 뒤로만 뺄 수 있다고 했는데..

스택의 구조를 보면 위에서 넣고 위에서 빼고 있습니다. 

 

 

 

그러면, 스택은 링크드리스트가 아닌가요? 

 

 

그건 아니고, 스택은 특정한 순서를 따르는 선형적 구조라고 했습니다!

스택을 옆으로 뉘어보면 어떨까요?

 

 

 

 

 

출처: https://lsh424.tistory.com/51

 

 

 

 

 

 

순서는 두 가지가 존재합니다.

 

첫째, LIFO(Last In First Out) : 마지막에 들어온 데이터가 먼저가 먼저 나가는 데이터 구조로, 흔히 후입선출 구조라고도 부릅니다. 둘째, FILO(First In Last Out) : 처음 들어온 데이터가 마지막에 나가는 데이터 구조로, 흔히 선입후출라고도 이야기합니다. 

 

 

 

 

출처: geeksforgeeks.org

 

 

 

 

3가지 기본 작업이 스택에서 수행됩니다. 

• Push : 스택 안으로 데이터를 넣습니다. 만약 스택이 꽉 찬 상태에서 데이터를 더 넣을 경우, Overflow condition(오버플로우 상태)라고 이야기합니다.
• Pop : 스택 안에 있는 데이터를 제거합니다. 아이템은 넣어진 역순으로 빠져나옵니다. 만약 스택이 비어있는 상태에서 데이터를 꺼내려는 경우, Underflow condition(언더플로우 컨디션)라고 이야기합니다. 
• Peek or Top : 스택의 꼭대기 요소를 반환합니다.
• isEmpty : 만약 스택이 비어있다면, true를 반환하고, 비어있지 않다면 false를 반환합니다.

 

 

이미지를 함께 보시면, 위에서 이야기한 스택의 3가지 기본 작업에 대해 표현하고 있습니다.

스택의 마지막 부분(꼬리 부분)에 Push를 통해 데이터를 넣고, Pop를 통해 데이터가 빠져나오고, 마지막에 있는 데이터를 Top이라고 부르는 것을 이야기하고 있습니다.

 

 

 

---

 

 

 

위에서 

꽉 찬 스택에 데이터를 더 넣을 경우, Overflow condition가 된다고 했는데,

이걸 보고 보통 StackOverFlow라고 합니다. 

근데, 여기서 생각을 해볼 부분이 있는 거 같습니다.

 

 

 

여기서 스택이 왜 꽉 찰까요?

 

 

 

제가 아는 자바스크립트 배열은 매우 큰!! 큰 데이터를 담은 배열이 아닌 이상, 꽉 찼다고 한 것을 본 적이 없는 거 같은데 말이죠.

 

왜냐하면, 스택은 크기를 고정해서 사용하기 때문입니다. 당연한 얘기지만, 고정된 크기의 스택에 데이터를 계속 넣어서 넘치게 되면, 다른 메모리 영역을 침범하게 됩니다. (StackOverFlow) 

 

 

 

여기서 우리는 배열과 스택을 따로 구분을 해야 합니다. (혼용 NoNo!!)

 

 

 

스택이라는 자료구조는

프로세스를 구성하는 4대 요소 중 하나이며, 함수의 호출에 관여합니다.

 

프로세스에는 4가지 메모리 영역이 있는데, 스택, 힙, 데이터, 코드 영역이 있습니다. 

 

 

 

 

 

스택 메모리 영역은

 

프로그램이 자동으로 사용되는 임시 메모리 영역입니다.

(지역 변수, 매개 변수, 리턴 값 같이 잠시 사용되고 사라지는 데이터를 저장하는 영역)

 

함수가 호출되면 생성되고 함수가 반환됩니다.

 

프로세스가 메모리에 로드되면서 스택 사이즈가 고정이 되어서, 런타임시 스택 사이즈를 바꾸지 못하게 되어 

결국, 스택의 크기가 고정이 됩니다.

 

 

 

스택의 예시

(1) 기호 짝 맞추기(Balancing of symbos)
예) 괄호의 짝이 맞는지 확인하는 문제

 

(2) 중위 표기법(Infix)에서

     후기 표기법(Postfix) or 전위 표기법(Prefix)으로 전환

 

(3) 포토샵 같은 에디터에서 사용하는 Redo-undo & 웹 브라우저에서 사용하는 앞으로 가기 / 뒤로 가기

 

(4) 히스토그램(histogram), 주가 스팬(stock span), 트리 순회(tree traversal), 하노이의 타워(Tower of Hanoi)와 같은 알고리즘

 

(5) 백트래킹(back tracking)은 알고리즘 설계 기법 중 하나로, 만약 길이 효율적이지 않다면, 다시 이전 상태로 돌아와 다른 길로 가는 체스와 같은 게임이나 미로 찾기 같은  Knight-Tour 문제, N-Queen 문제가 있다. 우리가 현재 상태로 다시 이전 상태로 돌아가기 위해서 이전 상태가 저장되어 있는 스택을 사용한다

 

(6) 그래프 알고리즘의 Topological 정렬과 Strongly Connected Components

(현대 컴퓨터의 메모리 리는 주로 작동 목적을 위해 스택을 사용한다. 컴퓨터에서 작동되는 프로그램은 각자 할당된 메모리가 있음)

 

 

 

 

다 공부가 필요한 예시처럼 보이네요... 😅😅

 

 

 

실생활 예시로는 무엇이 있을까요?

 

쌓인 접시, 프링글스, 포갠 손들, 책더미가 생각나네요..

 

다른 실생활 예시가 있는지 여러분도 생각해보세요!

 

 

 

뭔가 예시가 시시하게 끝나는 거 같아서, 자바스크립트와 관련 있는 예시를 가져와봤습니다!

 

바로 '콜 스택'이라는 놈인데요.

자바스크립트 동작 원리 - 이벤트 루프를 공부해보셨으면, 아래 이미지를 한 번쯤 보셨을 거 같아요~

 

 

출처: 구글

 

 

 

v8 엔진 영역을 보면, 힙과 스택을 볼 수 있는데요. 

힙은 메모리가 할당되는 부분이고, 콜 스택은 함수가 호출될 때마다, 실행 콘텍스트가 쌓이는 영역입니다.

먼저 호출된 함수의 순서에 따라, 스택에 쌓이게 됩니다! 

 

 

아래 코드는 예시이니 참고해보세요!

 

function first() {
  second();
  console.log('첫 번째');
}
function second() {
  third();
  console.log('두 번째');
}
function third() {
  console.log('세 번째');
}
first();
third();

출처: 제로초

 

 

 

구현

스택을 구현하는 두 가지 방법이 존재하는데,

배열(array)을 사용하거나 링크드 리스트(linked list)를 사용합니다.

코드를 통해 살펴보자!

 

스택을 배열을 사용할 경우

var Stack = (function() {
  function Stack() {
    this.top = null;
    this.count = 0;
  }
  function Node(data) {
    this.data = data;
    this.next = null;
  }
  Stack.prototype.push = function(data) {
    var node = new Node(data);
    node.next = this.top;
    this.top = node;
    return ++this.count;
  };
  Stack.prototype.pop = function() {
    if (!this.top) { // stack underflow 방지
      return false;
    }
    var data = this.top.data;
    this.top = this.top.next;
    // 예전 this.top의 메모리 정리
    this.count--;
    return data;
  };
  Stack.prototype.stackTop = function() {
    return this.top.data;
  };
  return Stack;
})();

 

호출 결과

var stack = new Stack();
stack.push(1); // 1
stack.push(3); // 2
stack.push(5); // 3
stack.pop(); // 5
stack.stackTop(); // 3

 

 

배열을 이용했을 경우의 장점과 단점(pros and cons)

장점: 구현하기 쉽다. 포함되지 않은 포인터로서 메모리는 저장된다.

단점: 다이내믹하지 않다. 런타임에 의해서 배열이 증가하거나 작아지지 않는다.

 

 

 

링크드리스트를 사용할 경우

var LinkedList = (function() {
  function LinkedList() {
    this.length = 0;
    this.head = null;
  }
  function Node(data) {
    this.data = data;
    this.next = null;
  }
  LinkedList.prototype.add = function(value) {
    var node = new Node(value);
    var current = this.head;
    if (!current) { // 현재 아무 노드도 없으면
      this.head = node; // head에 새 노드를 추가합니다.
      this.length++;
      return node;
    } else { // 이미 노드가 있으면
      while(current.next) { // 마지막 노드를 찾고.
        current = current.next;
      }
      current.next = node; // 마지막 위치에 노드를 추가합니다.
      this.length++;
      return node;
    }
  };
  LinkedList.prototype.search = function(position) {
    var current = this.head;
    var count = 0;
    while (count < position) { // position 위치만큼 이동합니다.
      current = current.next;
      count++;
    }
    return current.data;
  };
  LinkedList.prototype.remove = function(position) {
    var current = this.head;
    var before;
    var remove;
    var count = 0;
    if (position == 0) { // 맨 처음 노드를 삭제하면
      remove= this.head;
      this.head = this.head.next; // head를 두 번째 노드로 교체
      this.length--;
      return remove;
    } else { // 그 외의 다른 노드를 삭제하면
      while (count < position) {
        before = current;
        count++;
        current = current.next;
      }
      remove = current;
      before.next = remove.next;
      // remove 메모리 정리
      this.length--;
      return remove;
    }
  };
  return LinkedList;
})();

 

호출 결과

var list = new LinkedList();
list.add(1);
list.add(2);
list.add(3);
list.length; // 3
list.search(0); // 1
list.search(2); // 3
list.remove(1);
list.length; // 2

 

링크드리스트의 장점과 단점(pros and cons)

장점: 런타임에 의해 스택의 실행이 증가하거나 줄어듭니다.

단점: 포인터를 포함해야 하기 때문에 추가적인 메모리가 필요로 합니다. 

 

 

스택에 관련한 시간 복잡도

스택에서 사용되는 기본 작업들인 push, pop, isEmpty와 peek 메서드는 모두 O(1)의 시간 복잡도를 가집니다. 

 

 

 

 

---

 

 

2. 큐(Queue)

스택과 같이 큐는 같은 선형적 구조는 특정한 순서를 따릅니다.

순서는 FIFO(First In First Out) 선입선출입니다.

 

 

출처: https://devowen.com/211

 

 

스택과 큐의 차이점은 제거에 있습니다.

스택은 가장 최근에 추가된 데이터를 제거하지만, 큐는 가장 처음에 들어왔던 데이터를 삭제한다.

 

헷갈린다. 다시 이야기하면,

 

스택은 가장 마지막에 쌓인 데이터를 제거하고 큐는 가장 앞에 추가된 데이터를 삭제한다.

 

 

큐의 동작

주로 아래에 나오는 4가지 기본 동작에 의해 동작한다.

 

• Enqueue: 큐에 데이터를 추가한다. 만약 큐가 꽉 찼을 때, Overflow condition이 된다.
• Dequeue: 큐에서 데이터를 제거한다. 데이터는 들어온 순서대로 빠져나온다. 만약 큐가 비어져 있을 경우, Underflow condition이 된다.
• Front: 큐의 앞부분의 데이터를 가진다.
• Rear: 큐의 뒷부분의 데이터를 가진다.

 

쉽게 생각해서,

BTS 팬 사인회가 있어서, 많은 사람들이 줄을 서있습니다. 

사람들은 줄을 서고 줄에서 나갑니다. 

 

여기서 큐는 줄이라고 생각할 수 있고, 사람이 줄을 서는 것(Enqueue)과 줄을 빠지는 것(Dequeue)라고 볼 수 있습니다.

 

 

 

출처: geeksofgeeks

 

이미지를 함께 보시면, 위에서 이야기한 큐의 4가지 기본 작업에 대해 표현하고 있습니다.

 

스택에서는 제일 위를 가리키는 top이 있다면, 

큐에는 맨 처음을 가리키는 head와 맨 끝을 가리키는 rear, 두 개가 있습니다.

 

큐의 종류

큐를 구현하기 위해서, 우리는 두 가지 지표를 추적해야 합니다. - front(머리)와 rear(꼬리) 

 

우리는

rear에 데이터를 추가하고 (enqueue),

front에 데이터를 빼냅니다 (dequeue).

 

만약, 우리가 간단히 front와 rear의 지표를 증가시킨다면, 문제가 될 수 있습니다.

-> front가 rear에 (배열의 끝)에 도달할 수 있기 때문입니다. 

 

1. 순환 큐

여기에 대한 방법으로는 front와 rear를 circular Queue(순환 큐)(으)로 증가시켜주는 방법이 있습니다.

 

front와 rear가 연결되어 있는데요, 원래 1, 2, 3의 큐에선 3에서 끝나지만, 

순환 큐는 rear인 3에서 다시 front인 1로 넘어갑니다. 

 

 this.rear.next = this.front

 

 

출처: geeksforgeeks

 

순환 큐가 사용되는 이유는 메모리 관리 측면인데, 

자바스크립트에서는 메모리를 알아서 정리해주기 때문에, 효용성이 조금 떨어진다고 합니다!

 

 

2. 우선순위 큐

우선순위 큐는 enqueue와 dequeue는 같지만,

enqueue 할 때, 제일 뒤에 넣는 것이 아닌, 우선순위를 따져 데이터를 넣습니다.

우선순위는 프로그래머가 직접 정해주면 됩니다.

 

다만, 우선순위 큐의 문제로, 보통 큐와 같이 구현하면 데이터를 삽입하기 힘들다는 단점이 있어,

주로 힙이라는 자료구조를 사용해서 구한다고 합니다.

 

출처: https://devowen.com/211

 

 

출처: https://devowen.com/211

 

큐의 예시

큐는 즉시 처리될 필요가 없을 경우 사용되지만, Breadth First Search(너비 우선 탐색)처럼 First In First Out 순서처럼 처리되어야 합니다. 또한, 큐의 속성은 아래와 같은 시나리오에도 유용합니다.

 

1) 여러 소비자 사이에서 자원이 공유될 경우
ex) Disk Scheduling, CPU Scheduling

 

2) 두 프로세스 사이에서 비동기적으로 데이터를 받을 경우
ex) IO Buffers, pipes, file IO, etc.

 

2-1)  IO Buffers 예시 : 프린터 - 인쇄를 요청한 순서대로 큐에 들어가, 순서대로 인쇄물이 출력

컴퓨터 장치들 사이에서 데이터(data)를 주고받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해
임시 기억 장치의 자료구조로 Queue를 사용합니다. 이것을 통틀어 버퍼(buffer)라고 합니다.

 

 

 

출처: 코드스테이츠

 

 

 

 

(왼쪽) CPU에서는 이벤트를 규칙적으로 처리합니다. (오른쪽) 대부분의 컴퓨터 장치에서는 이벤트가 불규칙하게 발생합니다.

출처: 코드스테이츠

 

 

 

컴퓨터와 프린터 사이의 데이터(data) 통신을 정리하면 다음과 같습니다.

• 일반적으로 프린터는 속도가 느립니다.
• CPU는 프린터와 비교하여, 데이터를 처리하는 속도가 빠릅니다.
• 따라서, CPU는 빠른 속도로 인쇄에 필요한 데이터(data)를 만든 다음, 인쇄 작업 Queue에 저장하고 다른 작업을 수행합니다.
• 프린터는 인쇄 작업 Queue에서 데이터(data)를 받아 일정한 속도로 인쇄합니다.

유튜브와 같은 동영상 스트리밍 앱을 통해 동영상을 시청할 때, 다운로드된 데이터(data)가 영상을 재생하기에 충분하지 않은 경우가 있습니다. 이때 동영상을 정상적으로 재생하기 위해 Queue에 모아 두었다가 동영상을 재생하기에 충분한 양의 데이터가 모였을 때 동영상을 재생합니다.

 

 

큐 구현하기

var Queue = (function() {
  function Queue() {
    this.count = 0;
    this.head = null;
    this.rear = null;
  }
  function Node(data) {
    this.data = data;
    this.next = null;
  }
  Queue.prototype.enqueue = function(data) {
    var node = new Node(data);
    if (!this.head) {
      this.head = node;
    } else {
      this.rear.next = node;
    }
    this.rear = node;
    return ++this.count;
  };
  Queue.prototype.dequeue = function() {
    if (!this.head) { // stack underflow 방지
      return false;
    }
    var data = this.head.data;
    this.head = this.head.next;
    // this.head 메모리 클린
    --this.count;
    return data;
  };
  Queue.prototype.front = function() {
    return this.head && this.head.data;
  };
  return Queue;
})();

 

큐 호출하기

var queue = new Queue();
queue.enqueue(1); // 1
queue.enqueue(3); // 2
queue.enqueue(5); // 3
queue.dequeue(); // 1
queue.front(); // 3

 

큐의 시간 복잡도

Enqueue (insertion) : O(1)

Dequeue (deletion) : O(1)

Front (Get front) : O(1)

Rear (Get Rear) : O(1)

 

보조 공간: input size를 고려하여 알고리즘이 문제를 해결하기 위해 임시로 사용하는 공간

: O(N)

 

 

배열로 큐를 구현할 때의 장단점

장점: 구현하기 쉽다.

단점: 사이즈가 고정되어 있다 (정적인 데이터 구조)

 

만약에 enqueue와 dequeue로 큐가 큰 숫자를 가졌다면, 큐가 비어있더라도 큐에 요소를 삽입하지 못할 수 있다. (순환 큐로 대처할 수 있다)

 

링크드리스트로 큐를 구현하는 게 더 쉽다. 

 

 

 

 

 

 

출처

코드 스테이츠 | null

제로초 | https://bit.ly/3fBRuoP

제로초 | https://bit.ly/3g1gswW

제로초 | https://bit.ly/3g5eoUW

배하람 블로그 | https://bit.ly/2RaCxkp

DevOwen | https://devowen.com/211

geeksforgeeks | https://bit.ly/3pdIIkb