[C] 연결리스트(Linked List)로 큐(Queue) 구현

by

서론

큐의 필수함수인 push, pop, top(=front)를 C로 구현했다.

다른 글

[C] 단방향 연결리스트(Linked List) 구현

구현

//c++

#include <iostream>

typedef struct list {
	int item;
	list *next;
}list;

typedef struct queue {
	list *front;
	list *rear;
	int cnt;
}queue;

void create(queue *q) {
	list *head = (list*)malloc(sizeof(list));
	head->item = NULL;
	head->next = NULL;

	q->cnt = 0;
	q->front = q->rear = head;
}

void push(queue* q, int item) {
	list *tmp = (list*)malloc(sizeof(list));
	tmp->item = item;
	tmp->next = NULL;
	if (q->front->item == NULL) {
		q->front = q->rear = tmp;
	}
	else {
		q->rear->next = tmp;
		q->rear = tmp;
	}
	q->cnt++;
	//std::cout << q->rear->item << std::endl;
}

void pop(queue* q) {
	list *tmp = (list*)malloc(sizeof(list));
	tmp = q->front;
	q->front = q->front->next;
	free(tmp);
	q->cnt--;
	//std::cout << q->front->item << std::endl;
}

int top(queue *q) {
	if (q->front != NULL) return q->front->item;
	else return -1;
}

int main() {
	int n;
	std::cin >> n;
	queue q;
	create(&q);
	for (int i = 1; i <= n; i++) {
		push(&q, i);
	}
	while (q.cnt != 1) {
		//std::cout << top(&q) << std::endl;
		pop(&q);
		push(&q, top(&q));
		pop(&q);
	}
	std::cout << top(&q);
}

Leave a Comment