Computer Science/Data Structure 자료구조11 [C언어] Array Stack 배열 스택 구현 스택이란 ? 리스트와 같이 선형 (Sequential) 구조 자료를 순차적으로 저장한다. 리스트와 다르게 LIFO(후입 선출) 자료의 추가와 제거가 TOP에서 이루어 진다. 스택에 필요한 주요 Operations Pop - 스택의 Top에 있는 자료를 제거한 후 반환한다. Push - 스택의 Top에 자료를 추가한다. Peek - 스택의 Top에 있는 자료를 반환한다. (제거 x) isEmpty - 스택이 비어있는지 확인한다. 배열 스택의 장점 속도가 빠르다 더 빨리 노드에 접근할 수 있다. 배열 스택의 단점 미리 저장할 데이터의 개수를 예측하고 여유롭게 스택의 크기를 지정해야한다. 나중에 데이터를 추가하기 위해서이다. 만약 데이터의 개수만큼 배열의 크기가 정해지면 나중에 새로운 데이터를 추가할 수 없게.. 2020. 6. 8. [C++] Doubly Linked List 이중 연결 리스트 구현 Doubly Linked List 이중 연결 리스트 구현 Doubly Linked List 는 무엇일까? Singly Linked List (단순 연결 리스트) 는 노드 사이의 연결이 단방향 이다. 하지만 Doubly Linked List (이중 연결 리스트)는 노드 사이의 연결이 양방향이다. 각각의 노드는 다음 노드에 대한 연결뿐만 아니라 이전 노드에 대한 연결도 가지고 있다. 그렇기 때문에 Doubly Linked List는 이전 노드, 다음 노드로의 접근이 모두 가능하다. Doubly Linked List의 노드 구조 Doubly Linked List의 구조 첫번째 노드는 이전 노드가 없기 때문에 이전 노드에 대한 링크는 NULL 이다. 또한, 마지막 노드는 다음 노드가 없기 때문에 다음 노드에 대.. 2020. 6. 8. [C 언어] Array Circular Queue 배열 원형 큐 구현 Array Circular Queue 배열 원형 큐 왜 원형 큐 (Circular Queue) 를 사용할까? 1. 기존의 배열 큐 (Array Queue) Memory Overflow 문제를 해결하기 위해서이다.- 배열의 Front 에 빈 노드가 있다고 할지라도, Front에 새로운 노드를 추가하려고 할때 Memory Overflow가 발생한다. 배열 큐의 특성상 배열의 크기는 이미 정해져있기 때문이다.- 배열을 이동시키는 방법으로 이 문제를 해결할 수 있다. 하지만 배열을 이동하는데 O(N)의 시간 복잡도가 필요하다. 따라서 배열의 크기가 커질수록 이 문제는 효율적이지 않은 방법이 된다.- 이 문제를 위한 효과적인 방법은 원형 큐(Circular Queue)를 이용하는것이다. 처럼 dequeue를 실행.. 2020. 6. 7. 이전 1 2 3 다음
