[자료구조] Chapter3. STACKS AND QUEUES(1)

※ 이 카테고리의 글들은 knu EK.Ryu 교수님의 <자료구조> 수업을 듣고 나름대로 필자가 정리한 글입니다.

※ 부족한 설명이 있거나, 잘못 알고 작성한 부분이 보인다면 편하게 댓글로 알려주시면 정말 감사하겠습니다😊

3.1 Stack

스택은 데이터를 저장하고 삭제하는데 LIFO(Last In, First Out) 방식으로 작동하는 자료구조입니다. 즉, 마지막에 들어온 데이터가 가장 먼저 나가는 구조입니다.

위 그림에서 보이는 것처럼, A, B, C, D, E 순서로 데이터를 넣고, 삭제할 때는 E부터 제거됩니다.

 

스택에 데이터를 넣고(push), 빼는(pop) 함수에 대해서 아래에서 알아보겠습니다.

void push(element item) // 데이터 추가
{
    if (top >= MAX_STACK_SIZE - 1)
        stackFull();
    stack[++top] = item;
}

void stackFull() // 스택이 꽉 찼을 때 오류 출력
{
    fprintf(stderr, "Stack is full, cannot add element");
    exit(EXIT_FAILURE);
}

element pop() // 스택에서 데이터 뽑기(가장 위에 있는!)
{
    if (top == -1)
        return stackEmpty();
    return stack[top--];
}

 

 

3.2 Stacks Using Dynamic Arrays

배열을 이용한 스택은 데이터가 스택의 용량을 넘어서 쌓일 수 없습니다.

하지만 동적 할당을 이용한다면, 스택의 크기가 가득 찰 때 동적으로 배열을 두 배 늘려 이 문제를 극복할 수 있습니다.

pop() 함수는 그대로이고, push() 함수와 stackFull() 함수는 아래와 같이 변경하면 됩니다.

void push(element item)
{
    if (top >= capacity - 1)
        stackFull();
    stack[++top] = item;
}

void stackFull()
{
    REALLOC(stack, 2 * capacity * sizeof(*stack));
    capacity *= 2;
}

 

 

3.3 Queues

큐는 FIFO(First In, First Out) 방식으로 동작하는 자료구조로, 먼저 들어온 데이터가 먼저 나가는 구조입니다.

삽입은 큐의 뒤쪽(rear)에서 이루어지고, 삭제는 앞쪽(front)에서 이루어집니다.

큐를 구현하는 방법에는 두 가지 방법이 있습니다.

1. 1차원 배열을 이용한 큐

2. 1차원 배열을 원형으로 연결하여 이용하는 원형 큐

 

(1) 1차원 배열 큐

먼저 1차원 배열 큐를 코드로 작성해 보겠습니다.

void addq(element item)
{
	// add an item to the queue
    if (rear == MAX_QUEUE_SIZE - 1)
        queueFull();
	queue[++rear] = item;
}

element deleteq()
{
	// remove element at the front of the queue
	if (front == rear)
		return queueEmpty();
	return queue[++front];
}

이 1차원 배열 큐에는 작업을 진행하면서 큐가 점점 오른쪽으로 이동하게 된다는 문제가 있습니다.

이를 해결하기 위해서는 배열의 모든 원소를 왼쪽으로 이동시키는 배열 이동(array shifting) 작업이 필요합니다. 하지만 이 작업에도 시간 복잡도가 O(MAX_QUEUE_SIZE)로 매우 비호율적이기 때문에 대안으로 원형큐라는 자료구조를 사용합니다.

 

(2) 원형 큐 Circular Queue

원형 큐는 배열의 끝에서 다시 배열의 처음으로 돌아갈 수 있도록 구현되어, 배열의 끝에 도달했을 때 전체를 다시 이동시키지 않고도 효율적으로 큐를 사용할 수 있게 해 줍니다.

아래 코드에서 원형 큐의 삽입, 삭제 코드를 확인해 봅시다.

void addq(element item)
{
	rear = (rear + 1) % MAX_QUEUE_SIZE;
	if (front == rear)
		queueFull();
	queue[rear] = item;
}

element deleteq()
{
	if (front == rear)
		return queueEmpty();
	front = (front + 1) % MAX_QUEUE_SIZE;
	return queue[front];
}

코드를 통해 원형 큐의 특징을 하나 알 수 있는데, 큐는 꽉 찼을 때도 리스트의 한 자리가 비어있게 됩니다.

이는 원형 큐에서 front와 rear가 동일할 때 큐가 비어있는 상태와 가득 찬 상태를 구분하기 위해 필요합니다.

 

3.4 Circular Queues using Dynamic Arrays

원형 큐가 가득 찼을 때 데이터를 더 추가하고 싶다면 동적할당을 이용할 수 있습니다. 

위 이미지는 원형 큐가 가득 찼을 때를 표현한 것으로, 실제로 원형 큐는 1차원 배열 형태이기 때문에 (b)의 형태를 갖고 있습니다.

(b)의 상태에서 realloc을 하여 원형 큐의 크기를 2배 늘린다면, 문제가 발생할 수 있습니다. 원형 큐의 특징을 고려하지 않아, (c)의 그림에서 보이듯이 가운데에 큰 빈 공간이 발생할 수 있습니다.

(d): 이를 예방하기 위해서는 6, 7번 index에 들어있는 값들을 오른쪽 끝으로 shifting 시켜 해결하거나,

(e): 꽉 찬 배열의 값들을 복사 후, malloc을 사용하는 방법이 있습니다.

 

원형 큐의 크기를 동적할당으로 늘리는 두 방법을 비교해 봅시다: realloc --> shifting vs malloc

먼저, 첫 번째 방법을 이용하면 배열을 2배로 확장하고 원소를 오른편으로 미는 것을 다 합쳤을 때 최대 2 * capacity - 2의 원소를 복사하게 됩니다.

 

두 번째 방법에서는 배열 크기를 malloc을 이용해서 배가할 때 값들을 잘 복사해서 넣음으로써 capacity-1로 복사할 원소 수를 줄일 수 있습니다.

 

두 번째 방법의 코드를 한 번 작성해봅시다.

이 코드에서 함수 copy(a, b, c)는 위치 a에서 b-1까지의 원소를 c에서 시작하는 위치로 복사하는 함수입니다.

void addq(element item)
{
	rear = (rear + 1) % MAX_QUEUE_SIZE;
	if (front == rear)
		queueFUll();
	queue[rear] = item;
}

void queueFUll()
{
	// 이전 큐의 크기를 두 배로 확장
	element* newQueue;
	MALLOC(newQueue, 2 * capacity * sizeof(*queue));

	// 큐의	데이터를 새로운 큐로 복사
	int start = (front + 1) % capacity;
	if (start < 2)
		copy(queue + start, queue + start + capacity - 1, newQueue);
	else
	{
		copy(queue + start, queue + capacity, newQueue);
		copy(queue, queue + rear + 1, newQueue + capacity - start);
	}

	// 새로운 큐의 정보를 업데이트
	front = 2 * capacity - 1;
	rear = capacity - 2;
	capacity *= 2;
	free(queue);
	queue = newQueue;
}

원형 큐가 리스트에서 하나의 segment일 경우

 

원형 큐가 리스트에서 두 개의 세그먼트로 나눠질 경우

 

 

다음 장에서는 스택과 큐를 사용하는 문제들을 공부해봅시다.😆