[자료구조] 리스트 큐 (ListBasedQueue / Linked Queue)

 

 

 

node를 사용해서 linked-queue라고도 불림

 

리스트 기반으로도 큐를 구현할 수 있다.

오히려 구현하는데 신경쓸게 별로 없다.

앞선 원형큐보다 간단하다.

enqueue dequeue 할때 malloc free 순서 좀만 신경써주면된다.

 

하지만 노드를 사용하기에 그냥 배열을 사용하는 원형큐보다는 메모리를 더 쓴다

 

---

typedef int Data;

typedef struct node {
	Data data;
	Node* next;
}Node;

typedef struct queue {
	Node* front;
	Node* rear;
}Queue;

 

void QueueInit(Queue* pq) {
	pq->front = NULL;
	pq->rear = NULL;
}

 

int QISEmpty(Queue* pq) {
	pq->front==NULL ? 1 : 0;
}

 

void Enqueue(Queue* pq,Data data) {
	(pq->front)->next = (Node*)malloc(sizeof(Node));
	pq->rear = pq->front->next;
	(pq->rear)->data = data;
}

 

Data Dequeue(Queue* pq) {
	Node* delNode = pq->front;
	Data retData = (pq->front)->data;
	pq->front = delNode->next;
	free(delNode);
	return retData;
}

 

Data QPeek(Queue* pq) {
	return pq->front->data;
}