[TIL]Data Structure 01)stack, queue

Violet Lee·2020년 10월 22일
0

javascript

목록 보기
18/24

sprint achivement

  • 자료구조가 무엇인지 설명할 수 있다.
  • 여러가지 자료구조들을 설명할 수 있다.
  • 각 자료구조의 장/단점과 사용목적에 대해 설명할 수 있다.
  • 시간/공간 복잡도가 무엇인지 설명할 수 있다.
  • Big-O 표기법에 대해 설명할 수 있다.

자료(DATA)

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


컴퓨터의 언어

0과 1, 전기가 통하면 1, 안통하면 0.
-> 이 언어를 인간은 알아먹을 수 없기떄문에 '컴파일러'를 이용해 번역하기 시작.


데이터타입

8비트 = 1byte = 65라는 값
8비트 = 1byte = 66이라는 값

그러나 저 두 값은 a,b가 되기도 함.

=> 즉,

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

원시타입(primitive type)

  • 정수,실수
  • 문자
  • 논리(참,거짓)

사용자 정의타입

  • 구조체, 클래스 등..

자료구조(data structure)

  • 데이터타입: 하나의 데이터를 어떻게 해석할지 정의한것

    vs

  • 자료구조: 여러 데이터의 묶음을 어떻게 저장하고 '사용'할지 정의한것.

    ex) 배열. 차례차례 데이터들을 저장해놓은 자료구조. 스택,트리 등..

예) 우리에게 천만개의 데이터가 있는데, 그 중 우리가 원하는 데이터를 찾아야하는데,
그거를 배열에 넣어놨다면, 우리는 천만번의 검색을 통해 찾아야 함.

이것을, 방법만 다르게 한다면 최소 24번안에 찾을 수 있음. < 자료구조를 이용해서!


스택, 큐

study achivement

  1. 개념의 이해뿐만 아니라, 직접 자료구조를 구현해야 한다면, 어떻게 작성해야할지 생각해보기.
  2. 자료구조의 모양 추상적으로 그림 그려보기.
  3. 해당 자료구조가 갖고있는 property, method 찾아보기.
  4. 각 method는 어떻게 동작되고있는것인지 알아보고, 의사코드 작성해보기
  5. 블로그 플랫폼등에 TIL형식으로 기록하기

stack

쌓여있는 접시더미와 같이 작동한다. LIFO의 구조. === 후입선출의 구조.

자료구조  가져오기  추가하기  삭제하기
stack    O(n)     O(1)      O(1)

Queue

놀이공원에서 서는 줄과 같이 작동한다.
사람들이 맨 끝에 줄을 서고, 맨 앞에서부터 놀이기구에 탑승하는것과 같다,
FIFO구조. === 선입선출 구조


예제 01

function calc(expression) {
  // 1. 문자를 하나씩 검사한다.
  // 2. 숫자를 만나면 숫자를 스택에 푸시한다.
  // 3. 연산자를 만나면 스택에서 팝을 두 번 하고, 두 개의 숫자를 가지고 연산한다.
  // 4. 3의 연산 결과를 다시 스택에 푸시한다.
  // 5. 문자열이 끝날 때 까지 반복한다.
  // 6. 문자열이 끝나면 연산 결과 값을 리턴한다.
}



const result = calc("9 3 * 15 5 / + 2 -")
console.log(result);
  1. 9와 3을 넣고 *을 만나서 9, 3 pop되고, 스택에 27 들어가고,
  2. 5, 5를 넣고, 그리고 /를 만나서 15, 5가 pop되고, 3이 스택에 들어가고,
  3. 27과 3이 stack에 있는 상태에 거기에 +를 만나서, 27,3이 pop되고, 30이 스택에 들어가고,
  4. 2가 숫자라서 stack에 들어가서 현재 stack에는 30, 2 가 들어있는데, 거기서 -를 만나서,
  5. 30-2=28이 되어서, 30, 2 pop되고, 28이 들어가게된다. 최종결과값은 그래서 28이 됨.

예제 02

맨 앞 front index가 2이고 맨 뒤 rear index가 6인 요소?

Q) 그런데 어쩔때, 맨 앞 front index가 2일수가 있는 것이죠?

A) 예를들어 0, 1을 pop해서 맨 앞 fromt index가 2인 경우인 것이다..!
   꼭 pop의 경우가 아니더라도 어찌됐든 앞의 두 요소가 삭제돼버려서 뒤의 요소부터 있게된경우다!!

   그러므로 예를 들어 0,1,2,3,4,5,6 이 들어있다면
   맨 앞 front index가 2인 '2' 요소부터,
   2 3 4 5 6 총 5개가 남는것이다..!

오늘의 achivement
우선순위 큐 === 트리 ..? 검색해봐야 할 듯.

profile
예비개발자

0개의 댓글