Computer Science/Data Structures11 2. Queue & Stack Queue Queue는 한글로 번역하면 줄이라는 뜻인데 줄을 서는 원리와 똑같이 동작하기 때문이다. 먼저 들어간 element가 먼저 나오는, First In First Out (FIFO) 형태를 갖는 자료구조이다. 따라서 index에 따라 넣고 빼는 것이 아닌 맨 뒤에 넣거나(enqueue), 맨 앞에서 빼는(dequeue) 것만 가능하다. Enqueue 위와 같이 리스트 형태로 구현된 queue가 있을 때, enqueue를 통해 노드를 추가하고 싶다면 추가할 새 노드를 만들어 준 뒤 맨 뒤 노드의 포인터를 새 노드로 지정해주면 된다. 이 때 마지막 노드의 포인터(tail)를 따로 저장해두지 않으면 처음부터 끝까지 탐색해야 하므로 미리 저장해두어야 한다. 따라서 언제나 위와 같이 상수 시간이 걸리므로 .. 2020. 5. 12. 1. Array & Linked List Array A ordered sequence of elements of the same type 배열이란 같은 형태의 요소들로 이루어진 자료구조를 말하며 다음과 같은 특징이 있다. - 각각의 element들은 index를 통해 참조한다. - 특정 순서에 따라 저장하기에 편리하다. - 미리 크기를 설정해주어야 한다. Search 배열은 i 번째 element를 찾을 때 시작 주소 + ( i × 자료형의 크기 ) 계산만 하면 위치를 찾을 수 있다. 따라서 탐색에 걸리는 시간이 상수이므로 시간복잡도는 O(1)이 된다. Insertion 위와 같은 배열에서 2와 6 사이에 4를 넣고 싶다면 뒤의 모든 element들을 한칸씩 뒤로 옮겨주어야 한다. 따라서 삽입에 element 갯수 n에 비례한 시간이 소모되므로.. 2020. 5. 12. 이전 1 2 다음
