7일차 과제 - Stack, Queue, Array, Linked List 자료구조와 차이점

1. Stack (스택): 스택은 LIFO(Last In, First Out) 원칙을 따르는 자료구조이다.
   즉, 가장 최근에 추가된 항목이 가장 먼저 제거된다.
   스택은 함수 호출, 실행 취소(undo) 등에 주로 사용된다.
   나중에 집어넣은 데이터가 먼저 나오는 구조 / LIFO (Last In First Out), peek(가장 마지막 집어넣은 데이터 확인)
   • peek 가 있는 이유를 생각해봤을 때, 브라우저에서 이전 페이지, 작업을 확인하는 경우에 필요하다고 생각된다.
   <스택 구조도> 
   

• 한쪽이 막혀있는 상태에서 pop을 할 경우 가장 마지막에 저장된 데이터가 빠져나간다.

<스택 pseudocode>

• 데이터가 순서대로 입력을 받는다.(저장된다.) / push
• 스택이 가득 찬 경우, 가장 마지막에 입력된 데이터가 빠져나간다. / pop
• 가장 마지막에 저장된 데이터를 확인할 수 있다. / peek

---

2. Queue (큐): 큐는 FIFO(First In, First Out) 원칙을 따르는 자료구조이다.
즉, 가장 먼저 추가된 항목이 가장 먼저 제거된다.
큐는 데이터를 순차적으로 처리해야 하는 상황, 예를 들어 인쇄 작업 대기열이나 메시지 대기열 등에 사용된다.

Stack 과 마찬가지로 데이터를 집어넣을 수 있는 선형(Linear) 자료형

먼저 집어넣는 데이터가 먼저 나오는 방식 / FIFO (First In First Out)

사용되는 Property 또는 메소드는 Enqueue, dequeue (shift)

• 자바스크립트에서 Array method 중 shift() 메소드가 배열의 첫 번째 요소를 삭제하고 삭제된 요소를 반환해주기 때문에(mutable 한 메소드), dequeue 를 구현할 때 사용한다.

<큐 구조도>

---

3. Array (배열): 배열은 동일한 타입의 여러 항목을 저장하는 데 사용되는 가장 간단한 자료구조 중 하나이다.
배열의 모든 요소는 연속적인 메모리 위치에 저장되며, 인덱스를 사용하여 각 요소에 직접 접근할 수 있다.
그러나 배열의 크기는 생성 시 정의되고 변경할 수 없으며, 이로 인해 메모리를 비효율적으로 사용할 수도 있다.

Array(배열)이 인덱스와 value 로 정해진 공간에 데이터가 저장

인덱스를 가지고 있기 때문에, 검색 / 접근 / 정렬 등에 장점

자료의 추가 / 삭제 측면에서, 중간에 자료가 추가 / 삭제 되면 그 다음에 위치한 이미 지정된 인덱스를 모두 바꿔주어야 하기 때문에, 많은 시간이 소요된다.

 

4. Linked List (연결 리스트): 연결 리스트는 각 요소가 메모리의 어느 위치에 있는지를 가리키는 링크 또는 참조를 포함하는 노드로 구성된 선형 자료구조이다.
연결 리스트는 삽입과 삭제가 자주 발생하는 경우에 유용하며, 메모리를 효율적으로 사용할 수 있다.
그러나 연결 리스트에서 특정 요소에 접근하려면 리스트의 처음부터 차례대로 거쳐가야 하므로, 이는 배열에 비해 더 많은 시간이 소요된다.

Linked list 는 존재하는 데이터 만큼의 공간을 차지한다.

Linked list 가 데이터 공간을 절약하는 데 더 효과적이라 할 수 있다.

순차적으로 검색을 하기 때문에, 많은 시간이 소요됨.

자료의 추가 / 삭제 측면에서, Linked List 는 추가 / 삭제된 노드 이전과 이후의 포인터(주소)만을

바꿔주면 되기 때문에 빠른 처리가 가능하다.

Array와 Linked list 차이

<Linked List Pseudo 코드>

1. 노드를 데이터와 next 포인터로 구분한다.
2. head (첫 번째 데이터 참조)가 기본적으로 존재해야 한다.

---

• Stack과 Queue는 추가 및 제거 순서에 따라 다르게 동작합니다. Stack은 가장 마지막에 추가된 요소를 먼저 제거하고, Queue는 가장 먼저 추가된 요소를 먼저 제거한다.
• Array와 Linked List는 데이터 저장 방식과 접근 방식에서 차이가 있다. Array는 연속적인 메모리 공간에 데이터를 저장하고 인덱스를 통해 직접 접근할 수 있지만, 크기가 고정되어 있다.
• Linked List는 비연속적인 메모리 공간에 데이터를 저장하며, 각 노드는 다음 노드를 가리키는 링크를 가지고 있다. 이 구조는 데이터의 삽입과 삭제를 용이하게 만들지만, 특정 요소에 접근하려면 리스트를 처음부터 순차적으로 거쳐가야 한다.

각 자료구조의 사용 케이스에 따라 그 성능과 효율성이 달라질 수 있다.
예를 들어, 데이터의 삽입과 삭제가 빈번한 경우에는 Linked List가 적합할 수 있다.
반면, 인덱스를 통해 특정 요소에 빠르게 접근해야 하는 경우에는 Array가 더 적합하다.
마찬가지로, 가장 최근의 항목을 먼저 처리해야 하는 경우에는 Stack을, 항목을 추가된 순서대로 처리해야 하는 경우에는 Queue를 사용하는 것이 좋다.