TIL(37) 자료구조(Stack, Queue) 1.

10831 단어 자료구조TILTIL

자료구조 / 알고리즘 ✍🏻

자료구조📌


  • 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것
  • 데이터를 효율적으로 다룰 수 있는 방법을 모아 자료구조라는 이름을 붙였다.
  • 대표적으로 네가지의 자료구조로 나뉜다.
    • 스택(Stack), 큐(Queue), 트리(Tree), 그래프(Graph)
  • 특정한 상황에 놓은 문제를 해결하는데 특화
  • 많은 자료구조를 알아두면, 어떠한 상황이 닥쳤을 때 적합한 자료구조를 빠르고 정확하게 적용하여 문제를 해결 할 수 있다.
  • 자료구조는 배열(ARRay)이다.

⌨️ 데이터(data) : 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값
또한, 이름, 나이, 키 집 주소 혹은 유전자 DNA까지 데이터로 분류
그러나 데이터는 그 자체만으로 어떤 정보를 가지기 힘들기에 분석하고 정리하여 활용해야 데이터의 의미를 가질 수 있다.
데이터를 목적에 따라 구분, 분류하여 필요에 따라 특징을 잘 파악(분석)하여 정리하고, 활용 해야 한다.


Stack(스택)📍

  • 쌓다, 쌓이다, 포개지다 와 같은 뜻을 가지고 있다. 마치 접시를 쌓아 놓은 형태와 비슷한 자료 구조
  • 데이터(data)를 순서대로 쌓는 자료 구조
  • 특징은 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근

자료구조 정책 : LIFO(Last In Fist Out), FILO(First In Last Out)

  • 먼저 들어간 데이터(data)는 가장 나중에 나온다.

Stack의 실사용 예시

  • 브라우저 뒤로가기, 앞으로 가기 기능

Stack의 기본적인 코드

class Stack {
  constructor() {
    this.storage = {};
    this.top = 0; // 스택의 가장 상단을 가리키는 포인터 변수를 초기화 합니다.
  }

  size() {
    return this.top;
  }

// 스택에 데이터를 추가 할 수 있어야 합니다.
  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  }
	
// 가장 나중에 추가된 데이터가 가장 먼저 추출되어야 합니다.
  pop() {
    // 빈 스택에 pop 연산을 적용해도 에러가 발생하지 않아야 합니다
    if (this.size() <= 0) {
      return;
    }

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

Queue(큐) 📍

  • 줄을 서서 기다리다, 대기 행렬 이라는 뜻을 가진다.
  • Stack과 반대 개념
  • 데이터(data)를 주고 받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간차이를 극복하기 위해 임시 기억장치의 자료구조로 Queue를 사용하고, 이를 통틀어 버퍼(Buffer)라고 한다.

자료구조 정책 : FIFO(First In First Out), LILO(Last In Last Out)

  • 먼저 들어간 데이터(data)는 먼저 나온다.

Queue의 실사용 예시

  • 컴퓨터와 연결 된 프린터

    • 일반적으로 프린터는 속도가 느리다.
    • CPU는 프린터와 비교하여, 데이터를 처리하는 속도가 빠르다.
    • 따라서, CPU는 빠른 속도로 인쇄에 필요한 데이터(data)를 만든 다음, 인쇄 작업 Queue에 저장하고 다른 작업을 수행한다.
    • 프린터는 인쇄 작업 Queue에 데이터(data)를 받아 일정한 속도로 인쇄 한다.
  • 유튜브와 같은 동영상 스트리밍 앱을 통해 동영상을 시청할 때, 다운로드 된 데이터(data)가 영상을 재생하기에 충분하지 않은 경우가 있습니다. 이때 동영상을 정상적으로 재생하기 위해 Queue에 모아 두었다가 동영상을 재생하기에 충분한 양의 데이터가 모였을 때 동영상을 재생한다.

Queue의 기본적인 코드

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

  size() {
    return this.rear - this.front;
  }
	
// 큐에 데이터를 추가 할 수 있어야 합니다.
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
	
// 가장 먼저 추가된 데이터가 가장 먼저 추출되어야 합니다.
  dequeue() {
    // 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않아야 합니다
    if (this.size() === 0) {
      return;
    }

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

    return result;
  }
}

좋은 웹페이지 즐겨찾기