자료 입출력

문제6) 선형 자료 구조인 스택, 큐, 리스트의 자료 입출력 원리를 설명하시오.

답)

 

1.순차적 자료 나열, 선형 자료 구조 스택, 큐, 리스트의 개념

스택	한쪽 끝에서만 데이터를 넣고 뺄 수 있는 제한적으로 접근할 수 있는 후입선출 (Last-In-First-Out) 형태의 자료구조
큐	FIFO(First in First out; 선입 선출)의 특징을 가지는 자료구조
리스트	데이터를 일정한 순서로 나열한 자료구조
선형 자료구조는 데이터를 저장할 때 연속적인 기억 공간에 배정하는 자료구조임 스택 , 큐 , 리스트는 순서가 있는 선형 자료구조로, 입력/출력시 스택은 한쪽에서만 가능 , 큐는 입력과 출력의 방향이 다르며 , 리스트는 어느곳에서나 입출력 가능한 점이 특징

 

2. 후입선출 구조 , 스택의 자료 입출력 원리 설명

가. LiFo (Last In , First Out) 스택의 자료 입출력 원리 상세 설명

스택 개념	top 이라고 하는 리스트의 한쪽 끝에서만 삽입과 삭제가 일어나는 자료구조 Push와 Pop을 통해 가장 최근에 보관한 자료가 나오는 LIFO(Last In First Out)구조로 컵에 물을 붓듯이 가장 마지막에 삽입된 자료가 먼저 삭제 되는 자료구조 형태
자료 입력 원리	Push
자료 출력 원리	POP
스택에서 가장 중요한 연산은 요소는 push와 pop이며, 스택에서의 입출력은 맨 위에서만 일어나고 스택의중간에서는 데이터를 삽입하거나 삭제할 수 없음

 

나. 스택의 활용 범위 설명

활용	설명
괄호의 짝 검사	괄호의 짝, 괄호의 순서 검사
함수 호출	프로그래밍에서의 함수 호출과 복귀에 따른 순서를 관리 (재귀적 사용)
웹 브라우저 방문기록 (뒤로 가기)	가장 나중에 열린 페이지부터 다시 보여준다
역순 문자열 만들기	가장 나중에 입력된 문자부터 출력한다
실행 취소(undo)	가장 나중에 실행된 것부터 실행을 취소한다.
스택의 삽입이나 삭제시 맨 위의 데이터를 삭제하기 때문에 시간복잡도는 늘 O(1)이며 , 특정한 데이터를 찾을때는 데이터를 찾을때까지 순차적으로 수행해야 하므로 O(n)임

 

3. 선입선출 구조 , 큐의 자료 입출력 원리 설명

가. FiFo (First In, First Out) 큐의 자료 입출력 원리 상세 설명

큐의 개념	큐는 선입선출(FIFO : First-In-First-Out) 구조로 먼저 넣은 데이터를 먼저 꺼내는 자료구조 자료의 입력은 rear 에서 하고 출력은 반대쪽 front 에서 진행됨
자료 입력 원리	enqueue
자료 출력 원리	dequeue
데이터 입력 시 Enqueue, 출력 시 Dequeue 동작을 수행함

 

나. 큐의 활용 예시 설명

활용	설명
대기열에 사용	서로 다른 쓰레드 사이 또는 프로세스 사이에서나 네트워크를 통해 자료를 주고받을 때 자료를 일시적으로 저장하는 용도
웹 서버 요청처리	웹 서버에서 클라이언트 요청 시, 받은 요청을 큐에 저장호고 순차적으로 처리하여 서버 과부하를 방지하고 응답 시간을 최소화
너비 우선 탐색 (BFS)	탐색할 노드를 큐에 저장하고 순차적으로 방문하여 그래프를 탐색
역순 문자열 만들기	가장 나중에 입력된 문자부터 출력한다
배열큐, 원형큐 등의 형태로 사용하며, 우선순위가 필요한 경우 우선순위 큐로도 활용 가능

 

4. 노드를 통한 연결 , 리스트의 자료 입출력 원리 설명

가. 리스트의 자료 입출력 원리 상세 설명

리스트 개념	자료들을 임의의 기억 장소에 저장시키고, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 구조
자료 입력 원리	Insert
자료 출력 원리	Delete
노드를 사용하여 입력과 출력을 연결하므로, 순서에 상관없이 입출력이 가능한 특징 존재 . 제한없이 데이터에접근 가능하여 활용도가 높음

 

나. 리스트의 자료 활용 예시 설명

활용	설명
Tree, Graph 등 활용	연결리스트를 활용하여 Tree , graph 자료구조로 활용 (이진트리 등 계층구조 구현에 효과적 )
커널 모드 프로그래밍	커널 모드 특성상 빠른 처리를 위해 데이터 입/출력이 자유로운 리스트 활용
리스트는 데이터를 담을 공간의 추가나, 자료 입력/출력이 자유로워서 단순하지만 효율적으로 사용할 수 있는대표적인 자료구조

---

 

공감과 댓글은 아이티신비에게 큰 힘이 됩니다.

블로그 글이 유용하다면 블로그를 구독해주세요.♥