[자료구조] Queue, Stack

Queue

기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다.
- wikipidia

• 먼저 들어간 것이 먼저 나가는 "선입선출"로, FIFO 구조를 가지고 있다.
• 삭제 연산이 수행되는 곳을 Front, 삽입 연산이 이루어지는 곳을 Rear로 FIFO 구조를 위해서 스텍과 다르게 큐의 한쪽 끝에는 삽입 작업이, 다른 한쪽 끝에서는 삭제 작업이 나뉘어서 이루어지고 있다.
• 큐는 Rear에서 이루어지는 삽입 연산을 Enqueue라고 부르며, Front에서 이루어지는 삭제 연산을 Dequeue라고 부른다.

Queue의 사용 사례

• 은행 업무
• 대기열 순서와 같은 우선순위의 작업 예약 등
• 서비스 센터의 대기 시간
• 프로세스 관리

Queue 구현해보기

• 데이터를 넣는 것을 enqueue라고 하며, 데이터를 꺼내는 과정을 dequeue라고 한다.
• Array를 통한 예시

// array를 통한 예시

const queue = [];

//enqueue - 순서대로 넣고
queue.push('seahorse');
queue.push('dolphin');
queue.push('whale shark');
queue; // ['seahorse','dolphin','whale shark']

//dequeue - 첫번째부터 꺼냄
const a = queue.shift(); //'seahorse'
queue; // ['dolphin','whale']

• Class Object를 통한 예시

//class를 통한 구현
class Queue {
  constructor() {
    this.storage = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(element) {
    this.storage[this.tail] = element;
    this.tail++;
  }

  dequeue() {
    let removed = this.storage[this.head];
    delete this.storage[this.head];
    this.head++;
    return removed;
  }
}

const queue2 = new Queue();

queue2.enqueue('seahorse');
queue2.enqueue('dolphin');
queue2.enqueue('whale shark');
queue2; // Queue { storage: { '0' : 'seahorse' , '1' : 'dolphin', '2' : 'whale shark' }, head: 0, tail: 3 }

queue2.dequeue(); //'seahorse'

queue2; // Queue { storage: { '1' : 'dolphin', '2' : 'whale shark' }, hea

Stack

스택은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝 먼저내기 목록(pushdown list)이라고도 한다.
스텍은 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO -Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다'하여 Push라고 하고 반대로 넣어둔 자료를 꺼내는 것은 팝(Pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 구조를 LIFO 구조라고 한다.
- wikipidia

Stack은 “쌓다”라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조이다. 위의 사진과 같이 데이터가 순서대로 쌓이며, 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조를 가지고 있다.

Stack은 정해진 방향으로만 쌓을 수 있으며, Top으로 정한 곳을 통해서만 접근할 수 있다. 새로 삽입되는 자료는 Tip이 가리키는 가장 맨 위에 쌓이게 되며, 자료를 삭제할 때도 top을 통해서 삭제가 가능하다.

Stack의 사용 사례

• 웹 브라우저 방문 기록(뒤로 가기)
• 실행 취소(undo)
• 역순 문자열 만들기
• 후위 표기법 계산

Stack 구현하기

• Push : 순서대로 데이터를 넣어준다.
• Pop : 가장 마지막 데이터를 꺼내고 제거
• peek : Stack에 쌓인 데이터의 가장 마지막 데이터를 보여주기만 하는 동작

// Array를 통한 Stack 구현
const stack = [];

stack.push('dog');
stack.push('cat');
stack.push('horse');

console.log(stack); // [ 'dog', 'cat', 'horse' ]
const a = stack.pop();
console.log(a); // hores
console.log(stack); // [ 'dog', 'cat' ]

// peek - stack에 쌓인 제일 마지막 요소를 보여주는 메서드
stack[stack.length - 1]; // 'cat'

// Class를 통한 Stack 구현

class Stack {
  constructor() {
    this.storage = {};
    this.size = 0;
  }

  push(element) {
    this.size++;
    this.storage[this.size] = element;
  }

  pop() {
    let removed = this.storage[this.size];
    delete this.storage[this.size];
    this.size--;
    return removed;
  }

  peek() {
    return this.storage[this.size];
  }
}

const classStack = new Stack();
classStack.push('hi');
classStack.push('hello');
classStack.push('안녕');

const b = classStack.pop();
console.log(b); // '안녕'
const c = classStack.peek();
console.log(c); // 'hello'

참조

https://jud00.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue%EC%97%90-%EB%8C%80%ED%95%B4%EC%84%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90

https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

https://velog.io/@nayeon/Data-Structure-Stack-Queue-in-JS