자료구조/스택 & 큐

큐? 큐는 선입 선출구조로, 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입 선출구조입니다. 큐에 데이터를 추가하는 작업을 enqueue, 데이터를 꺼내는 작업을 dequeue, 데이터를 꺼내는 쪽을 front, 데이터를 넣는 쪽을 rear라고 합니다. 배열로 큐 구현하기 1. enqueue 데이터 x를 enqueue하려면 배열 que의 마지막 원소의 인덱스인 idx의 다음 인덱스인 idx + 1에 추가합니다. que[idx + 1] = x 이때 처리의 복잡도는 O(1)이고, 비교적 적은 비용으로 구현할 수 있습니다. 2. dequeue 데이터 y를 dequeue하려면 배열 que의 0번째 원소를 꺼내고, 이후의 원소들을 앞쪽으로 옮겨야 합니다. 이때의 처리 복잡도는 O(n)으로, 데이터를 꺼낼 때마다 ..

스택이란? 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식입니다. PUSH로 데이터를 스택에 넣고, POP을 통해 데이터를 스택에서 꺼냅니다. 스택 구현하기 1. 스택 초기화 스택 배열 stk는 푸시한 데이터를 저장하는 스택 본체인 리스트형 배열입니다. 인덱스가 0인 원소를 스택의 바닥이라고 하며, 데이터가 스택에 추가되는 PUSH 작업이 수행되면 stk[0]에 저장됩니다. 그렇다면 고정 길이의 스택 stk 배열을 구현할 때 어떤 인자를 전달해야할까요? 바로 스택의 최대 크기를 나타내는 capacity와 현재 스택에 쌓여 있는 데이터의 개수를 나타내는 stack pointer입니다. 그렇다면 고정길이 스택 클래스인 FixedStack의 init 메서드를..