1)스택(Stack)
1. 스택의 구조
– 데이터 입출력이 한쪽에서만 일어아는 구조
– 스택 포인터(TOP)가 가장 마지막에 삽입된 데이터가 저장된 위치 정보(값)를 저장한다.
– 데이터가 삽입(PUSH)될 때마다 1씩 증가하며, 스택의 크기를 넘어서게 되면 Overflow를 발생
– 스택 포인터는 데이터를 추출(POP)할 때마다 1씩 감소하며, 0보다 작아지게 되면 UnderFlow를 발생
2. 스택의 특징
– 가장 나중에 삽입된 데이터가 가장 먼저 추출되는 후입선출(LIFO: Last In First Out) 방식
– 프로그램의 함수 호출, 깊이 우선 탐색, 재귀 호출, Linear List, Post-fix등에 사용
3. 수식 표기법
– 피연사자와 연산자를 배치, 나열하는 방법
– 연산자의 위치에 따라 전위식, 중위식, 후위식
– 전위식(Pre-fix): 연산자가 피연산자들의 앞(왼쪽)에 위치
– 중위식(In-fix): 연산자가 피연산자들의 중간에 위치
– 후위식(Post-fix): 연산자가 피연산자들의 뒤(오른쪽)에 위치
2)수식 표기법 변환
1. 중위식을 전위식으로 변환
2. 중위식을 후위식으로 변환
3. 전위식을 중위식으로 변환
4. 후위식을 중위식으로 변환
3)큐(Queue)
1. 큐의 구조
– 데이터의 입출력이 반대쪽에서 일어나는 구조
– 삽입 포인터(Rear)는 가장 마지막에 삽입된 데이터의 위치를 가르키며 삽입될때 마다 1씩 증가한다
– 삭제 포인터(Front)는 가장 처음에 삽입된 데이터의 위치를 가리키며 삭제될때 마다 1씩 증가한다
– Rear와 Front의 초기값은 모두 -1이며 두값이 같을 때는 큐에 데이터가 비어있는 경우이다.
2. 큐의 특징
– 가장 먼저 삽입된 데이터가 가장 먼저 출력되는 선입선출(FIFO: First In First Out) 방식
– 프린터 스풀이나 입출력 버퍼와 같은 대기 행렬에 적합한 자료 구조
– 데이터가 삭제될수록 Front값이 증가하므로 저장된 데이터를 다시 앞쪽으로 옮겨줘야 한다
4)데크(Deque)
1. 데크의 구조
– 데이터의 입출력이 양쪽 모두에서 일어나느 구조(양방향 큐)이다.
– 각각의 포인터(Left, Right)가 데이터 삽입, 삭제에 따라 1씩 증감
2. 데크의 특징
– 입/출력이 빈번한 경우에 적절한 자료 구조
– 입출력 제한 유형에 따라 스크롤 방식과 쉘프 방식
– 입력 제한(Scroll): 출력은 양쪽에서 가능하지만 입력은 한쪽에서만 가능
– 출력 제한(Shelf): 입력은 양쪽에서 가능하지만 출력은 한쪽에서만 가능
5)선형(Linear) 리스트
1. 선형 리스트 구조
– 같은 유형의 데이터가 연속된 공간에 저장되는 자료 구조
– 가장 단순한 구조이며 접근 속도(탐색 속도)가 빠르다.
– 삽입, 삭제 시 나머지 데이터들의 위치 이동이 필요하므로 시간이 오래 걸린다
– 선형 리스트의 대표적인 유형으로는 배열(Array)
– 하나의 이름과 첨자(Index)를 통해 데이터들의 위치를 구분
– 고정 크기의 모메리 공간을 사용하며 논리적인(접근하는) 순서와 물리적인(저장된) 순서가 같다
– 배열의 중간 위치에 데이터를 삽입하는 경우, 해당 위치의 오른쪽에 있는 모든 요소를 한 칸씩 오른쪽으로 이동시켜야 한다.
– N개의 데이터를 가진 배열의 평균 이동 횟수: (N+1)/2
– 배열의 중간 위치에 데이터를 삭제하는 경우, 해당 위치의 오른쪽에 있는 모든 요소를 한 칸씩 왼쪽으로 이동시켜야 한다
– N개의 데이터를 가진 배열의 평균 이동 횟수: (N-1)/2
6)연결(Linked) 리스트
1. 연결 리스트의 구조
– 데이터의 삽입, 삭제가 어려운 배열의 단점을 보완한 자료 구조
– 데이터의 연속적 나열이 아닌, 서로 다른 위치의 노드와 노드의 연결로 구성
– 노드(Node): 데이터와 자신이 연결된 데이터의 포인터(위치값을 저장하는 변수)를 묶는 단위
– 노드마다 포인터가 필요하므로 기억 공간이 추가로 필요하며 접근 배열보다 느린 편이다
– 노드의 형태와 구성에 따라 다양한 종류의 연결 리스트가 존재한다
2. 단일(Single) 연결 리스트
– 1개의 포인터를 사용하여 자신의 다음 노드 위치를 기억하는 형태의 리스트
– 마지막 노드의 포인터는 Null값을 가진다
– 탐색은 항상 첫 노드부터 시작되어야 하며, 포인터가 훼손되면 복구가 불가능
3. 단일 원형(Circular) 연결 리스트
– 단일 연결 리스트의 형태에서, 마지막 노드에서 다시 첫 노드로 탐색이 가능한 형태의 리스트
– 마지막 노드의 포인터는 첫 노드의 위치값을 가진다
– 반복해서 전체 노드의 탐색이 가능
4. 이중(Double) 연결 리스트
– 2개의 포인터를 사용하여 자신의 전(Prev), 후(Next) 노드 위치를 기억하는 형태의 리스트이다
– 양방향 탐색이 가능하고, 포인터가 훼손되어도 복구의 가능성이 있다
– 첫 노드의 Prev포인터와 마지막 노드의 Next포인터는 Null값을 가진다
5. 이중 원형 연결 리스트
– 이중 연결 리스트와 원형 리스트의 특징을 합한 형태의 리스트
– 양방향 탐색이 가능하고, 포인터 훼손 시 복구의 가능성이 있으며 반복적인 순회가 가능
– 첫 노드의 Prev포인터는 마지막 노드의 위치값을 가지고, 마지막 노드의 Next포인터는 첫 노드의 위치값을 가진다