밤빵몬의 컴퓨터

리스트 리스트에는 항목들이 차례대로 저장되어 있다. 리스트의 항목들은 순서 또는 위치를 가진다. 앞서 살펴본 스택과 큐도 넓게 보면 리스트의 일종이다. 집합은 각 항목 간에 순서의 개념이 없기 때문에 리스트는 집합하고는 다르다. 리스트의 구현 리스트는 배열과 연결 리스트를 이용하여 구현할 수 있다. 1. 배열을 이용한 구현 배열을 이용하면 리스트를 가장 간단하게 구현할 수 있다. 장점은 구현이 간단하고 속도가 빠르다는 것이다. 단점은 리스트의 크기가 고정된다는 것이다. 따라서 만약 데이터를 추가하고 싶은데 더 이상 남은 공간이 없다면 문제가 발생한다. 또한 리스트 중간에 새로운 데이터를 삽입하거나 삭제하기 위해서는 기존의 데이터들을 이동하여야 한다. 배열을 이용하여 리스트를 구현하면 순차적인 메모리 공간..

원형 큐의 구조 원형 큐는 선형 큐의 front와 rear값이 계속 증가하기만 한다는 문제점을 극복한 구조이다. 배열을 선형으로 생각하지 않고 원형으로 생각한다. 즉, front와 rear의 값이 배열의 끝인 (MAZ_QUEUE_SIZE -1)에 도달하면 다음에 증가되는 값은 0이 되도록 하는 것이다. 원형 큐의 삽입, 삭제 원형 큐에서는 front와 rear 의 개념이 약간 변경된다. 먼저 초기 값은 -1이 아닌 0이다. front는 항상 큐의 첫 번째 요소의 하나 앞을, rear는 마지막 요소를 가리킨다. 처음에 front, rear는 모두 0이고 삽입 시에는 rear가 먼저 증가되고, 증가된 위치에 새로운 데이터가 삽입된다. 또 삭제 시에도 front가 먼저 증가된 다음, 증가된 위치에서 데이터를 ..

큐의 구조 FIFO: First-In First-Out 큐는 먼저 들어온 데이터가 먼저 나가는 구조이다. 이러한 형태를 선입 선출이라고 한다. 큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조를 가지고 있다. 큐에서 삽입이 일어나는 곳을 후단(rear)라 하고 삭제가 일어나는 곳을 전단(front)라고 한다. 큐의 삽입, 삭제 큐로의 삽입 연산은 enqueue연산이라고 하고 삭제 연산은 dequeue연산이라고 한다. enqueue연산은 큐에 요소를 추가하는 연산으로서 큐의 맨 뒤에 새로운 요소를 추가한다. dequeue연산은 큐의 맨 앞에 있는 요소를 꺼내서 외부로 반환한다. 그림 2는 큐에서의 enqueue와 dequeue연산을 보여준다. 큐에서 enqueue(A)를 수행하면 ..

스택의 구조 LIFO: Last-In First-Out 스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다. 이러한 입출력 형태를 후입 선출이라고 한다. 스택에서 입출력이 이루어지는 부분을 스택 상단(Stack top)이라 하고 반대쪽인 바닥 부분을 스택 하단(Stack bottom)이라고 한다. 스택에 저장되는 것을 요소(element)라 부른다. 스택에 요소가 하나도 없을 때 그러한 스택을 공백 스택(empty stack)이라고 한다. 스택의 삽입, 삭제 스택의 삽입과 삭제는 모두 스택 상단에서 발생한다. 스택으로의 삽입 연산은 push 연산이라고 하고 삭제 연산은 pop 연산이라고 한다. 그림 2는 스택에서의 push와 pop연산을 보여준다. 공백 스택에서 push(..