CSE 전공노트

지난 글에서 큐에 대한 대략적인 개념을 공부했습니다. 하지만 앞에서 공부했던 대로 큐를 구현하게 되면 문제가 한 가지 존재합니다. 바로 add와 delete를 반복적으로 계속 수행하다 보면 front와 rear는 계속 증가하게 될 것이고, 그러면 아래의 그림과 같이 배열에 안쓰는 부분이 계속 증가하여 공간을 낭비하게 됩니다. 그래서 front와 rear가 너무 커지게 되면 이것을 다시 앞으로 당겨주는 작업이 필요하게 됩니다. 하지만 아무래도 이러한 작업이 번거롭다 보니 circular queue (원형 큐)라는 것이 등장합니다. 원형 큐는 위의 그림과 같은 형태로 큐의 양 쪽 끝을 이어놓은 형태입니다. 이런 형태로 구현을 하면 굳이 뒤로 밀린 front와 rear를 앞으로 당기지 않고 계속 순환하면서 큐..

오늘은 큐에 대해서 공부해보려고 합니다. 큐는 앞에서 살펴본 스택과는 달리 삽입과 삭제가 다른 방향으로 나오는 형태의 리스트를 뜻합니다. 먼저 삽입된 데이터가 먼저 나오는 형태입니다. 이 때문에 First-In-First-Out (FIFO) list라고도 부릅니다. 스택에서는 top을 이용해서 배열을 관리하는 것처럼, 큐에서는 front, rear 두 개의 변수를 이용합니다. front는 큐의 앞 쪽 끝을 가리키고, rear는 큐의 제일 뒤 쪽 끝을 가리키게 됩니다. 기본적인 형태는 다음과 같습니다. front와 rear는 -1로 초기화하여 선언합니다. 데이터가 추가될 때마다 제일 뒤를 가리키는 변수인 rear가 1씩 증가하고, 데이터가 삭제될 때마다 가장 앞을 가리키는 변수인 front가 1씩 증가합니..

스택은 삽입과 삭제가 리스트의 한쪽 끝에서만 일어나는 자료구조입니다. 스택에 뭔가를 추가하는 것을 push라고 하고, 삭제하는 것을 pop이라고 합니다. 스택은 전형적인 후입선출 (Last-In-Frist-Out)의 형태로써, 아래의 그림처럼 구현됩니다. Push를 실행하게 되면 가장 위에 데이터를 쌓아 올리고, pop을 실행하면 가장 위에서부터 데이터를 삭제하게 됩니다. 스택은 C로 구현하면 다음과 같이 구현할 수 있습니다. 스택은 1차원 배열을 이용하여 구현을 하게 됩니다. #define MAX_STACK_SIZE 100 //Stack의 최대 사이즈 typedef struct { int key; // 변수는 더 추가해도 상관없습니다. 변수가 하나밖에 없다면 굳이 구조체를 만들지 않고 구현해도 됩니다...