자료구조&알고리즘/자료구조 (4) 썸네일형 리스트형 [자료구조] 덱(Deque)의 개념과 연결 리스트로 구현(C언어) INDEX 1. 덱의 개념 2. 덱의 ADT를 구성하는 함수 3. 구현 3-1. 노드와 덱 구조체 3-2. 덱의 초기화와 비어 있는지 확인 3-3. 덱의 Front삽입과 Rear삽입 3-4. 덱의 Front추출과 Rear추출 1. 덱의 개념 덱은 아래의 그림처럼 직관적으로 이해하는 것이 가장 편하다. 스택이 입구와 출구가 1개뿐이었고 큐가 입구와 출구가 구별되는 일방향 통로의 느낌이었다면 덱은 큐의 업그레이드 버전인 양방향 이동 통로라고 이해할 수 있다. 그만큼 큐보다 개념적인 것들이 더 등장하게 된다. 덱에서 정보의 접근과 저장은 오직 Front와 Rear에서만 가능하다. 즉 큐보다 데이터 접근성이 더 좋아진 것이다. 덱의 Front에서 시작해서 Rear까지 이동할 수 있고 그 반대도 마찬가지로 가능하.. [자료구조] 스택을 활용해서 두 자리 수 이상의 연산이 가능한 계산기 만들기(C언어) 스택으로 계산기를 구현하려면 아래와 같은 과정을 거쳐야 한다. 중위 표기법을 모두 후위 표기법으로 바꾼다. 후위 표기법으로 바뀐 식을 스택에 넣어준다. 스택에 있는 값들을 특정 규칙에 따라 연산한다. 중위 표기법과 후위 표기법에 대한 내용은 위키 문서를 참조하기를 바란다. 이해를 돕기 위해서 후위 표기법을 가장 잘 설명한 블로그 주소도 남긴다. 주로 스택은 구제체 안에 배열을 선언한 상태로 사용한다. 아래는 스택을 구성하는 여러 기능들을 구현해 보았다. 이들 모두 계산기 구현에 중요한 역할을 하기 때문에 반드시 알고 넘어가야 한다. #include #include #include #define MAX_LEN 100 typedef struct Stack { // 스택 구조체 int data[MAX_LEN].. [자료구조] 연결 리스트(C언어) 연결 리스트(Linkedlist) 연결 리스트란 노드가 연결되어 있는 자료구조이다. 이때 노드는 노드만의 데이터와 포인터를 갖고 있다. 여기서 데이터는 우리가 저장하고자 하는 대상이 될 수도 있다, 예를 들면 수열, 등수에 따른 시험 점수 등이 될 수 있다. 즉 관리되는 데이터를 표현하는 것이 노드의 데이터 부분이다. 노드의 포인터는 사실 연결 리스트를 연결 리스트로 만들어주는 가장 중요한 특성이다. 포인터는 다음 노드 또는 이전 노드와의 연결을 담당한다. 즉 데이터 관리를 위한 포인터인 것이다. 우리가 알고 있는 일반적인 배열과는 다르게 데이터의 추가와 삭제가 어느 지점에서도 O(1)만에 가능하다는 장점이 있다. 하지만 단점으로는 데이터로의 임의적 접근이 상당히 제한된다는 점이다. 왜냐하면 초기 데이터.. [자료구조] 큐(Queue).(C언어) INDEX 1. 개요 2. 배열? 연결리스트? 3. 구현 3-1. Node(노드) 3-2. Queue(큐) 3-3. initQueue(초기화) 3-4. isempty(비어 있는지 확인) 3-5. enqueue(데이터 삽입) 3-6. dequeue(데이터 반환) 3-7. printQueueContents(큐에 있는 원소들 출력) 3-8. 주석 제거한 전체 코드 1. 개요 FIFO(First In First Out) 방식을 취하고 있는 자료구조이다. 스택(Stack)의 업그레이드 버전이라고 생각하면 쉽다. 왜냐하면 입출구를 공유하는 스택과는 다르게 큐는 입구와 출구가 다르기 때문이다. 큐는 단방향 구조인 동시에 rear부분에서 enqueue(데이터 삽입)와 front부분에서 dequeue(데이터 출)가 발생.. 이전 1 다음
