10월 22일 TIL DataStructure : Stack, Queue

feelslikemmmm·2020년 10월 26일

TIL

목록 보기

24/36

Stack

스택이란 자료구조는 사전적 정의인 '쌓다' '더미' 와 같습니다. 쉽게 설명하자면, 밑이 막힌 상자를 생각하시면 됩니다. 밑이 막혔으니 위로만 물건을 집어 넣을 수 있고, 뺄 수가 있겠죠? 이러한 구조 때문에 먼저 들어온 물건은 나중에 나갈 수 있고, 나중에 들어온 물건은 먼저 나갈 수 있게 됩니다. 이러한 구조를 '선입후출' '후입선출' 이라고 합니다.

자료구조를 공부하는 데 있어 코드로 구현하는 것도 중요하지만, 그보다 중요한 것은 자료구조를 어떻게 사용할지 아는 것이 더 중요합니다. 모든 자료구조는 [삽입],[삭제],[읽기]를 기본으로 가집니다. 따라서 앞으로 자료구조의 사용법은 이 세가지 위주로 알아보겠습니다.

스택 용도 및 예제

우리가 많이 사용하는 브라우저를 생각해봅시다. 인터넷 서핑을 하다가 뒤로가고 싶을 때, 뒤로가기 버튼을 사용합니다. '뒤로가기'버튼이 바로 스택으로 구현된 메쏘드(method) 중 하나입니다.

앞서 스택은 밑이 막힌 상자라고 하였습니다. 상자에 들어 갈 물건들은 그 동안 서핑하였던 인터넷 페이지들 입니다. 그러면 제일 마지막에 봤던 페이지는 가장 위에 쌓여져 있겠지요? (참고로, 우리 눈에 보여지는 페이지는 가장 위에 있는 페이지입니다.) 상자에 들어있는 물건을 빼는 것이 '뒤로가기'입니다. 즉 물건을 빼면 가장 최근에 본 페이지가 빠지겠지요. 그럼 가장 위에 쌓여져 있는 물건은 그 전에 봤던 페이지입니다. 따라서 '뒤로가기'버튼을 누르면 지금 보고 있는 페이지(스택의 최상위)가 빠져나가면서, 이전에 봤던 페이지가 보여지게 됩니다. 이렇게 '뒤로가기' 버튼은 스택의 구조로 구성되어 있습니다.

스택 사용법

push(element) - 요소를 스택의 최상단에 추가합니다.
pop() - 스택의 최상단에서 요소를 제거하고 반환합니다.
size() - 스택의 현재 요소 개수를 반환합니다.

스택 method 구현하기

class Stack {
  constructor() {
    this.storage = {};
    this.top = 0;
  }
  size() {
    //스택에 현재 몇개의 접시가 있는지 확인하는 로직
    if(this.top <= 0) {
      return 0;
    } else {
      return this.top;
    }
  }

  push(element) {
    if(this.top <= 0) {
      this.top = 0; //0보다 작을 경우 , 0으로 세팅
      this.storage[this.top] = element;
      this.top ++;
    }
    else {
    this.storage[this.top] = element;
    this.top ++;
    }
  }

  pop() {
    if(this.top < 0) {
      return;
    }
    delete this.storage[this.top];
    this.top--;
    return this.storage[this.top];
  }
}

module.exports = Stack;

Queue(큐)의 개념

먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식
Stack(스택)과 반대되는 개념
데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용

Queue(큐)의 종류

선형(큐)
- 크기 제한
- 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮김
원형(큐)
- 선형 큐의 문제점을 보완
- front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결하는 방식

Queue(큐)의 메소드

배열을 이용한 큐

getSize() : 큐의 크기를 반환
isEmpty() : 큐가 비어있으면 true, 비어있지 않으면 false 반환
isFull() : 큐가 가득 차있으면 true, 그렇지 않으면 false 반환
enqueue() : ((rear+1) % size)번째 인덱스에 데이터 추가
dequeue() : ((front+1) % size)번째 인덱스의 데이터 반환
toString() : 큐의 모든 데이터를 반환
clear() : 큐의 모든 데이터를 삭제

연결리스트를 이용한 큐

isEmpty() : 큐가 비어있으면 true, 비어있지 않으면 false 반환
enqueue() : 큐가 비어있으면 새로운 노드를 front와 rear로 선언, 비어있지 않으면 새로운 노드를 rear 노드의 next로 선언한 후 새로운 노드를 rear로 선언
dequeue() : front 노드의 데이터 반환 후 front 노드의 next를 front 노드로 선언
toString() : 큐의 모든 데이터를 반환
clear() : 큐의 모든 데이터를 삭제

Queue(큐) 메소드 구현

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

  size() {
    if(this.front === this.rear) {
      return 0;
    } else {
      return this.rear - this.front;
    }
  }

  enqueue(element) {
    //storage 제일 마지막 인덱스로 추가하는 함수
      this.storage[this.rear] = element;
      this.rear++;
  }

  dequeue() {
    //요소를 큐의 앞에서 제거하고 반환합니다.
    if(this.front === this.rear) {
      return this.storage;
    }
    let deleteEl = this.storage[this.front];
    delete this.storage[this.front];
    this.front++;
    return deleteEl;
  }
}

module.exports = Queue;