[C언어] 스택과 큐 구현해보기

1. 스택

- 선입 후출 구조

- 맨 처음에 들어간 원소를 top라고 지정한다.

 

1) 배열

ⓐ 구조체 선언

#define SIZE 1000
typedef struct {
	int key;
    // 다른필드
}element;
element stack[SIZE];

 ⓑ push

int top = 0;
void push(int* top_ptr, element item) {
	if (*top_ptr >= SIZE) {
		printf("스택이 다 찼습니다.");
	}
	stack[(*top_ptr)++] = item;
}

ⓒ pop

void pop(int* top_ptr) {
	if (*top_ptr == 0) {
		printf("스택이 비어있습니다.");
	}
	stack[(*top_ptr)--];
}

* push와 pop 모두 매개변수로 포인터를 받는데, *top_ptr 은 top에 주소가 아닌 들어간 데이터 값이다. 

따라서 stack[(*top_ptr)++] 는 stack[ top++]랑 같다. 

 

2) 연결리스트

ⓐ 구조체 선언

typedef struct list_node* list_pointer; // list노드의 주소를 저장할 포인터를 선언함
typedef struct list_node {
	int data; //데이터가 들어감
	list_pointer link; //다음 노드의 주소를 저장할 포인터
};

ⓑ push

void push(list_pointer stack, int item) {
	list_pointer temp;
	temp = (list_pointer)malloc(sizeof(list_node));
	if (temp == NULL) { //동적으로 구조체를 선언했을 때 메모리확보가 불가능하면 null을 반환함
		printf("스택이 다 찼습니다.");
		return;
	}
	temp->data = 10;
	temp->link = stack->link;
	stack->link = temp;	
}

ⓒ pop

void pop(list_pointer stack)
{
	list_pointer temp;
	int item;
	if (stack->link == NULL) { //마지막 삽입한 원소의 주소는 null을 가르키고있다
		printf("스택이 비었습니다.");
		return;
	}
	temp = stack->link;
	item = temp->data;
	stack->link = temp->link;
	free(temp);

}

 

2. 큐

- 선입 선출 구조

- 맨처음에 들어간 원소(삭제가 일어나는 쪽)를 front, 마지막에 들어간 원소(삽입이 일어나는 쪽)를 rear라고 칭한다.

 

ⓐ 배열

#define MAX_QSIZE 1000
typedef struct {
	int key;
	/* other fields here */
} element;
element queue[MAX_QSIZE];
int front, rear = 0;

void enqueue(int* rear_ptr, element item)
{
	if (*rear_ptr >= MAX_QSIZE) {
		printf("큐가 다 찼습니다.");
		return;
	}
	queue[(*rear_ptr)++] = item;
}

void dequeue(int* front_ptr, int rear)
{
	if (*front_ptr == rear) {
		printf("큐가 비어있습니다.");
	}
	queue[(*front_ptr)++];
}

ⓑ 연결리스트 // 코드 수정 필요 (2021.04.17~)

typedef struct list_node* list_pointer; // list노드의 주소를 저장할 포인터를 선언함
typedef struct list_node {
	int data; //데이터가 들어감
	list_pointer link; //다음 노드의 주소를 저장할 포인터
};

struct LinkedQueue {
	list_node* front, * rear;
	LinkedQueue() {
		front = rear = NULL; 
	}
};


void enqueue(list_pointer node, int item)
{
	list_pointer node = (list_pointer)malloc(sizeof(list_node)); //새로운 큐 추가
	node->data = item; //큐의 데이터 삽입
	node->link = NULL; 

	if (front == NULL) {
		printf("큐가 다 찼습니다.");
		return;
	}
	else {
		rear->link = queue;
		rear = rear->link;
	}
	
}

void dequeue(list_pointer queue)
{
	if (queue->link == NULL) {
		printf("큐가 비어있습니다.");
		return;
	}

	list_pointer node = front;
	int tmp = node->data;
	front = node->link;
	free(node);

}

 

 

 

 

* 원형 큐(Circular Queue)

- 원처럼 생긴 큐이다.

그림으로 쉽게 이해가 된다.

- 큐가 다 차있을 때는 rear+1 = front, 큐가 비어있을 때는 rear = front 이다.

 

- 코드 구현

void enqueue(int *rear_ptr, int front, element item)
{
 	if ((*rear_ptr + 1) % MAX_QSIZE == front) {
 	printf("큐가 다 찼습니다.");
 	return;
 }
 	queue[*rear_ptr] = item;
	*rear_ptr = (*rear_ptr + 1) % MAX_QSIZE;
}

void dequeue(int *front_ptr, int rear)
{
 	int k;
 	if (*front_ptr == rear) {
 	printf("큐가 비어있습니다.");
 	}
 	k = *front_ptr;
 	*front_ptr = (*front_ptr + 1) % MAX_QSIZE;
}

> (*rear_ptr+1)%MAX_QSIZE 의 의미 : 큐사이즈가 만약에 1000이고, *rear_ptr +1 = 1001 이면 

나머지는 1이되므로 front는 가장 마지막에 들어간 원소의 인덱스이므로 1이된다. 그러므로 큐가 다찼다는 뜻