CS/DataStructure7

• 

  Stack and Queue Stack LIFO(Last In First Out) 구조.(입구/출구가 하나) 차곡 차곡 쌓이는 구조로 먼저 들어간 원소가 가장 먼저 나온다. 먼저 들어간 것이 먼저 나오는 것이 아닌 나중에 나온다. 활용예시 브라우저의 방문 기록 (뒤로가기) 역순 문자열 만들기(가장 마지막에 들어간 것이 마지막에 나온다) 실행 취소. 후의 표기법. 수식의 괄호 연산. 재귀 호출의 구조 방식. DFS Queue FIFO(First In First Out) 구조.(먼저 들어간 것이 먼저 나온다.) Stack 과 정반대로 입구/출구가 각각 따로 존재하며 1개씩 갖는다. 일상 생활에서 흔히 볼 수 있는 질서 있는 형식이다. 큐의 활용예시 프린터의 인쇄 은행 창구(먼저 와서 대기 순번을 발급받은 대로) 콜센터 고객 대기 시간 .. CS/DataStructure 2021. 3. 30.

• Array vs Linked List Array 논리적 저장 순서와 물리적 저장 순서가 일치.(index를 활용하여 해당 element에 접근 할 수 있다.) 해당 원소에 인덱스를 알고 있으면 O(1)이라는 시간 복잡도를 갖는다. Random Access가 가능하다. 하지만 삭제 또는 삽입과정에서 비용이 많이 발생한다. 해당 원소의 삽입 과정에서 맨 뒤의 경우를 제외하고 원소들이 있는 처음 또는 중간에 넣게 된다면 삽입할 공간을 만들기 위해 해당 원소들이 뒤로 이동해야하는 비용이 발생한다. 해당 원소의 삭제 과정에서 해당 원소를 삭제 한 후 빈 공간이 생긴다. 이 빈 공간을 매우기 위해 빈 공간 다음으로 이어지는 원소들을 한 칸씩 앞으로 떙겨야 하므로 비용이 발생한다. 비용에 대한 시간 복잡도는 O(n) 이다. Linked List 배열에 .. CS/DataStructure 2021. 3. 30.