자료구조 (Array, Linked-List), 추상적 자료형 (Stack, Queue)

 

C Programming Course Project - Reservation Management System

 

C Programming 과정의 프로젝트로, Double linked-list와 Stack을 이용한 시스템을 만든적이 있다. 이 프로젝트를 리뷰하다보니, 자료구조에 대한 정리가 미흡한것 같아 확실히 정리해보고자 한다.

 

배열(Array)과 링크드 리스트(Linked-list)는 자료구조이며, Stack과 Queue는  추상적 자료형이라는 것으로 명확히 나눠보자.

 

---

자료구조와 추상적 자료형의 관계

자료구조(Data Structure)는 데이터를 효율적으로 관리하기 위한 구체적인 구현 방식이며,
추상적 자료형(Abstract Data Type, ADT)은 데이터와 연산을 논리적으로 정의한 개념이다.

 

 스택과 큐는 구현방법이 전혀 정의되어 있지 않으니 일반적인 방법은 있지만 추상적 자료형이고. 반면에 배열은 연속적으로 저장되어 있도록 구현되어 있어야 하므로 자료구조이고, 연결 리스트도 다음 데이터의 위치를 저장하는 방식으로 정해져 있으니 자료구조이다. 

 

 

---

1) 자료구조

1) 배열 (Array)

• 크기가 고정된 연속된 메모리 블록에 데이터를 저장하는 선형 데이터 구조.
• 인덱스를 통해 데이터에 빠른 접근 가능.
• 중간 삽입/삭제 시 긴 연산 시간이 필요.

 

2) 링크드 리스트 (Linked List)

• 각 요소(노드)가 데이터와 다음 요소의 포인터를 포함하며 동적으로 연결된 선형 데이터 구조.
• 동적으로 크기 조정 가능 (malloc).
• 데이터 접근은 느림.
• 삽입/삭제가 배열보다 효율적 (특히 중간 삽입/삭제 시).
• 단일 링크드 리스트: 노드가 한 방향으로만 연결.
• 이중 링크드 리스트: 노드가 양방향으로 연결.
• 크기가 가변적이거나 삽입/삭제가 빈번한 경우 많이 사용됨(예: 메모리 관리, 데이터 캐싱)

 

 

---

2) 추상적 자료형

1) 스택 (Stack)

• LIFO (Last In, First Out) 방식으로 작동하는 자료형.
• 구현 방법:
  배열 기반: 고정 크기의 배열로 구현.
  링크드 리스트 기반: 노드로 스택을 구현하여 크기 제한 없음.
• 함수 호출 스택, 뒤로 가기 기능 등에 사용됨.

 

2) 큐 (Queue)

• FIFO (First In, First Out) 방식으로 작동하는 자료형.
• 구현 방법:
  배열 기반: 고정 크기 큐.
  링크드 리스트 기반: 동적 크기 큐.
  원형 큐: 배열 기반 큐의 공간 효율성을 개선한 방식.
• UART 송수신, CPU 스케줄링 등에 사용됨.

 

---

 

정리하자면, 특정 상황에서 더 직관적이고 효율적인 구조가 필요할 때, 배열과 링크드 리스트를 활용하여  만든 구조를 스택과 큐라고 생각하면 된다.

 

큐 같은 경우에는 특히 디지털 회로 설계 시 많이 사용되는데 그 이유는 workload balance이다.

 

위의 그림과 같이 저희에게 Core0와 Core1과 같은 module이 존재한다고 생각해보자.

 

Core0는 data1, data2, data3 ...이렇게 계속해서 data를 출력하고 있으며, Core1은 해당 data들을 받아서 연산을 해야되는 module이다.

그런데 문제점은 Core1이 지금 다른 일을 하고있어 당장 data1, data2를 받을 수 없는 상황인 것이다. 그럴 때 어떻게 해야될까? Core0에서 data를 나중에 보내면 되는거 아니냐는데 Core0는 모종의 이유로 지금당장 data1, data2, data3를 출력하고 나중에는 다른 Core를 위한 data를 또 생성해야한다.

 

그럴 때 사용하는 것이 큐 구조이다. data1, data2이렇게 출력되는 Core0의 data들을 큐에 잠시 담아두고 있다가 Core1이 준비가되면 data1부터 순차적으로 가져올 수 있게 중간다리, buffer의 역할로 사용된다.

 

"Data를 나중에 써야되면 그냥 memory에 read하고 write하면 안되나?" 하는데 RAM에 비해 큐 구조의 이점은 바로 'Address관리가 필요없다'는 것이다.

 

Memory에서 Data를 읽거나 쓰기 위해서는 Address와 Data를 주고 write enable신호를 줘야한다.이렇게 되면 Address를 전송하기 위한 Bandwidth증가, 에너지 소비 증가, Address 출력을 관리하기 위한 core의 부담까지 증가하게 된다. 하지만, 큐 구조에서는 그냥 Data를 전송해야되면 write enable만, Data를 읽어오려면 read enable만 주면 된다.

물론 Data를 시간 순으로 정렬된 형태로 밖에 못가져오지만 많은 Dataflow architecture에서 가져온 순서대로 Data를 사용하는 경우는 많으니 효율성을 위해서 해당 구조를 많이 쓰게 되는 것이다.

 

 

Reference)

https://velog.io/@gju06051/Verilog%EC%8B%AC%ED%99%943-FIFOSingle-Clock