자료구조, 그 첫 번째 이야기 | Stack , Queue , Double-ended queue , List

자료구조란, 데이터를 관리함에 있어서, 효율적인 접근, 수정을 가능하게 하는 데이터의 관리 형식이다. 더 구체적으로 말하면, 자료구조란 데이터 값의 집합, 그 사이의 관계에 적용할 수 있는 연산들이다. 

스택 (Stack) 이란 데이터의 값을 저장하는 자료구조로서, 제한적인 접근, 두 가지의 기본적인 연산을 가진다. 접근(Peek), 삭제 되지 않은 원소들 중 가장 최근에 삽입한 데이터의 값에 접근한다.   삽입(Push), 데이터의 값들의 모음에 새로운 값을 추가한다.  삭제(Pop), 삭제 되지 않은 원소들 중 가장 최근에 삽입한 데이터를 모음에서 제거한다.

스택의 성질을 한 문장으로 요약하자면 LIFO(Last In, First Out) 이다. 

 

 

 

큐 (Queue) 란 데이터의 값을 저장하는 자료구조로서, 제한적인 접근, 두 가지의 기본적인 연산을 가진다. 접근(Peek), 삭제 되지 않은 원소들 중 가장 먼저 삽입한 데이터의 값에 접근한다. 삽입(Push , Enqueue), 데이터의 값들의 모음에 새로운 값을 추가한다.  삭제(Pop, Dequeue), 삭제 되지 않은 원소들 중 가장 먼저 삽입한 데이터를 모음에서 제거한다.

큐의 성질을 한 문장으로 요약하자면, FIFO(First In, First Out) 이다. 

 

 

Double-ended queue (이하 Deque) 이란 Queue를 일반화한 형태의 자료구조로서 2가지의 제한적인 접근, 4가지의 연산을 가진다.  앞 접근, Deque에서 가장 앞에 있는 원소의 데이터의 값에 접근한다.  뒤 접근, Deque에서 가장 뒤에 있는 원소의 데이터의 값에 접근한다.   앞 삽입, Deque의 앞에 원소를 추가한다. 뒤 삽입, Deque의 뒤에 원소를 추가한다. 앞 삭제, 삭제 되지 않은 원소들 중 Deque의 가장 앞에 위치한 데이터를 모음에서 제거한다. 뒤 삭제, 삭제 되지 않은 원소들 중 Deque의 가장 뒤에 위치한 데이터를 모음에서 제거한다.

Deque는 Queue 와 Stack을 합친 형태의 자료구조로서, head-tail linked list 라고도 불린다.

 

리스트(List)는 데이터의 값을 저장하는 자료구조로서, 다음과 같은 제한적 접근과, 연산을 가진다. 접근, 현재 가리키고 있는 데이터의 값에 접근한다.  전달, 현재 가리키고 있는 데이터의 다음 데이터를 가리키도록 한다.

List 는 이러한 연산의 특징 때문에 값의 Random Access 가 안된다는 단점이 있지만, 데이터의 임의 위치 추가가 상수시간에 가능하다는 장점이 있다. 

 

각 자료 구조의 값의 추가 / 삭제 / 임의 위치 추가 / 임의 위치 삭제 / 값 검색 등의 연산에 대한 비교는 다음 포스팅에서 다루고자 한다.