Stack, Queue

최경락 (K_ROCK_)·2021년 12월 17일

선형구조(Linear)

Stack과 Queue는 데이터가 일렬로 연결된 선(line)과 같은 모양을 가진다고 하여 선형구조라고 불린다.

Stack

말의 뜻 그대로 데이터를 쌓는 모양을 가진다.
먼저 들어간 데이터가 가장 나중에 나오고, 나중의 데이터가 가장 먼저 나온다.
선입후출(FILO) 또는 후입선출(LIFO)
대표적으로 브라우저의 앞으로, 뒤로가기나, 문서의 되돌리기 등에 해당 구조가 사용된다.
→ React의 history 객체를 생각해봐도 될 듯.

class를 이용한 stack 구현

class Stack {
	constructor() {
    this.count = 0
    this.storage = {}
  }
  push(el) {
    this.count++ // 함수가 실행되면 count를 1추가한다.
    this.storage[this.count] = el // 인자를 storage 객체에 키값을 count로 하여 추가한다.
    return this.count // 현재 count를 리턴한다.(arr.push와 같음)
  }
  pop() {
    const removed = this.storage[this.count] // 현재 값을 변수에 저장한다.
    delete this.storage[this.count] // 현재 값을 지운다.
    this.count-- // 카운트를 1 뺀다.
    return removed // 변수로 저장해둔 현재값을 반환한다.(arr.pop와 같음)
  }
  peek(){
    return this.storage[this.count] // 현재값을 반환한다.
  }
}

let stack = new Stack()

stack.push('bye') // 1
// stack = {storage : {1 : 'bye'}, count : 1}
stack.push('hello') // 2
// stack = {storage : {1 : 'bye', 2 : 'hello'}, count : 2}

stack.pop() // hello
// stack = {{1 : 'bye'}, count = 1}

stack.peek() // "bye"

늘어나는 count 값을 key로 가진 객체를 구현하고, 해당 key를 활용하여 뒤에 있는 자료를 탐색하고, 지운다.

array를 이용한 stack 구현

let stack = []

stack.push(1) // [1]
stack.push(2) // [1, 2]
stack.push(3) // [1, 2, 3]
stack.push(4) // [1, 2, 3, 4]

stack.pop() // [1, 2, 3]
stack.pop() // [1, 2]
stack.pop() // [1]
stack.pop() // []

// 선입후출

Queue

queue 는 줄을 서서 기다린다는 뜻을 가지고 있다.
먼저 들어간 데이터가 먼저 나오고, 마지막에 들어간 데이터는 마지막에 나온다.
선입선출(FIFO) 또는 후입후출(LILO)
순차적으로 실행되어야하는 작업에서 사용된다.
→ 프린터가 문서를 프린트하는 순서를 결정할 때

class를 이용한 queue구현

class Queue {
  constructor () {
    this.storage = {}
    this.head = 0
    this.tail = 0
  }
  push(el) {
    this.storage[this.tail] = el // tail의 값을 키로 가진 객체를 추가한다.
    this.tail++ // tail의 값을 1 올린다.
    return Object.keys(this.storage).length // 현재 queue의 길이를 리턴한다.
  }
  shift(){
    let removed = this.storage[this.head] // 현재값을 변수에 저장한다.
    delete this.storage[this.head] // 현재값을 지운다.
    this.head++ // head의 값을 1 올린다.
    return removed // 저장한 현재값을 리턴한다.
  }
  peek(){
    return this.storage[this.head] // 현재값을 리턴한다.
  }
}

let queue = new Queue

queue.push('bye') // 1
// stack = {storage : {1 : 'bye'}, head : 0, tail : 1}
queue.push('hello') // 2
// stack = {storage : {1 : 'bye', 2 : 'hello'}, head : 0, tail : 2}

queue.shift() // hello
// stack = {storage : {2 : 'hello'}, head : 1, tail : 2}

queue.peek() // "bye"

뒤에 추가되는 값은 tail을 이용하여 구현하고, 앞에서 제거되는 값들은 head를 이용하여 해당 인덱스와 동일하게 늘려가면서 현재값의 인덱스와 맞춘다.

array를 이용한 queue 구현

let queue = []

queue.push(1) // [1]
queue.push(2) // [1, 2]
queue.push(3) // [1, 2, 3]
queue.push(4) // [1, 2, 3, 4]

queue.shift() // [2, 3, 4]
queue.shift() // [3, 4]
queue.shift() // [4]
queue.shift() // []

// 선입선출

버퍼(buffer)

처리속도가 다른 두 매개체 간의 데이터 교환시 속도와 시간차이를 극복하기 위해 자료를 임시적으로 저장하는 구조.
→ 임시 기억 장치가 테이터를 쌓아 저장할 때, 데이터를 queue 의 형태로 저장한다.
예를 들어 프린터가 문서를 출력할 때, 문서를 순서대로 전달하는 CPU는 일정한 속도로 빠르게 전송한다.
하지만, 프린터의 문서 출력은 그보다 시간이 오래걸리기 때문에, 전달된 문서를 임시 저장 장치에 queue의 형태로 저장하고, 순서대로 하나씩 처리한다.
→ 저장되는 데이터가 queue의 형태인 임시 저장 공간을 버퍼라고 한다.
만약, 버퍼에 쌓이는 속도가 처리속도보다 느려져 끊기게되면 그것이 버퍼링이다.