Stack과 Queue, Array와 Linked List

1. Stack

스택(Stack)은 LIFO(Last In First Out) 구조를 가진 자료구조입니다.

스택에 요소를 삽입하는 push와 요소를 삭제하는 pop 동작이 있고,

스텍 내부에 요소 존재 여부를 확인하는 is_empty 동작 또한 존재합니다.

스택은 주로 함수의 실행 순서를 관리하는 데 사용됩니다.

 

2. Queue

큐(Queue)는 FIFO(First In First Out) 구조를 가진 자료구조입니다.

큐에 요소를 삽입하는 enqueue와 요소를 삭제하는 dequeue 동작이 있고,

스택과 마찬가지로 요소 존재 여부를 확인하는 is_empty도 존재합니다.

큐는 주로 요청이 들어온 순서대로 작업을 처리하는 데 사용됩니다.

 

3. Array

배열(Array)은 같은 타입의 데이터를 일렬로 나열한 자료구조입니다.

메모리 공간을 연속적으로 할당하고 인덱스를 사용해서 각 요소에 접근합니다.

크기가 고정되어 있기 때문에 사전에 최대 크기를 지정해야 하고,

요소의 삽입 또는 삭제가 발생하면 전체 요소를 이동시켜야 하므로 비효율적입니다.

인덱스의 존재로 랜덤 액세스가 가능하여 검색에 유리합니다.

배열은 주로 정렬 알고리즘에서 사용됩니다.

 

4. Linked List

링크드 리스트는 데이터를 저장하는 노드(Node)들이 연결되어 있는 자료구조입니다.

각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성되어 있고,

메모리 공간은 불연속적으로 할당합니다.

그렇기 때문에 삽입 또는 삭제가 자주 발생하는 경우에는 배열보다 효율적입니다.

하지만 랜덤 액세스가 불가능하여 검색에는 적합하지 않습니다.

링크드 리스트는 주로 스택, 큐에서 사용됩니다.