![]()
큐의 구현 큐는 두가지 방법을 통해서 구현할 수 있다 배열을 활용하여 선형 형태로 큐를 구현하는 것. 배열을 활용하여 원형 형태로 큐를 구현하는 것 선형 큐 다음처럼 선형 큐는 일반 선형 배열 형태로 구현한다. Front 와 Rear를 통해 큐의 맨 앞과 뒤를 표시한다. 초기상태의 표시를 위해 front와 rear는 -1로 시작한다. Front위치에는 아무것도 저장하지 않는다 공백 상태 : Front = Rear 포화 상태 : Rear = Max_index 선형 큐의 문제는 dequeue를 통해 요소를 큐에서 제거함에도 불구하고 배열 크기만큼의 데이터만 저장할 수 있다는 점에 있다. 즉, 아무리 dequeue연산을 통해서 요소를 제거해도 이미 이전에 5개의 요소를 저장한 바가 있다면 더 이상 해당 큐를 ..
![]()
큐 먼저 들어온 데이터가 먼저 나가는 형태의 자료구조를 말한다. 이를 선입선출(FIFO)이라고 한다. 큐의 가장 대표적인 예시는 매표소에서의 대기열을 들 수 있다. 먼저 대기줄에 들어온 사람이 먼저 나가게 되므로 이는 큐를 이해하기 적절한 예시이다. ADT 객체 : 0개 이상의 요소들로 구성된 선형 리스트 연산 : create(max_size) ::= 최대 크기가 max_size인 공백 큐를 생성한다. init(q) ::= 큐를 초기화 한다. is_empty(q) ::= size == 0이면 true 반환 is_full ::= size == max_size이면 true 반환 peek(q) ::= 큐의 가장 앞의 요소 값을 반환한다. enqueue(q, e) ::= 큐의 가장 뒤에 요소 e를 추가한다 de..
Queue & Deque 이번 챕터에서는 큐와 덱에 대해서 알아본다. 이전에 알아보았던 스택까지 합쳐서 스택, 큐, 덱에 대한 아주 간단한 아이디어는 다음과 같다. Stack 후입 선출 LIFO 예) 접시 쌓기 Queue 선입 선출 FIFO 예) 줄서기 Deque Double ended queue 즉, 앞과 뒤 말단에서 삽입,삭제 이루어짐. 이번 챕터에서 다루게 될 내용은 다음과 같다. 큐 선형 큐 원형 큐 예시) 버퍼 덱 선형 원형
Stack 이름에서 알 수 있듯이 후입선출하는 형태의 자료구조. 접시를 쌓아서 보관하는 것을 예로 들 수 있다. ADT 객체 : 0개 이상의 원소를 가지는 유한한 길이의 선형 리스트 연산 : create(size) ::= 최대 크기 size인 스택 생성 is_full(s) ::= 스택의 모든 자리에 원소가 차있다면 true 반환 is_empty(s) ::= 스택이 모두 비어 있다면 true반환 push(s,item) ::= s스택에 item원소 추가 pop(s) ::= s스택의 가장 위 원소를 반환하고 제거한다. peek(s) ::= s스택의 가장 위 원소를 반환한다.
Stack 이번 챕터에서는 스택에 대해서 다룬다. 스택, ADT 배열 구현 구조체 활용 동적 할당 활용 괄호 검사 수식 표기(전위, 중위, 후위) 수식 변환 미로탐색
![]()
구조체 구조체는 타입이 다른 데이터를 하나로 묶는 방법이다. 배열은 타입이 같은 데이터를 하나로 묶는다. 구조체는 각 요소를 멤버(필드)라고 하고, 멤버 변수의 이름으로 접근한다. 배열은 각 요소를 인덱스로 접근한다. 선언 선언은 struct 키워드를 통해서 다음과 같이 한다. 접근은 맴버 변수의 이름을 통해 접근한다. Typedef C언어에서 typedef 키워드는 기존 타입에 새로운 이름을 붙일 때 사용한다. 구조체 변수를 선언할 때 매번 앞에 struct를 작성해야한다는 번거로움이 있으므로 typedef를 통해 코드를 한 단어라도 줄여볼 수 있다.
![]()
배열 배열은 같은 타입의 변수 여러개 만드는 경우에 사용한다. ADT 객체 : 쌍의 집합 연산 : create(size) ::= size개의 요소를 저장할 수 있는 배열 생성 get(A, i) ::= 배열 A의 i번째 요소 반환 set (A, i, v) ::= 배열 A의 i번째 위치에 v값 저장
배열 구조체,포인터 앞으로 배우게 될 자료구조를 학습하는데 있어서 기본이 되는 배열, 구조체, 포인터와 관련 알고리즘에 대해서 배워보도록 한다. 문법에 대한 이야기는 대부분 생략하고 작성한다. 배열 구조체 다항식 표현 희소행렬 포인터 동적 할당 구조체와 포인터
