4.4Stacks and Queues

Stacks

LIFO(Last In First Out) 원칙을 따르는 데이터 구조들의 통칭. 쌓아놓은 책 더미처럼, 가장 마지막에 쌓은 것이 가장 먼저 처리되는 데이터 구조다. 이전에 본 콜 스택(Call Stack)이나 Undo/Redo 기능, 브라우저 히스토리의 routing 등이 스택의 대표적인 사례들이다.

자바스크립트의 built-in Array를 통해 스택을 만들 수 있다.

javascript
const stack = [];
stack.push("google"); // 1
stack.push("instagram"); // 2
stack.push("youtube"); // 3

stack.pop(); // "youtube"
stack.pop(); // "instagram"
stack.push("amazon"); // 2
stack.pop(); // "amazon"
// ...

물론, unshift를 통해 데이터를 추가하고 shift를 통해 데이터를 제거하는 방식으로도 스택을 구성할 수 있지만 index가 있는 Array의 특성상 비효율적인 방식이다.

사실 더 나아가자면, javascript의 built-in Array 자체가 index가 있는데 stack에는 굳이 필요하지 않으므로 위의 방식도 최선의 방식은 아니다. 따라서 한번 직접 javascript의 stack을 구현해보자.

앞서 우리가 함께 구현한 linked list의 방식을 사용하면 된다. 다만, pop의 경우 Singly Linked List에선 tail 정보가 없었기에 루프문으로 구성요소를 끝까지 훑어야했다는 단점(O(N))이 있으므로 O(1)로 만들기 위해선 맨 앞에 추가하고 맨 앞에서 제거하는 방식을 택한다.

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

class Stack {
  constructor(){
    this.first = null;
    this.last = null;
    this.size = 0;
  }
  push(val){
    const newNode = new Node(val);
    if(!this.first){
      this.first = newNode;
      this.last = newNode;
    } else {
      const temp = this.first;
      this.first = newNode;
      this.first.next = temp;
    }
    return ++this.size;
  }
  pop(){
    if(!this.first) return null;
    const temp = this.first;
    if(this.first === this.last){
      this.last = null;
    }
    this.first = this.first.next;
    this.size--;
    return temp.value;
  }
}

Stack의 Big O

삽입(Insertion)과 제거(Removal)이 모두 O(1)이라는 점이 Stack을 쓰는 이유다. 반면, Searching과 Access는 루프를 돌아야하기 때문에 O(N)인데, Search와 Access 및 보다 다양한 메소드를 사용한다면 Singly Linked List나 Doubly Linked List를 쓰는게 낫다.

Queues

FIFO(First In First Out) 원칙을 따르는 데이터 구조들의 통칭.

놀이동산에 선 줄처럼, 가장 처음에 들어온 것이 가장 먼저 처리되는 데이터 구조다. 컴퓨터의 백그라운드 태스크나 리소스 업로드, 프린터의 태스크 프로세싱 큐 등이 큐의 대표적인 사례들이다.

자바스크립트의 built-in Array를 통해 큐를 만들 수 있다.

javascript
const queue = [];
queue.push("FIRST"); // 1
queue.push("SECOND"); // 2
queue.push("THIRD"); // 3

queue.shift(); // "FIRST"
queue.shift(); // "SECOND"
// ...

물론, unshift를 통해 데이터를 추가하고 pop을 통해 데이터를 제거하는 방식으로도 큐를 구성할 수 있지만 index가 있는 Array의 특성상 비효율적인 방식이다.

따라서 큐도 직접 구현해보자.

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

class Queue {
  constructor(){
    this.first = null;
    this.last = null;
    this.size = 0;
  }

  enqueue(val){
    const newNode = new Node(val);
    if(!this.first){
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }
    return ++this.size;
  }

  dequeue(){
    if(!this.first) return null;

    const temp = this.first;
    if(this.first === this.last){
      this.last = null;
    }
    this.first = this.first.next;
    this.size--;
    return temp.value;
  }
}

Queue의 Big O

Stack처럼 삽입(Insertion)과 제거(Removal)이 모두 O(1)이라는 점이 Queue를 쓰는 이유다. Searching과 Access는 루프를 돌아야하기 때문에 O(N)인데, Search와 Access 및 보다 다양한 메소드를 사용한다면 Singly Linked List나 Doubly Linked List를 쓰는게 낫다.

---

🤠 개인 탐구

2개의 큐를 이용해 스택 구현하기

연습문제로, 2개의 큐를 이용해 스택을 구현하라는 것이 나왔다. Node와 Queue는 위에서 구현한 형태를 사용한다.

스택을 만든다는 것은 결국 가장 마지막에 추가(push)한 데이터가 가장 먼저 나와야(pop)한다는 의미다. 큐는 가장 먼저 추가한 데이터가 가장 먼저 나오므로, 두 개의 큐를 이용한다면 메인 큐에 데이터를 보관하되 추가할 땐 여기가 아니라 보조 큐에 데이터를 추가한 후, 메인 큐 데이터를 모두 보조 큐로 옮기고 보조 큐를 메인 큐와 스왑하면 된다. 이렇게 하면 pop은 그저 dequeue로 쉽게 구현할 수 있고, push만 따로 구현하면 된다.

javascript
class Stack {
    constructor() {
        this.q1 = new Queue;
        this.q2 = new Queue;
    }
    push(val) {
        this.q2.enqueue(val);
        while(this.q1.size > 0){
            this.q2.enqueue(this.q1.dequeue())
        }
        const temp = this.q1;
        this.q1 = this.q2;
        this.q2 = temp;
        return this
    }
    pop() {
        return this.q1.dequeue()
    }
}