1. 스택(Stack)
스택이란?
스택은 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입출력 순서는 후입선출(FILO) 방식이다.
데이터를 제한적으로 접근할 수 있는 구조이고, 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조이다.
스택은 콜 스택이라 하여 컴퓨터 프로그램의 서브루틴에 대한 정보를 저장하는 자료구조에도 널리 활용된다. 컴파일러가 출력하는 에러도 스택처럼 맨 마지막 에러가 가장 먼저 출력되는 순서를 보인다.
또한 스택은 메모리 영역에서 LIFO 형태로 할당하고 접근하는 구조인 아키텍처 레벨의 하드웨어 스택의 이름으로도 널리 사용된다. 이외에도 꽉 찬 스택에 요소를 삽입하고자 할 때 스택에 요소가 넘쳐서 에러가 발생하는 것을 스택 버퍼 오버 플로 (stack buffer overflow) 라고 부른다. 질의응답 서비스 사이트인 스택오버플로의 명칭도 여기서 유래했다고 ,,,
스택은 거의 모든 애플리케이션을 만들 때 사용되는 자료구조로서, 스택과 연관된 알고리즘을 제대로 이해하느냐 못하느냐에 따라 기본 알고리즘을 설계할 수 있느냐 없느냐가 결정되기도 한다.
스택 구조
- 스택은 LIFO 또는 FILO 데이터 관리 방식을 따름
- 대표적인 스택의 활용 : 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
- 주요기능
- push() : 데이터를 스택에 쌓기
- pop() : 데이터를 스택에서 꺼내기
- 스택의 크기 : 스택에서 쌓을 수 있는 데이터의 최대 개수
스택 구조와 프로세스
- 스택 구조는 프로세스 실행 구조의 가장 기본이다.
- 함수 호출 시 프로세스 실행 구조를 스택과 비교해서 이해할 필요가 있다.
스택의 장단점
장점
- 구조가 단순해서 구현이 쉽다.
- 데이터 저장, 읽기 속도가 빠르다.
단점 (일반적인 스택 구현 시)
- 데이터 최대 개수를 미리 정해야 함 ⇒ 파이썬의 재귀 함수는 1000번 까지만 호출이 가능함
- 저장 공간의 낭비가 발생할 수 있음 ⇒ 미리 최대 개수만큼 저장 공간 확보해야 함
스택의 경우 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적이다.
이 경우, 위에서 열거한 단점이 있을 수 있다.
2. 선형 리스트(Linear List)
선형리스트는 일정한 순서에 의해 나열된 자료 구조이다.
- 선형 리스트는 배열을 이용하는 연속 리스트와 포인터를 이용하는 연결 리스트로 구분된다.
연속 리스트(Contiguous List)
- 연속 리스트는 배열과 같이 연속되는 기억장소에 저장되는 자료 구조이다.
- 연속 리스트는 기억장소를 연속적으로 배정받기 때문에 기억장소 이용 효율은
밀도가 1로서 가장 좋다.
여기서 밀도가 1 이란?
연속 리스트의 기억장소 이용 효율을 이렇게 표현한 것은 연속 리스트는 기억장소를 연속적으로 배정받아 데이터를 기억하므로 배정된 기억장소를 빈 공간없이 꽉 차게 사용한다는 의미 !
- 연속 리스트는 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 있어야 하며, 삽입/삭제 시 자료의 이동이 필요하다.
연결 리스트(Linked List)
- 연결 리스트는 자료들을 반드시 연속적으로 배열시키지 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라
노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조이다.
노드 란?
자료를 저장하는 데이터 부분과 다음 노드를 가리키는 포인터인 링크 부분으로 구성된 기억 공간이다.
Data부분 | Link 부분 으로 나뉨
연결 리스트의 장단점
장점
- 연결 리스트는 노드의 삽입/삭제 작업이 용이하다.
- 기억 공간이 연속적으로 놓여 있지 않아도 저장할 수 있다.
단점
- 연결 리스트는 연결을 위한 링크(포인터) 부분이 필요하기 때문에 순차 리스트에 비해
기억 공간의 이용 효율이 좋지 않다. - 연결 리스트는 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근 속도가 느리다
- 연결 리스트는 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘들다.
3. 큐(Queue)
큐는 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료 구조이다.
- 큐는 가장 먼저 삽입된 자료가 가장 먼저 삭제되는
선입선출(FIFO; First In First Out)방식으로 처리한다. - 큐는 시작과 끝을 표시하는 두 개의 포인터가 있다.
- 프펀트(F, Front) 포인터 : 가장 먼저 삽입된 자료의 기억 공간을 가리키는 포인터로, 삭제 작업을 할 때 사용한다.
- 리어(R, Rear) 포인터 : 가장 마지막에 삽입된 자료가 위치한 기억 공간을 가리키는 포인터로, 삽입 작업을 할 때 사용한다.
- 큐는 운영체제의
작업 스케줄링에 사용한다.
