[Algorithm] Data Structure and Algorithm Stack vs Queue

 

자료구조란?

 

자료구조란 여러 데이터들의 묶음을 저장 및 사용 방법을 정의한 것이다.

데이터란 실생활을 구성하고 있는 값을 의미한다. 잘 정리된 데이터는 새로운 인사이트를 만들어낼 수도 있고, 사용성을 높이기 때문에 데이터의 활용도를 높이기 위해 자료구조가 탄생하게 된다.

 

자료구조 종료 Data Structure

 

 

실생활에서 데이터를 효율적으로 사용하기 위한 방법인 자료구조는 알고리즘 문제에서도 자주 출제된다. 알고리즘 문제에서 자주 등장하는 자료구조는 Stack, Queue, Tree, Graph 4가지 종류다.

 

 

선형 자료구조 Stack

 

Stack 쌓아올리다 라는 뜻을 가지고 있다. 말 그대로 데이터를 입력된 순서대로 쌓아올리고 가장 위에서 부터 데이터를 출력하는 LIFO(Last In First Out) 형식을 취하고 있다.

스택의 특징

 

① 입력과 출력이 하나의 바향으로 이루어지는 제한적 접근이 이뤄진다.

② LIFO, FILO 형식을 취한다.

③ Stack 자료구조에서는 Push() 메소드로 데이터를 입력하고, Pop() 메소드로 데이터를 출력한다.

 

Stack 자료구조를 사용하는 가장 간단한 예시는 웹 브라우저에서 앞으로 가기와 뒤로 가기다. 브라우저에서는 현재 페이지를 Pre Stack에 보관하고 뒤로가기 버튼이 클릭되면 현재 페이지를 Next Stack에 저장하고 Pre Stack에 가장 나중에 보관된 페이지를 불러온다.

마찬가지 논리로 앞으로 가기 버튼이 클릭되면 Next Stack의 가장 마지막으로 보관된 페이지를 가져오고 현재 페이지를 Pre Stack에 저장한다.

 

Stack 자료구조 구현 소스코드

class Stack {
  constructor() {
    this.storage = {};
    this.top = 0; // 포인터 변수
  }

  // 스택 사이즈
  size() {
    return Object.keys(this.storage).length;
  }

  // 데이터 입력(Input)
  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  }
	
  // 데이터 출력(Output)
  pop() {
    if (this.top<=0) {
      return;
    }

    const result = this.storage[this.top-1];
    delete this.storage[this.top-1];
    this.top -= 1;
    
    return result;
  }
}

 

 

선형 자료구조 Queue

 

Queue는 줄을 서서 기다리다 라는 뜻을 가지고 있는 자료구조다. 즉 가장 먼저 입력된 데이터가 가장 먼저 출력되는 구조를 가진다. 흔이 Stack과는 반대의 개념으로 FIFO(First In, First Out) 혹은 LILO(Last In, Last Out) 형식을 취한다.

 

스택과 동일하게 입력과 출력의 방향이 고정되어 있다. 한가지 방향으로만 데이터가 입력되고, 한가지 방향으로 출력된다. Queue에 데이터를 입력하는 것을 enqueue라고 하며 데이터를 출력하는 것을 dequeue라고 한다.

 

큐(Queue) 자료구조의 대표적인 예로는 프린터 스풀링이 있다. 출력하고자 하는 문서는 임시 기억장치인 스풀에 저장되고 들어온 순서대로 프린팅된다. 임시로 기억되는 장치를 통틀어 버퍼(Buffer)라고도 한다. 각 데이터들의 불규칙적인 속도를 일정하게 유지하기 위해 버퍼(buffer)를 사용한다.

 

CPU에서는 이벤트를 규칙적으로 처리하게 되지만, 컴퓨터 장치에서는 CPU 속도를 따라가지 못하기 때문에 불규칙적인 이벤트를 일정한 속도로 처리하기 위해서는 버퍼(buffer)처럼 중간 완충장치가 있어야 한다.

 

유뷰튜같은 스트리밍 서비스에서도 다운로드 된 영상 데이터가 충분하지 않을 경우 재생을 하지 못하게 된다. 따라서 동영상을 재생하기 위한 충분한 데이터가 쌓일 때 까지 기다렸다가 재생하게 되는데 이때 데이터가 임시저장되는 곳이 Queue 자료구조를 가지게 된다.

 

큐의 종류

 

큐(Queue)는 일반 큐와 원형 큐로 구분된다.

 

큐(Queue) 자료구조 구현 소스코드 : 

 

class Queue {
  constructor() {
    this.storage = {};
    
    // Queue는 포인터가 앞 뒤로 2개가 존재함
    this.front = 0;
    this.rear = 0;
  }

  size() {
    return Object.keys(this.storage).length;
  }
	
	// 데이터 입력(Input)
    enqueue(element) {
      this.storage[this.rear] = element;
      this.rear += 1;
  	}
	
	// 데이터 출력(Output)
    dequeue() {
    if (this.front === this.rear) {
      return;
    }

    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;

    return result;
  }
}

 

 

[Javascript] Array Function some, sort, every 사용법

 

[Javascript] Function Expression vs Declaration 함수 표현식 vs 함수 선언식 차이점