Stack, Queue, Array, Linked List

스택(Stack)

• 후입선출(LIFO: Last-In-First-Out) 방식
• 데이터를 삽입(push)하고 삭제(pop)할 때 가장 최근에 삽입된 데이터가 먼저 삭제됩니다.
  → 한쪽 끝에서만 데이터를 삽입하고 삭제
• 예시: 웹 브라우저의 뒤로 가기 기능, 함수 호출 시 로컬 변수와 복귀 주소 저장 등

큐(Queue)

• 선입선출(FIFO: First-In-First-Out) 방식
• 데이터를 삽입(enqueue)하고 삭제(dequeue)할 때 가장 먼저 삽입된 데이터가 먼저 삭제됩니다.
  → 한쪽 끝에서 데이터를 삽입하고, 반대쪽 끝에서 데이터를 삭제
• 예시: 작업 큐, 메시지 큐, 버퍼 등

배열(Array)

• 일정한 크기의 연속된 메모리 공간에 데이터를 저장합니다.
• 인덱스를 사용하여 데이터에 접근할 수 있습니다.
• 데이터의 삽입, 삭제 시에는 해당 인덱스에 직접 접근하여 조작합니다.
• 크기가 고정되어 있어 삽입이나 삭제가 비효율적일 수 있습니다.
• 예시: 정수 배열, 문자열 배열 등

연결 리스트(Linked List)

• 데이터를 노드(Node)라는 개별적인 객체에 저장하고, 노드들이 링크(포인터)로 연결되어 있습니다.
• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성됩니다.
• 데이터의 삽입, 삭제 시에는 링크를 수정하여 조작합니다.
• 크기가 동적으로 조정될 수 있으며, 삽입과 삭제가 상대적으로 빠릅니다.
• 예시: 단일 연결 리스트, 이중 연결 리스트 등

배열은 크기가 고정되고 데이터의 삽입과 삭제가 비효율적일 수 있지만, 인덱스를 통한 빠른 접근이 가능

반면에 연결 리스트는 크기가 동적으로 조정될 수 있으며 데이터의 삽입과 삭제가 용이하지만, 포인터로 인한 메모리 공간의 낭비가 발생할 수 있음