큐(Queue)란 무엇인가? 큐는 먼저 입력된 자료가 먼저 출력되고 늦게 입력된 자료는 나중에 출력되는 선입선출(First In First Out: FIFO), 후입후출(Last In Last Out: LILO) 형태의 순차 자료구조이다. 순차 구조이기 때문에 논리적 구조가 순서를 가진 한줄로 표현할 수 있고 한쪽에서는 입력만 반대쪽에서는 출력만 되는 특징이 있다. #그림으로 설명 순차 리스트 또는 연결 리스트로 구현할 수 있는데, 각 종류의 리스트로 구현된 큐를 순차 큐, 연결 큐라고 하고 순차 큐는 다시 운영 방식에 따라 선형 큐, 이동 큐, 원형 큐로 구분된다. #표로 구분 선형 큐 리스트의 시작부터 끝까지 차례로 데이터를 추가하고 마지막 원소가 리스트의 끝에 도달하면 포화 상태라고 판단한다. 추가..

스택(Stack)이란 무엇일까? 한쪽에서만 자료를 넣을 수 있고 자료를 넣은 쪽에서만 자료를 꺼낼 수 있는 자료구조이다. 자료를 꺼낼 때 가장 최근에 넣은 자료부터 꺼낼 수 있다. 처음 넣은 자료 뒤에 또 다른 자료를 넣어버리면 처음 넣은 자료는 후에 넣은 자료들을 모조리 꺼낸 다음에야 꺼낼 수 있다. 이런 구조를 Last In First Out 줄여서 LIFO, First In Last Out 줄여서 FILO 혹은 후입선출, 선입후출 형식이라고 부른다. 예를 들어 인터넷 서핑을 하다 뒤로가기를 하는 것은 후입선출의 형식이다. 가장 마지막으로 방문한 사이트를(Last In) 뒤로 가기를 하면 처음으로 보여주니까(First Out) 여러 종류의 문서 작업 도중에 사용하는 Ctrl + z 도 같은 후입선출이..

배열(Array)이란? 인덱스와 인덱스에 대응하는 같은 타입의 데이터들로 이루어진 자료 구조를 뜻한다. 집합과 비슷하지만 원소들이 중복가능하지만 순서가 있고 리스트와 비슷하지만 데이터의 빈자리를 허용한다. 거의 모든 프로그래밍 언어에서 사용할 수 있는 가장 기초적인 자료 구조이며 다른 자료구조들의 부품으로 쓰이는 경우도 많다. 따라서 프로그래머라면 배열은 필수적으로 알고, 사용할 수 있어야 한다. #배열 이미지 추가 데이터를 연속적인 메모리 공간에 저장하므로 메모리 관리가 편하다. 인덱스를 식별자로 이용해 데이터에 접근하므로 배열의 데이터 접근 시간 복잡도는 O(1)이다. 배열은 자료에 대한 접근이 많은 경우에 사용하면 좋다. 배열은 인덱스를 식별자로 가지기 때문에 데이터가 삭제되어도 리스트처럼 빈자리를..

연결 리스트(Linked List)란? 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 데이터 구조이다. 여기서 노드(node)란 데이터 연결될 다음 데이터데 대한 주소를 저장하기 위한 의 단위구조를 말한다. 데이터의 값을 저장하는 데이터 필드(Data Field)와 다음 노드의 주소를 저장하는 링크 필드(Link Field)를 가진다. 따라서 순차 자료구조 방식과 다르게 데이터의 물리적 순서와 논리적 순서가 일치할 필요가 없다. #노드 구조 이미지 추가 . 선형 리스트와는 달리 노드의 중간지점에서도 자료의 삽입, 삭제 연산이 O(1)의 시간에 가능하다. 중간에 데이터를 삭제해도 노드의 링크 필드가 가지는 주소 값을 바꿔주면 다음 데이터와 연결할 수 있기 때문이다. ..

선형 리스트(Linear List)란? 선형 리스트란 순서를 가지고 일렬로 나열한 데이터의 모임이다. 가장 간단한 형태의 자료구조이다. 표현하고자하는 논리적인 순서와 실제 메모리상에 저장되는 물리적인 순서가 동일하다. 집합과 비슷하지만 데이터가 순서를 가지고 있다는 게 다르고 배열과 비슷하지만 인덱스 값이 식별자가 아니라는 것이 다르다. 배열은 인덱스 값을 식별자로 가지기 때문에 원소를 삭제했을 때 삭제된 데이터의 자리를 비워두는데 이런 구조가 메모리의 낭비를 유발한다. 반면에 리스트는 인덱스 값을 식별자로 가지기 않기 때문에 원소가 삭제되면 뒤 원소로 빈틈없이 채워넣는다. 그 결과 리스트는 배열에 비해 메모리의 낭비가 적다. 배열과 같이 랜덤 엑세스가 가능하므로 특정 위치의 데이터에 접근하는 시간복잡도..