[데이터구조] Stack / Queue

Stack

순서가 있는 요소의 모음으로, LIFO(Last In First Out) 의 법칙을 따른다.

가장 나중에 들어온 요소가 끝에 붙고 가장 첫번째로 나가게 (삭제되게) 된다.

접시 쌓기와 같다고 생각하면 된다. 가장 위에 놓여있는 접시를 가장 처음으로 사용하게 된다.

 

스택은 수학적 모델이 아니라 행동으로 정의되는 추상적인 데이터 타입이다.

두 가지 동작을 하는데

 - push : 컬렉션에 요소를 추가한다.

 - pop : 컬렉션에 가장 마지막으로 추가 된 요소를 삭제한다.

 

스택을 사용할 수 있는 예시 상황

 - 브라우저 히스토리 추적

 - 타이핑을 취소할 때

 - 자바스크립트 런타임에서의 콜스택

 

Queue

FIFO (First In First Out) 법칙을 따르는 컬렉션이다. 먼저 추가된 요소가 가장 먼저 삭제된다.

큐의 두 가지 동작은

 - enqueue : 컬렉션의 끝에 요소를 추가한다. (end, rear, tail)

 - dequeue : 컬렉션의 가장 앞에서 요소를 제거한다. (front, head)

 

여기에 추가로 

 - peek: 가장 처음에 있는 요소를 삭제하지 않고 값을 가져온다.

 - isEmpty: 큐가 비어있는지 확인한다.

 - size: 큐의 요소의 개수를 가져온다.

 - print: 큐의 요소를 보여준다. 

 

큐를 사용할 수 있는 예시 상황

 - 프린터

 - CPU 태스크 스케쥴링

 - 자바스크립트 런타임에서의 콜백큐 큐

 

자바스크립트에서 Queue 적용하기 (배열)

class Queue {
	constructor() {
    	this.items = []
    }
    
    enqueue(element) {
    	this.items.push(element)
    }
    
    dequeue() {
    	return this.items.shift()
    }
    
    isEmpty() {
    	return this.items.length === 0
    }
    
    peek() {
    	if (!this.isEmpty()) return this.items[0]
        else return null
    }
    
    size() {
    	return this.items.length
    }
    
    print() {
    	console.log(this.items.toString())
    }
}

const queue = new Queue()
console.log(queue.isEmpty()) // true

queue.enqueue(10)
queue.enqueue(20)

console.log(queue.size()) // 2
queue.print() // 10, 20

console.log(queue.dequeue()) // 10
console.log(queue.peek()) // 20

 

배열을 통해서 queue를 적용했지만 shift 메서드를 사용하면 시간 복잡도가 O(n)이 된다.

시간 복잡도를 O(1)로 바꾸기 위해서 객체를 이용하여 queue를 적용할 수도 있다.

 

자바스크립트에서 Queue 적용하기 (객체)

class Queue {
	constructor() {
    	this.items = {}
        this.rear = 0
        this.front = 0
    }
    
    enqueue(element) {
    	this.items[this.rear] = element
        this.rear++
    }
    
    dequeue() {
    	const items = this.items[this.front]
        delete this.items[this.front]
        this.front++
        return item
    }
    
    isEmpty() {
    	return this.rear - this.front === 0
    }
    
    peek() {
    	return this.items[this.front]
    }
    
    size() {
    	return this.rear - this.front
    }
    
    print() {
    	console.log(this.items)
    }
}

const queue = new Queue()
console.log(queue.isEmpty()) // true

queue.enqueue(10)
queue.enqueue(20)

console.log(queue.size()) // 2
queue.print() // { '0': 10, '1': 20 }

console.log(queue.dequeue()) // 10
console.log(queue.peek()) // 20

 

 

Circular Queue

첫번째 요소가 마지막 요소에 연결된 것처럼 하나의 메모리 블럭이 사용되고, 큐의 사이즈는 정해져 있다.

FIFO 법칙에 따라서 마지막으로 들어온 요소가 첫번째로 나가게 된다.

 

dequeue 동작을 하면서 생성 된 빈 공간을 다시 사용한다. 따라서 dequeue 되지 않고 큐가 다 차게 된다면 더이상 enqueue 할 수 없다.

그래서 정해진 사이즈를 사용해야 하는 큐로 작업을 해야할 때 ciruclar queue를 사용하면 좋다.

 

 - enqueue

 - dequeue

 

추가로

 - isFull

 - isEmpty

 - peek

 - size

 - print

 

사용 상황 예시

 - 시계

 - 데이터 스트리밍

 - 신호등

 

자바스크립트에서 Circular Queue 적용하기 (배열)

class CircularQueue {
  constructor(capacity) {
    this.items = new Array(capacity)
    this.capacity = capacity
    this.currentLength = 0
    this.front = 0
    this.rear = 0
  }

  isFull() {
    return this.currentLength === this.capacity
  }

  isEmpty() {
    return this.currentLength === 0
  }

  enqueue(element) {
    if (!this.isFull()) {
      // 만약 Queue의 사이즈가 5인데 5를 넘어서 6이 될 경우, 나눈 나머지인 1로 다시 돌게 된다.
      this.rear = (this.rear + 1) % this.capacity
      this.items[this.rear] = element
      this.currentLength += 1
      if (this.front === 0) {
        this.front = this.rear
      }
    }
  }

  dequeue() {
    if (this.isEmpty()) {
      return null
    }

    const item = this.items[this.front]
    this.items[this.front] = null
    this.front = (this.front + 1) % this.capacity
    this.currentLength -= 1
    if (this.isEmpty()) {
      this.front = -1
      this.rear = -1
    }

    return item
  }

  peek() {
    if (!this.isEmpty()) return this.items[this.front]
    return null
  }

  print() {
    if (this.isEmpty()) console.log('empty')
    else {
      let i
      let str = ''

      for (i = this.front; i !== this.rear; i = (i + 1) % this.capacity) {
        str += this.items[i] + ' '
      }

      str += this.items[i]
      console.log(str)
    }
  }
}

const queue = new CircularQueue(5)
console.log(queue.isEmpty()) // true

queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
queue.enqueue(40)
queue.enqueue(50)

console.log(queue.isFull()) // true
queue.print() // 10 20 30 40 50

console.log(queue.dequeue()) // 10
console.log(queue.peek()) // 20

queue.print() // 20 30 40 50
queue.enqueue(60)
queue.print() // 20 30 40 50 60