자료구조3 Queue 개요 한 쪽 끝에선 삽입, 다른 쪽 끝에선 삭제가 일어나는 자료구조 Queue의 성질 First-in First-out (FIFO), 즉 선입선출 방식으로 객체를 담는다. rear에 삽입하고 front에서 삭제한다. Queue 대표적인 operation은 enqueue, dequeue가 있고, 추가로 front, size, empty 등을 지원할 수 있다. Array 또는 Linked List로 구현할 수 있다. Array의 크기를 변경하기 곤란하다는 점을 고려하여 환형으로 구성하면 시간복잡도를 낮출 수 있다. 배열에서 큐의 시작점, 끝점, 크기를 기억하는 변수를 만들어서 구현할 수 있다. 아래는 Array기반 큐의 구현 예시이다. (Linked list 기반 큐는 SLL과 똑같다.) struct Arr.. 2020. 10. 26. Stack 개요 한 쪽 끝에서만 삽입 삭제가 일어나는 자료구조 Stack의 성질 Last-in First-out (LIFO), 즉 후입선출 방식으로 객체를 담는다. 삽입과 삭제에 쓸 위치를 알고 있어야 한다. Stack 대표적인 operation은 push, pop이 있고, 추가로 top, size, empty 등을 지원할 수 있다. Array 또는 Linked List로 구현할 수 있다. 아래는 각각에 대한 예시이다. struct ArrayStack { int* stack; int maxSize, sz; ArrayStack(int ms) { maxSize = ms; sz = 0; stack = new int[maxSize]; } void push(int data); int pop(); } struct Node {.. 2020. 10. 26. Array 개요 동일 자료형 원소들의 sequence. TYPENAME name[SIZE] 의 꼴로 쓴다. Array의 성질 index를 이용해 각 원소를 임의 참조할 수 있다. [0 : N) 크기를 미리 정해야 한다. Insertion index i에 원소 e를 삽입할 때, index가 i 이상인 모든 원소를 shift 한다. $O(n)$ Deletion index i의 원소를 삭제할 때, index가 i 이상인 모든 원소를 shift 한다. $O(n)$ Array의 원소들은 연속하여야 하기 때문이다. Implementation 아래는 이론에서 배운 내용을 구현한 코드이다. #include using namespace std; /* # Insert(i, e)O(n) # Remove(i)O(n) # at(i)O(1.. 2020. 10. 25. 이전 1 다음
