7월 23일 (목)_Data Structures, Stack, Queue

오늘 학습 내용

1.  Data Structures 에 대한 이해

  오늘은 컴퓨터 학문에서 가장 기본이 되는 데이터 구조에 대하여 학습하였다.

자료란?

• 문자, 숫자, 소리, 그림, 영상, 단어 등의 형태로 된 의미 단위이다. 자료를 의미있게 정리하면 정보가 된다.

  우리는 컴퓨터를 사용하기 위해 명령과 데이터를 주게 된다. 이 때, 컴퓨터는 0과 1로 데이터를 받게 된다. 하지만 사람이 0과 1로 대화를 하기는 어렵기에 인간의 언어를 컴퓨터 언어로 번역하는 번역기인 컴파일러가 만들어 졌다.

컴파일러(compiler)란?

  특정 프로그래밍 언어로 쓰여 있는 문서를 다른 프로그래밍 언어로 옮기는 프로그램을 말한다. 그렇지만 아직도 컴퓨터에는 0, 1로 데이터가 저장된다. 이 저장된 데이터도 인간이 읽을 수 있게 Data Type을 지정한다. 이를 ASCII Table에 대입해 데이터를 읽을 수 있게 되었다.

Data Type란?

• 컴퓨터에 0과 1로 저장되어 있는 데이터를 인간이 사용하는 여러가지 데이터들의 종류로 해석하기 위한 장치
• 같은 이진 데이터라도 인간의 해석에 따라 다른 데이터가 될 수 있다.

Data Structure란?

• Data Type : 하나의 데이터를 어떻게 해석할지 정의한 것
• Data Structure : 여러 데이터들의 묶을을 어떻게 저장하고 사용할지 정의한 것  ex )  Array, Stack, Tree ...

2.  Stack, Queue 이해 및 구현

1)  Stack

 

 

 

 

자료 구조의 Stack 은 간단히 말해서

LIFO : last in, first out 방식을 말한다.

 

시간 복잡도

가져오기 : O(n)

추가 , 삭제 : O(1)

 

 

 

Stack 데이터 구조에 필요한 Method 3가지 (Size, Push, Pop)

1. 우선 새로운 Stack 데이터 구조를 만듬. 이후 데이터를 담을 수 있는 Storage 와 값을 추가 및 삭제 하는 위치인 Top 이 필요함.

 

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

 

2. Size

Stack에 현재 요소가 얼마나 들어있는지 알아보는 Method 이다. 탑의 높이를 말한다고 생각하면 될 듯 하다.

 

수도코드 - Stack 데이터의 this.top 값을 retrun 함

 

3. Push(element)

Stack 데이터의 최상단에 element를 추가하는 Method 이다. 이 때 중요한 것은 this.top 값을 증가

 

수도코드 - this.top의 값을 증가하고 storage 최상단(Top)에 element를 추가

 

4. Pop

Stack 데이터의 최상단의 element를 제거하고 그 값을 return하는 Method 이다. 이 때는 this.top 값을 감소

 

수도코드 - this.top의 값을 감소하고 최상단(Top)의 값을 return 한다. 감소 시 조건으로 this.top > 0 일 때만 감소 시킨다.

2)  Queue

 

 

 

자료 구조의 Queue 은 간단히 말해서

FIFO : first in, first out 방식을 말한다.

 

    시간 복잡도

    가져오기 : O(n)

    추가 , 삭제 : O(1)

 

 

Queue 데이터 구조에 필요한 Method 3가지 (Size, Enqueue, Dequeue)

1. 새로운 Queue 데이터 구조를 만듬. 이후 데이터를 담을 수 있는 Storage 와 값의 앞 과 뒤를 가르키는 Front, Back이 필요함.

 

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

 

2. Size

Queue에 데이터가 얼마나 들어가 있는지 알아보는 Method 이다. Front 와 Back의 차 값을 통해 알 수 있다.

 

수도코드 - Front - Back의 값을 return 함.

 

3. Enqueue(element)

Queue의 Back 측에 element를 추가하는 Method 이다. 이 때 this.back 값을 증가

 

수도코드 - this.back의 값을 증가하고 storage 뒤 측(Back)에 element를 추가

 

4. Dequeue

Queue의 Front 측에 element를 제거하고 그 값을 return 하는 Method 이다. 이 때 this.front 값을 증가

 

수도코드 - this.front의 값을 증가하고 storage 앞 측(Front)에 element를 변수에 넣은 후 그 값은 제거하고 이후 변수에 넣어두었던 값을 return 한다. 이 때 조건은 this.back과 this.front의 값이 같으면 안된다. 같을 시에는 각 값에 0을 대입한다.