[C로 쓴 자료구조] 연결 리스트의 Stack & Queue

 

 

배열을 이용한 스택과 큐의 구현 방법에는 메모리 낭비, Stack Full의 발생 가능성이라는 문제점이 있다.

따라서 연결 리스트를 이용해 스택과 큐를 구현해 유동적으로 메모리를 관리해보자.

 

 

리스트를 이용한 스택과 큐의 구현

 

 

---

Stack

 

 

스택 선언

 

스택의 초기 조건 : top = NULL;

경계 조건 : top = NULL if stack is empty.

                  IS_FULL(temp) if the memory is full.

 

struct element {
	int key;
};

struct stack {
	element data;
	struct stack* link;
};

struct stack *top;

 

 

스택에 노드 추가 (push)

 

스택의 제일 앞부분에 push 하는 연산은 time complexity O(1)

제일 뒷부분에 push 하는 연산은 time conplexity O(n)을 가진다.

 

void push(element item) { //스택 top에 새로운 item 추가

	struct stack *temp;
	temp = (struct stack*)malloc(sizeof(struct stack));

	if (temp == NULL) {
		fprintf(stderr, "The memory is full\n");
		exit(1);
	}

	temp->data = item;
	temp->link = top;
	top = temp;
}

 

 

스택에서 삭제 (pop)

 

element pop() { //스택의 top이 가리키는 element를 삭제하여 return
	struct stack *temp;
	temp = top;
	element item;

	if (temp == NULL) { //top==NULL
		fprintf(stderr, "The stack is empty\n");
		exit(1);
	}

	item = temp->data;
	top = temp->link;
	free(temp);
	return item;
}

 

 

---

 

Queue

 

 

큐 선언

 

큐의 초기 조건 : front = NULL;

경계 조건 : front = NULL if queue is empty.

                  IS_FULL(temp) if the memory is full.

 

front : 리스트의 맨 앞을 가리키는 포인터

rear : 리스트의 맨 뒤를 가리키는 포인터

 

struct element {
	int key;
};

struct Queue {
	element data;
	struct Queue *link;
};

struct Queue *front, *rear;

 

 

큐에 노드 추가 (Inqueue)

 

rear 앞에 새로운 노드 추가

void addq(element item)
{
	// 큐의 rear에 새로운 element 추가
	struct Queue* temp;
	temp = (struct Queue*)malloc(sizeof(struct Queue));
	if (temp == NULL) { // memory full
		fprintf(stderr, "The memory is full\n");
		exit(1);
	}
	temp->data = item;
	temp->link = NULL;
	if (front) 
		rear->link = temp;
	else 
		front = temp;
	rear = temp;
}

 

 

큐에서 노드 삭제 (Dequeue)

 

rear가 가리키고 있는 노드를 삭제하는 delete last는 rear의 앞 노드를 알고 있어야 하기 때문에 구현하기 매우 까다롭다

 

front가 가리키는 노드 삭제

element deleteq()
{
	// 큐에서 front가 가리키는 노드 삭제 후 element는 return
	struct Queue *temp = front;
	element item;
	if (temp == NULL) { // *front == NULL
		fprintf(stderr, "The queue is empty\n");
		exit(1);
	}
	item = temp->data;
	front = temp->link;
	free(temp);
	return item;
}

 

 

구조체 연결리스트 큐 구현

 

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>


struct element {
	int reach;
	int amount;
	int priority;
};

struct Queue {
	element data;
	struct Queue* link;
};

struct Queue *front=NULL, *rear=NULL;

void addq(element item)
{
	// 큐의 rear에 새로운 element 추가
	struct Queue* temp;
	temp = (struct Queue*)malloc(sizeof(struct Queue));
	if (temp == NULL) { // memory full
		fprintf(stderr, "The memory is full\n");
		exit(1);
	}
	temp->data.reach = item.reach;
	temp->data.amount = item.amount;
	temp->data.priority = item.priority;
	temp->link = NULL;
	if (front)
		rear->link = temp;
	else
		front = temp;
	rear = temp;
}

element deleteq()
{
	// 큐에서 front가 가리키는 노드 삭제 후 element는 return
	struct Queue* temp = front;
	element item;
	if (temp == NULL) { // *front == NULL
		fprintf(stderr, "The queue is empty\n");
		exit(1);
	}
	item = temp->data;
	front = temp->link;
	free(temp);
	return item;
}

void print_queue() {
	
	struct Queue* temp;
	temp = front;
	for (temp; temp != NULL; temp = temp->link) {
		printf("%d\n", temp->data.reach);
		printf("%d\n", temp->data.amount);
		printf("%d\n", temp->data.priority);

	}
}