TIL#65(Array와 LinkedList, Stack과 Queue)

오늘 한일

• Array와 LinkedList

• Array : 배열은 동일한 데이터 타입의 요소들이 메모리 상에 연속적으로 저장된 자료구조이다.
  - 크기 : 배열의 크기는 초기화 시 결정되며, 이후에는 변경할 수 없다.
  - 접근 : 인덱스를 통해 O(1) 시간 복잡도로 요소에 빠르게 접근할 수 있다.
  - 메모리 : 고정된 크기 때문에 필요한 크기보다 큰 배열을 할당할 경우 메모리 낭비가 발생할 수 있다.
  - 삽입 / 삭제 : 중간에 삽입 / 삭제 시 O(n) 시간이 소요 되어 비효율적이다
• LinkedList : 연결 리스트는 각 요소가 노드로 구성되며, 각 노드는 데이터와 다음 노드에 대한 참조(포인터)를 포함하는 자료구조입니다.
  - 크기 : 필요에 따라 동적으로 크기를 조정할 수 있다.
  - 접근 :  특정 인덱스의 요소에 접근하려면 첫 번째 노드부터 순차적으로 접근해야 하므로 O(n) 시간이 걸려 비효율적이다.
  - 메모리 : 추가 메모리가 필요하다(데이터 외에 포인터 저장 공간).
  - 삽입 / 삭제 : 요소 삽입/삭제가 효율적이다(노드 포인터 조정으로 O(1) 시간 소요).

• Stack과 Queue

• Stack : 스택은 LIFO(Last In, First Out) 구조의 자료구조로, 마지막에 삽입된 요소가 가장 먼저 제거된다.
  기본 연산
  - push : 스택의 맨 위에 요소를 추가
  - pop : 스택의 맨 위에서 요소를 저거하고 반환
  - peek : 스택의 맨 위 요소를 제거하지 않고 반환
  사용 사례 : 함수 호출 스택, 브라우저 히스토리, 역순 작업 처리
• Queue : 큐는 FIFO(First In, First Out) 구조의 자료구조로, 먼저 삽입된 요소가 가장 먼저 제거된다.
  기본 연산
  - enqueue : 큐의 끈에 요소를 추가
  - dequeue : 큐의 앞에서 요소를 제거하고 반환
  - peek :  큐의 앞 요소를 제거하지 않고 반환
  사용 사례 : 작업 스케쥴링, 프린터 작업 대기열, 메시지 큐

오늘의 TIP

• 덱(deque) : 양쪽 긑에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이며 두 개 의 포인터를 사용하여 양쪽에서 삭제와 삽입을 발생시킬 수 있다. (큐와 스택을 합친 형태로 생각할 수 있다.)