TIL 61일차 - [자료구조/알고리즘] Stack & Queue

자료구조는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는
자료의 조직, 관리, 저장을 의미한다.
따라서 자료구조를 많이 아는 개발자일수록 데이터를 체계적으로 저장하고,
효율적으로 활용할 줄 알게 된다.
문제들을 해결하기 위해 자료구조를 많이 알게 되면,
특정 문제를 해결하는 데에 가장 적합한 자료구조를 빠르게 찾을 수 있게 되므로,
문제를 빠르고 정확하게 해결할 수 있게 된다.
앞서 배운 알고리즘과 자료구조는 밀접한 연관성이 있다.
즉 자료구조를 많이 아는 개발자란, 알고리즘 로직 또한 잘 짜는 개발자라고 볼 수 있을 것이다.

들어가기에 앞서 check 해보기

• JavaScript 기초 문법 및 고급 문법을 활용할 줄 알아야 한다.
  JavaScript 기초 문법 및 고급 문법은 코딩 테스트에 임하기 위해 필수 불가결한 것들이다.
  코딩 테스트는 결국 문제의 요구사항을 정확히 분석하여
  해당 요구사항을 만족하는 로직을 익숙하게 다룰 수 있는 프로그래밍 언어로 작성해야 하기 때문이다.
  알고리즘 로직을 짤 때는 해당 개념들을 주로 이용하게 된다.

  ☑️ 기초 제어문
  ☑️ 조건문
  ☑️ 문자열
  ☑️ 반복문
  ☑️ 배열
  ☑️ 객체
  ☑️ 고차함수
  ☑️ 재귀

  이러한 자료구조와 자료구조를 이용하여 해결할 수 있는 문제를 다루며 문제 해결 능력을 기르게 될 것이다.

• 자료구조에 대해 이해한다.

  o
  자료구조란 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것이다.

• 자료구조의 특징에 대해 이해한다.

  o
  자료구조는 특정한 상황에 놓인 문제를 해결하는 데에 특화되어 있다.

• 자주 등장하는 자료구조가 무엇인지 이해한다.

  o
  자주 등장하는 자료구조로는 스택, 큐, 트리, 그래프가 있다.
  

• 스택의 구조와 특징에 대해 이해한다.

  o
  데이터(data)를 순서대로 쌓는 자료구조를 의미하며, 프링글스 과자통에 비유할 수 있다.
  맨 처음 넣은 과자를 가장 먼저 뺄 수 없는 구조로, 가장 마지막에 넣은 과자 순서대로
  꺼낼 수 있다. 따라서 스택은 맨 처음 넣은 것은 가장 나중에 꺼내는 선입후출인 FILO(First In Last Out) 혹은 가장 나중에 넣은 것은 가장 먼저 꺼내는 후입선출인 LIFO(Last In First Out)의 특징을 가지고 있다.

  Stack에 데이터를 넣는 것을 'PUSH', 데이터를 꺼내는 것을 'POP'이라고 한다.

• 스택의 실사용 예제를 보고, 스택이 어떻게 이용이 되는지 이해한다.

  o
  자주 사용하는 브라우저의 '뒤로 가기', '앞으로 가기' 기능을 구현할 때
  자료구조 Stack이 활용한다.

  1. 새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack에 보관한다.
  2. 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때는,
     현재 페이지를 Next Stack에 보관하고,
     Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져온다.
  3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때는,
     Next Stack의 가장 마지막으로 보관된 페이지를 가져온다.
  4. 마지막으로 현재 페이지를 Prev Stack에 보관한다.
     이렇게 자료구조 Stack을 이용하면, 뒤로 가기와 앞으로 가기 버튼을 구현할 수 있다.

• 직접 구현한 스택이 어떤 식으로 동작하는지 이해하고,
  JavaScript 배열의 어떤 메서드를 사용해야 하는지 안다.

  o
  Stack에 데이터를 넣는 것을 'PUSH', 데이터를 꺼내는 것을 'POP'이라고 한다.

• JavaScript의 배열과 스택은 어떤 차이가 있는지 이해한다.

  o

• 큐의 개념과 구조, 특징에 대해 이해한다.

  o
  큐(Queue)는 줄을 서서 기다리다, 대기행렬이라는 뜻을 가지고 있다.
  큐는 톨게이트를 지나가는 자동차에 비유할 수 있다.
  톨게이트를 Queue 자료구조, 자동차는 데이터(data)로 비유할 수 있다.
  Queue는 Stack과 반대되는 개념으로,
  먼저 들어간 데이터(data)가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out)을 특징으로 가지고 있다.

  Queue에 데이터를 넣는 것을 'enqueue', 데이터를 꺼내는 것을 'dequeue'라고 한다.

• 큐의 실사용 예제를 보고, 큐가 어떻게 이용이 되는지 이해한다.

  o
  컴퓨터와 연결된 프린터에서 여러 문서를 순서대로 인쇄할 때 사용된다.

  1. 문서를 작성하고 출력 버튼을 누르면,
     해당 문서는 인쇄 작업 (임시 기억 장치의) Queue에 들어간다.
  2. 프린터는 인쇄 작업 Queue에 들어온 문서를 들어온 순서대로 인쇄한다.

  컴퓨터(출력 버튼) - (임시 기억 장치의) Queue에 하나씩 들어옴 - Queue에 들어온 문서를 들어온 순서대로 인쇄

• 직접 구현한 큐가 어떤 식으로 동작하는지 이해하고,
  JavaScript 배열의 어떤 메서드를 사용해야 하는지 안다.

  o
  Queue에 데이터를 넣는 것을 'enqueue', 데이터를 꺼내는 것을 'dequeue'라고 한다.

• JavaScript의 배열과 큐는 어떤 차이가 있는지 이해한다.

  o

실습

• JavaScript로 사용자 정의 데이터 타입을 만들어 내는 여러 방법 중에서,
  ES6 문법 중 하나인 class 키워드로 사용자 정의 데이터 타입을 만들고,
  Stack과 Queue의 데이터 타입을 정의한다.
  이렇게 생성한 사용자 정의 데이터 타입은
  Stack과 Queue을 Array와 object처럼 사용할 수 있다.

• 사용자 정의 데이터 타입으로 Stack을 정의하면,
  new 키워드를 통해 새로운 객체(인스턴스)를 만들 수 있다.
  그리고 생성한 인스턴스를 통해 다양한 메서드를 사용할 수 있다.

소감

🔡➡️💻➡️🤓👍

개념을 이해하는 것은 어렵지 않았지만,
스택과 큐를 이용하여 코드를 구현하는 것은 쉽지 않았다.
차근차근 순서대로 생각하여 코드를 구현하라고 하는데
아직 정확한 감이 잡히지를 않는다.