[선형구조]자료 구조의 개념 정리(리스트, 스택, 큐, 데크)

지금까지 자료구조를 대충 여겨왔네요...

이참에 하나씩 정리하려고 합니다.

자료 구조의 정의

프로그램에서 사용하기 위한 자료를 기억장치의 공간내에 저장하는 방법과 

저장된 그룹 내에 존재하는 자료 간의 관계, 처리 방법 등을 연구 분석하는 것을 말한다.

○ 자료 구조는 자료의 표현과 그것과 관련된 연산

○ 자료 구조는 일련의 자료들을 조직하고 구조화하는 것

○ 어떠한 자료 구조에서도 필요한 모든 연산들을 처리하는 것이 가능

○ 자료 구조에 따라 프로그램 실행시간이 달라짐

자료 구조의 분류

자료 구조의 이용

○ 정렬(Sort) : 기억장치 내의 자료를 일정한 순서에 의해 나열하는 것

○ 검색(Search) : 기억장치 내의 자료를 찾는 것

○ 파일 편성 : 자료를 기억 매체에 저장할 때의 파일 구조

○ 인덱스 : 파일에서 특정 자료를 빠르게 찾기 위한 색인표

아래에서부터는 자료구조의 개념만 살짝 훑어보고 지나가도록 하겠습니다.

나중에 코딩을 통해서 실제 해봐야할 필요가 있을것 같습니다.

□ 리스트

○ 선형 리스트(Linear List)

  - 배열과 같이 연속되는 기억장소에 저장되는 리스트 ex) 배열(Array)

  - 특징 

   · 가장 간단한 자료구조

   · 접근 속도가 빠름

   · 기억장소를 연속으로 배정받기 때문에 기억장소 이용 효율은 밀도가 1로서 가장 좋음

   · 자료의 개수가 n개 일때, 삽입시 평균 이동 횟수 : n+1/2, 삭제시 평균 이동 횟수 : n-1/2  

   · 삽입, 삭제 시 자료의 이동이 필요하기 때문에 작업이 번거로움

  - 구조 예시

    

○ 연결 리스트(Linked List)

  - 자료들을 반드시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결 시킴

  - 특징 

   · 노드의 삽입, 삭제 작업 용이

   · 연결을 위한 링크 부분이 필요하기 때문에 순차 리스트에 비해 기억공간 이용 효율이 좋지 않음

   · 포인터 찾는 시간 필요로 접근 속도 느림

   · 트리를 표현할 때 가장 적합한 구조

   · 삽입, 삭제 시 자료의 이동이 필요하기 때문에 작업이 번거로움

   · 종류 : 단순 연결 리스트, 단순 환상 연결 리스트, 이중 연결 리스트 등..

  - 구조 예시 

□ 스택

○ 스택의 개념

  - 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어짐

  - 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO : Last In First Out)

○ Stack의 응용

  - 부 프로그램 호출 시 복귀주소를 저장할 때

  - 함수 호출의 순서 제어

  - 인터럽트 발생 시 복귀주소를 저장 할ㄷ 때

  - 0 주소지정방식 명령어의 자료 저장소

  - 재귀 프로그램의 순서 제어 등...

○ 구조 예시

□ 큐(Queue)

○ 큐(Queue)

  - 선형 리스트의 한쪽에서는 삽입, 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료구조

  - 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO : First In First Out)

○ Queue의 응용

  - 창구 업무나 택시 정거장처럼 서비스 순서를 기다리는 등의 대기 행렬의 처리에 사용

  - 운영체제의 작업 스케줄링에 사용

○ 구조 예시

□ 데크(Deque)

○ 개념

  - 삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료 구조

  - 스택과 큐의 장정만 따서 구성한 것

  - 입력 제한 데크 : Scroll, 출력 제한 데크 : Shelf