자료구조란?

사전적의미로 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미.
즉, 여러 데이터의 묶음으로 데이터를 어떻게 저장 또는 사용할 것인가를 정의한 것이다.

방안에 따라 아주 다양한 방법이 있지만 그 중에 stack, queue를 우선 알아보았다.

자료구조를 배우는 이유는 특정 상황에 맞는 적합한 자료구조를 사용하여 문제를 해결할 때 정확하고, 최적의 코드를 작성할 수 있기 때문이다.
하여 자료구조들의 특징, 어떤 상황에 많이 쓰이는지, 자료구조 구현은 어떻게 하는지를 중점으로 공부하였다.

1. Stack

stack은 자료를 담아주는 자료형이고, 말 그대로 '자료(data)를 쌓는 구조'이다.

탑처럼 데이터가 수직으로 쌓여가는 모습을 상상해볼 수 있다.

stack 특징

• 선입후출 FILO(First In Last Out)
  가장 마지막에 추가한 자료(data)가 먼저나온다.

• 자료(data)에 제한적으로 접근 한다.
  가장 처음 담긴 데이터는 위에 쌓여있는 데이터가 다 빠져야 접근 가능하다.

• 중간 데이터는 확인할 수 없다.
  구조적 특징으로 중간 데이터에 뭐가 담겼는지 확인할 수 없다.

• 배열로 스택 구현시 데이터 크기를 미리 지정해야 하므로 저장공간의 낭비가 발생 할 수 있다.

• 구조가 단순해 구현이 쉽다.

• 데이터 저장/읽기 속도가 빠르다.

stack 사용 예제

• 브라우저 뒤로 가기, 앞으로 가기 기능을 구현시 활용
• 재귀 알고리즘
  재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 쌓을 수 있다.
• 역순 문자열 만들기

stack 구현 알고리즘

stack의 핵심은 후입선출이란 것이다. 그래서 가장 상단 데이터를 가르킬 수 있는 top이란 프로퍼티를 만들어 데이터 추가, 삭제시 마다 증/감해주는 식으로 데이터 크기를 확인할 수 있다.

class Stack {
  constructor() {
    this.storage: {},
    this.top = 0 // 스택의 가장 상단을 가리키는 포인터 변수를 초기화
  }
  
  size() {
    return this.top
  }
  
  push(element) {
    this.storage[this.top] = element
  	this.top++
  }
  
  pop(element) {
    // 빈 스택에 pop 연산을 적용해도 에러나지 않도록
    if(this.top <= 0) {
      return
    }
    
    const result = this.storage[this.top-1];
    delete this.storage[this.top-1];
    this.top -= 1;
    
    return result;
  }    
}

2. Queue

queue는 대기 행렬이란 뜻으로 '자료(data)를 나열하는 구조'이다. 한쪽 끝(rear)에서는 삽입만, 다른 한쪽 끝(front)은 삭제만 이루어진다.

queue는 자료(data)가 입력된 순서대로 처리해야 할 필요가 있을 때 사용된다.

queue 특징

• 선입선출 FIFO(First In First Out)
  stack과 반대되는 개념으로 먼저 들어간 자료(data)가 먼저 나온다.

• 배열로 큐 구현시 데이터 크기를 미리 지정해야한다.

• rear가 배열의 마지막 인덱스를 가르키면 queue에 공간이 있음에도 삽일 할 수 없다.
  삭제하면서 나머지 데이터가 앞쪽으로 이동하지 않으면 공간 낭비 발생

queue 사용 예제

• 컴퓨터와 연결된 프린터에서 문서 인쇄시 활용
  출력하기 버튼 -> Queue(임시 기억 장치)에 차례로 들어옴 -> 들어온 순서로 인쇄
  컴퓨터와 장치들 사이에 존재하는 속도의 차이나 시간차를 극복하기 위해 임시기억장치로 사용되며, 이것을 통틀어 버퍼(buffer)라고 한다.

📌 알고가기!
버퍼링(buffering)
대부분 컴퓨터 장치에서 발생하는 이벤트는 불규칙적으로 발생하는데 cup와 같이 발행한 이벤트 처리 장치는
일정한 처리 속도를 갖는다. 이 둘 사이의 차이를 버퍼를 사용해 해결 할 수 있다.

• 다른 예로, 유튜브 시청을 할 때의 버퍼링은 다운로드 된 자료(data)가 영상을 재생하기에 충분하지 않다면 순서대로 Queue에 모아 두었다가 충분한 양이 되었을 때 비디오를 복원하여 재생합니다.

• BFS(너비우선탐색)
  처리할 Node를 저장해야할 때 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++
  }
  
  dequeue(element) {
    if(this.size() === 0) return;
    
    let result = this.storage[this.front]
    delete this.storage[this.front]
    this.front++;
    return result;
}

Stack과 Queue Array로 구현

앞서 Stack과 Queue 구현한 것과 같이 class 키워드를 통해서 사용자 정의 데이터 타입을 만들 수도 있고, Array를 활용해서 만들 수 도 있다.

Array를 활용하면 사용자 정의를 통해 만드는 것 보다 시간 단축되고, 메서드로 stack과 queue와 유사하게 동작하도록 할 수 있다.

• Stack
  push()와 pop()
• Queue
  push()와 shift()