05.16 TIL (Stack과 Queue 그리고 Array와 Linked List 자료구조와 차이점)

Array

Array는 고정 크기의 연속된 메모리 공간에 데이터를 저장하는 자료구조이며, 데이터에 접근할 때 인덱스를 사용하여 빠른 임의 접근이 가능하다.

데이터의 삽입과 삭제가 비효율적이며, 중간에 데이터를 삽입하거나 삭제할 경우 다른 모든 요소를 이동시켜야 한다.

크기가 고정되어 있으므로 크기를 동적으로 변경하는 것이 어렵다.

Linked List

노드로 이루어진 연결된 목록으로 데이터를 저장하는 자료구조이며, 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성된다.

Stack

후입선출(LIFO, Last-InFirst-Out) 원칙에 따라 동작하는 자료구조이며, 데이터의 삽입은 스택의 맨 위에 삭제는 맨 위에서만 이루어진다.

주요 연산은 push(삽입)과 pop(삭제)이며 함수의 호출 스택, 괄호 짝 맞추기 등에 사용된다.

Queue

선입선출(FIFO, First-In-First-Out) 원칙에 따라 동작하는 자료구조이며, 데이터의 삽입은 큐의 뒤에, 삭제는 앞에서 이루어진다.

주요 연산은 enqueue(삽입)와 dequeue(삭제)이며, 작업 큐, 프로세스 스케줄링 등에 사용된다.

---

Array와 Linked List 주요 차이점

Array와 Linked List의 차이점

• 메모리 할당
  • Array는 정적으로 메모리를 할당하고 크기가 고정되어 있으며, Linked List는 동적으로 메모리를 할당하고 크기를 동적으로 조정할 수 있다.
• 데이터 삽입 및 삭제
  • Array는 데이터의 삽입과 삭제가 비효율적이며, 중간에 데이터를 삽입하거나 삭제할 경우 다른 모든 요소를 이동시켜야 한다. 반대로 Linked List는 데이터의 삽입과 삭제가 간단하고 효율적이며, 노드를 추가하거나 제거하는 것은 단순히 포인터 연결을 변경하는 작업이다.

Stack과 Queue의 주요 차이점

• 동작 원칙
  • Stack은 후입선출 원칙에 따라 동작하며, 가장 최근에 삽입된 데이터가 가장 먼저 삭제된다.
  • Queue는 선입선출 원칙에 따라 동작하며, 가장 먼저 삽입된 데이터가 자장 먼저 삭제된다.
• 삽입과 삭제 위치
  • Stack은 데이터의 삽입과 삭제가 스택의 맨 위에서 이루어지며, Queue는 데이터의 삽입은 큐의 뒤에서 이루어지고, 삭제는 큐의 앞에서 이루어진다.