[자료구조] 스택(Stack)과 큐(Queue), 배열(Array)과 연결 리스트(Linked List)

 

스택(Stack)
v. 쌓다, 포개다  n. 무더기

스택(Stack)

선형 자료구조의 일종으로, 그림처럼 입력할 때는 아래부터 차곡차곡 데이터를 쌓은 뒤, 출력할 때는 가장 위에서부터 데이터를 꺼낸다.
가장 늦게 입력된 데이터가 가장 먼저 출력되는 LIFO(Last In, First Out)구조. 

 

 

큐(Queue)
v. 줄을 서서 기다리다  n. 대기 행렬

큐(Queue)

선형 자료구조의 일종으로, 아래위가 뚫린 원통처럼 입력할 때 가장 먼저 들어간 데이터가 출력할 때 가장 먼저 사용된다.
가장 먼저 입력된 데이터가 가장 먼저 출력되는 FIFO(First In, First Out)구조.

 

 

배열(Array)
v. 배치하다, 배열하다  n. 배열

배열이란, 논리적 저장 순서와 물리적 저장 순서가 일치하는 가장 기본적인 자료구조다.
배열은 인덱스와 인덱스에 해당하는 데이터로 이루어져있는데, 일반적으로 같은 종류의 데이터가 순차적으로 저장되어있다.

원하는 데이터의 인덱스를 알고 있다면 해당 인덱스로 이동해서 바로 데이터를 호출할 수 있으므로 이때의 시간 복잡도는 O(1)으로 굉장히 효율적이다.
하지만 배열에 데이터를 삽입하거나 삭제할 때는 해당 인덱스 뒤에 있는 데이터의 인덱스를 한 칸 앞이나 뒤로 이동(Shift)시켜야 하기 때문에 시간 복잡도가 최대 O(n)이 될 수 있다.

데이터 삽입 시
👍 배열의 맨 끝에 데이터를 추가할 때: O(1)
👎 배열의 맨 앞에 데이터를 추가할 때: O(n)

데이터 삭제 시
👍 배열의 맨 끝 데이터를 삭제할 때: O(1)
👎 배열의 맨 앞 데이터를 삭제할 때: O(n)

 

 

연결 리스트(Linked List)

배열에서 데이터의 삽입, 삭제 시 발생하는 비효율성을 개선하기 위해 고안된 자료구조로, 각각의 데이터는 자신 다음에 어떤 데이터가 오는지만 기억하고 있다. 따라서 데이터 삽입, 삭제 시 뒤에 오는 데이터만 바꿔주면 되기 때문에 시간 복잡도가 O(1)가 된다.

단! 연결 리스트는 배열과 달리 논리적 저장 순서와 물리적 저장 순서가 같지 않기 때문에(인덱스를 이용하여 한 번에 원하는 데이터의 위치를 찾을 수 없기 때문에) 삽입, 삭제하기 위해 데이터의 위치를 찾기 위해서 가장 첫번째 데이터부터 순서대로 확인해봐야 한다. 이때 최악의 경우(원하는 데이터가 가장 마지막에 위치한 경우) 데이터의 위치를 찾는데 시간 복잡도가 O(n)이 될 수 있다.

결국 데이터를 찾는 과정과 삽입, 삭제까지 합쳐 최악의 경우 시간 복잡도가 O(n)이라는 결과를 갖는다. 이것만 놓고 보면 배열과 결과가 크게 다르지 않아 실망할지도 모르지만, 연결 리스트는 트리 구조의 근간이 되어 그 빛을 발한다.