배열(array)
1차원과 다차원배열이 존재
배열은 임의의 순서로 데이터를 읽을 수 있지만
데이터를 추가하거나 삭제하는 경우, 배열 내 다른 데이터의 순서(index)를 다시 매겨야 하므로 처리시간이 느림
리스트(list)
배열의 특별한 유형으로 단방향, 양방향, 순환연결 리스트(버퍼링에 주로 사용)가 존재
배열의 요소는 순차적으로 저장되지만, 리스트의 요소는 흩어진 상태로 메모리에 저장
리스트의 요소는 데이터와 포인터로 구성 (Node라 부름)
포인터는 리스트 내의 바로 다음 요소가 저장된 메모리 위치를 가리킴
마지막 노드는 다른 노드를 가리키지 않으므로 포인터는 Null값
스택(stack)
추가된 요소를 사용 가능한 메모리의 가장 앞 주소에 배치
LIFO, Last In First Out
동작은 같더라도 사용하는 기술이나 원하는 스택 종류에 따라 다양한 방식으로 구현가능
push, 스택에 요소 추가
pop, 마지막으로 추가된(맨 위) 요소 삭제
스택은 생성방식에 따라 데이터 구조의 크기나 규모가 고정된 정적 스택과 늘릴 수 있는 동적 스택으로 나뉨
정적 스택은 배열로 구현가능하며 동적 스택은 최상단 요소를 가리키는 포인터가 있는 단방향 연결 리스트로 구현
특정 요소를 검색하는 속도는 제한되지만 역추적이나 문자열 반전에 필요
외에도 함수 호출, 스케줄링, 인터럽트 메커니즘 등에 사용
큐(queue)
각 요소에 우선순위를 부여하는 데이터 구조의 한 종류
FIFO, First In First Out
비선형 데이터 구조의 큐도 존재
enqueue: rear가 가리키는 요소 다음, 가장 맨 뒤에 요소 추가
dequeue: front가 가리키는 가장 오랫동안 있던 요소 삭제
우선순위 큐(priority queue, 기본 큐를 확장)
키와 값의 체계를 사용해 큐의 요소들을 정렬
모든 요소는 우선순위가 존재하여 우선순위가 높은 요소가 큐에서 먼저 삭제
요소 추가하기, 삭제하기, 가장 높은 요소 가져오기, 큐가 가득 찼는지 확인하는 등의 메소드 필요
배열이나 연결 리스트를 사용하여 구현
알고리즘, 데이터 압축, 네트워킹 등 수많은 컴퓨터 과학 분양의 응용 프로그램에 사용