Stack
Last In First Out LIFO 후입선출 구조를 가진다.
가장 마지막에 삽입된 자료가 가장 먼저 삭제가 된다.
스택은 쌓아 올린다는 뜻인데, 자료구조에서의 스택 또한 자료를 쌓아 올린 형태의 자료구조이다.
같은 구조, 같은 크기의 자료를 정해진 방향으로만 쌓을 수 있다.
top으로만 접근이 가능한데, top은 가장 위의 자료이다.
즉, 가장 최근에 들어온 자료가 된다.
삽입 연산을 push, 삭제 연산을 pop이라고 한다.
빈 스택에서 원소를 추출하는 것을 Stack underflow 라고 한다.
반대로 스택이 넘치는 경우를 Stack overflow 라고 한다.
Queue
First In First Out FIFO 선입선출 구조를 가진다.
가장 먼저 삽입된 자료가 가장 먼저 삭제가 된다.
top에서만 접근이 가능한 스택과는 달리, 큐는 front와 rear에서 삽입 연산만이 실행된다.
리어에서 일어나는 삽입 연산을 enQueue라 한다.
프론트에서 일어나는 삭제 연산을 deQueue라 한다.
Array
배열
크기가 정해져 있어 정적 자료구조라 한다.
Index를 가진다.
인덱스를 가지기 때문에 원소의 인덱스 값을 사용해 탐색에 O(1)이 소요된다.
삭제에 삽입을 실행을 할때, 모든 원소가 이동을 해야 하기 때문에 O(n)의 시간이 소요된다.
배열이 꽉 차있을 경우 메모리를 재할당 해야한다.
그렇지 않으면 삽입 자체가 불가능하다.
Linked List
크기가 정해져 있지 않기 때문에 동적 자료구조 라고한다.
인덱스를 가지는 배열과 달리 Node를 가지고 있다.
각각의 노드가 물리적으로 연결되어 있는 것이 아닌, 논리적으로 연결이 되어있다.
노드가 다음 데이터를 가리키기 때문에 탐색을 할 때 하나 하나 찾아 가야하기 때문에 O(n)이 소요된다.
삭제나 삽입의 경우, 그 노드만 수정을 해 주면 되기 때문에 O(1)이 소요된다.
그러나 원하는 원소를 수정하기 위해서는 결국 탐색이 동반되기 때문에 O(n+1) 즉, O(n)이 소요된다.
