TIL 08. Data Structure01. Stack, Queue

five1star·2020년 9월 3일

CODESTATES datastructure queue stack 스텍 자료구조 큐

TIL

목록 보기

8/25

Codestates Immersive 두 번째 스프린트는 바로 Data Structure!
오늘부터 다음주 화요일까지 무려 주말 제외 4일이나 진행되는 스프린트다. 지금까지 중에서 가장 긴 스프린트다.
오늘부터 Data Structure를 4개의 파트로 나누어 학습한다. 오늘은 그 중 Stack과 Queue를 학습.

Why do we need Data Structures?

자료구조란 여러가지 데이터들의 묶음을 어떻게 저장하고 사용할지 정의한 것이다. 프리코스에서 주구장창 배우려고 노력한 배열도 자료 구조중 하나다.
쉽게 현대 사회가 정보가 과대한 시대라고 말한다. 정보를 어떻게 묶고, 어떻게 관리하는지에 따라 그 활용도는 무궁무진해진다. 단순히 모든 정보를 배열에 일렬로 담아서는 안되는 이유가 바로 여기에 있다.

let DATA = [1,2,3,4,5,6, (....),100000]

만약, 다음과 같이 10만개의 요소를 가진 배열이 있다고 가정했을 때, 이 배열에 특정 요소가 있는지 관리하기 위해서는 어떻게 해야할까? includes, find,혹은 filter를 쓰더라도 배열의 모든 요소를 훑어야 한다. 자료가 커질수록 관리 및 활용도가 떨어질 수 밖에 없다. 여기서 자료구조를 활용해야 하는 이유가 생긴다.

자료구조는 다양한 최적화된 형태로 데이터를 관리하여, 관리 및 문제 해결을 도모하는데 목적이 있다.

1. Stack

####1. STACK이란?
첫 번째로 살펴본 자료 구조는 Stack이다. Stack은 마치 쌓여있는 접시와 같은 형태를 취하고 있다.

스택의 형태는 아래가 막힌 과자통과 같다. 즉, 스텍 자료구조에 새로운 데이터가 쌓이면, 순서대로 위로 정렬이 되고, 형태에서 요소를 제거하면, 가장 마지막에 입력한 데이터부터 제거된다는 의미다. 가장 마지막에 들어온 것이, 가장 먼저 나간다는 의미로 이를

LIFO(Last In, First Out, 후입선출) 라고 부른다.

2. STACK, 어디서 쓰나?

Stack은 LIFO라는 특성으로 인해 여러 분야에서 활용이 가능하다. 가장 대표적인것은 바로 '뒤로가기'

같은 개념으로 프로그램상 UNDO를 하는것도 가능하며 역순 문자열, 재귀 알고리즘, 수식의 괄호 검사를 사용하는데 도움이 된다.특히 재귀 알고리즘의 경우, 리턴 전까지 재귀가 반복될수록 각 함수가 스택에 쌓인다. 스택에 쌓여있는 함수가 순서대로 pop된다. 연산자의 경우도 마찬가지다.

stack을 활용한 연산의 의사코드 예(계산기에서 활용 가능하다)

1) 인자로 숫자가 들어오면 push를 한다.
2) 연산자가 들어오면 연속 두 번 pop을 한다.(이전에 들어간 숫자를 꺼낸다)
3) pop한 숫자 두개를 두고 연산자로 계산을 한다.
4) 연산 결과를 push하고 1~3을 반복한다.
5) 마지막 인자까지 마치면 결과값을 리턴한다.

3. 클래스를 활용한 Stack 구현 의사코드

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

  size() { 
    this.top을 리턴한다.
  }

  push(element) { 
    // 1. top 숫자를 더해주고
    // 2. storage객체에 top을 키로, element를 벨류로 하는 prop를 추가한다.    
  }

  pop() { 
    //1. top이 0이면 0을 리턴한다.
    //2. storage 최상단의 prop를 삭제한다.  
  }
  
  peek(){ 
    //최상단에 위치한 데이터를 출력한다.
  }
  
  isEmpty(){ 
    // storage가 빈 객체면 true를 리턴한다.
  }
}

let newStack = new Stack;
newStack.push('a') 
newStack.size() // 1
newStack.peek() // 'a'
newStack.pop() // {1:'a'}
newStack.isEmpty() // true

2. Queue

####2. Queue란?
두 번째로 살펴본 자료 구조는 Queue다. 큐는 마치 마치 줄서기와 같이 작동한다.

큐는 데이터가 들어오면 순서대로 쌓이는것은 Stack과 동일하다. 다만 삭제할때 스택과 차이가 나는데, 스택이 나중에 들어온 데이터가 먼저 나가는 형태(LIFO)라면, 큐는 가장 먼저 들어온 자료가 가장 먼저 나가게 되는 FIFO(First In First Out,선입선출) 라고 부른다.

2. Queue, 어디서 쓰나?

Queue는 FIFO라는 특성으로 인해 다양한 곳에 사용된다.

가장 쉽게 생각할 수 있는 내용은 바로 접수번호다. 입력과 출력이 하나의 통로로 이루어져있다는 점에서 Stack보다 다양한 용도로 사용 가능하다.

4. 클래스를 활용한 Queue 구현

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

  size() {
  // storage의 프로퍼티의 갯수를 리턴한다.
  }

  enqueue(element) { 
    //만약, front와 rear의 num이 같으면, 두 숫자를 0으로 지정한다.
    //rear를 1 증가시키고, rear를 키값으로, el을 value로 객체에 추가한다.

  }

  dequeue() { 
    //만약, front와 rear의 num이 같으면, 두 숫자를 0으로 지정하고 0을 리턴한다.
    //아니라면(rear가 더 크다면)
    //front를 키값으로하는 prop를 삭제하고 리턴한다.
    //front를 ++해준다.
  }
}

let newQueue = new Queue;
newQueue.enqueue('a') 
newQueue.size() // 1
newQueue.dequeue() // {1:'a'}
newQueue.size() // 0

생각해볼것.

1) 큐 사용시 메모리에 대해서. enqueue후 dequeue로 앞의 prop를 삭제하고 font와 rear가 같아지면, 앞에 있는 Num이 낭비된다. 위 의사코드를 통해서 두 숫자를 리셋해주었지만 prototype에는 남는다. 이를 해결하기 위한 방법.
2) 원형이나 순환 큐, 우선순위 큐에 대해서