Stack과 Queue, Array와 Linked List 설명 및 차이점

Stack

데이터를 차곡차곡 쌓아 올린 자료구조

 

데이터가 순서대로 쌓이고 마지막에 쌓인 자료가 먼저 삭제되는 구조로 LIFO(Last In First Out), 후입선출 구조

 

스택에서 삽입 연산은 push(), 삭제 연산은 pop()

시간 복잡도는 삽입, 삭제는 O(1)이고 탐색은 O(N)

 

대표적인 예로 실행 취소(undo), 웹페이지의 뒤로 가기, 역순 문자열 만들기, 수식의 괄호 검사 등이 있다.

 

 

Queue

Stack과 다르게 먼저 들어온 것이 먼저 나가는 선입선출 구조를 가지고 있음, FIFO(First In First Out)

 

큐에서 삽입 연산은 offer(), 삭제 연산은 pull()

시간 복잡도는 스택과 동일하다.

 

LinkedList를 가지고 만드는 것이 유리하며 자료의 추가는 Enqueue, 삭제는 Dequeue라고 부른다.

대표적인 예로 은행이나 식당 등의 대기 순서, 프로세스 관리 등이 있다.

---

 

 

Array

Array는 고정 길이

따라서, 정해진 길이의 배열을 모두 채우면, 새로운 데이터를 추가하고 싶을 경우 새로운 배열을 만들어주어야 함

 

 

데이터를 연속된 메모리 공간에 저장하는 자료구조

따라서 인덱스를 통해 빠르게 원하는 위치에 접근할 수 있음

 

 

단점 : 

데이터를 삽입하거나 삭제할 때는 해당 위치에서 이후의 모든 데이터를 이동시켜야 하므로 시간이 많이 소요됨

삽입/삭제가 오래 걸리고 배열 중간의 데이터가 삭제 되면 공간 낭비가 발생할 수 있는 단점이 존재하고, 크기를 변경할 수 없다는 단점도 존재

 

 

 

ArrayList

 

Array와 비슷하지만, 가변적인 길이를 가진다. 

	Array	ArrayList
사이즈	초기화시 고정 int[] arr = new int[3];	초기화시 사이즈를 표시하지 않음. 크기가 가변적임 ArrayList<Integer> arrList = new ArrayList<>();
속도	초기화시 메모리에 할당되어 ArrayList보다 속도가 빠름	데이터 추가 삭제 시, 내부 배열 공간 여부에 따라 메모리를 재할당할 수 있기 때문에 속도가 Array보다 느림
크기 변경	사이즈 변경 불가	추가, 삭제 가능 add(), remove()
다차원	int[][][] multiArr = new int[3][3][3];	불가능

 

LinkedList

 

여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조

 

각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있는 트리구조의 근간이 되는 자료구조이다.

 

메모리를 연속적으로 사용하지 않아 삽입/삭제에 용이하다는 장점이 있다.

 

그러나 index로 임의 접근이 불가하며 처음부터 탐색을 해야하는 단점이 있다.(O(n))

 

따라서 배열은 빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때 사용하고 링크드리스트는 삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때 사용한다.