연결리스트로 구현한 스택(Stack), 큐(Queue)

지금까지 스택과 큐를 구현할 때 배열을 이용하여 구현하였다.

배열을 이용하여 구현하게 되면 간단하다는 장점은 있지만 용량이 고정된다는 단점도 존재한다.

배열은 동적으로 크기를 늘리거나 줄일 수 없기 때문에 처음 할당한 공간이 가득 차면 더 이상 데이터를 더 추가할 수 없기 때문이다.

용량이 자동으로 변할 수 있는 보다 자유로운 방법을 구현하기 위해 연결된 표현(linked representation)을 사용한다.

연결된 표현은 데이터와 링크로 구성되고 링크가 노드들을 연결하는 역할을 하게 된다.

용량이 고정되지 않는 장점 덕분에 스태이나 큐 뿐만 아니라 리스트나, 덱, 트리, 그래프 등 여러가지 자료구조를 구현하는데 널리 사용 된다.

연결된 표현(linked representation)의 특징

1. 데이터를 한군데 모아두는 것을 포기한다.

2. 데이터들은 메인 메모리상의 어디에나 흩어져서 존재할 수 있다.

3. 순서를 유지하기 위해 각각의 데이터는 다음 데이터를 가리키는 줄을 가진다.

4. 첫 데이터에서부터 순서대로 줄을 따라가면 모든 데이터를 방문할 수 있다.

이와 같이 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법을 연결 리스트(linked list)라고 한다.

이 때 상자를 이용하는 줄을 포인터가 된다.

배열에 비해 연결리스트는 다음과 같은 장점을 갖는다.

연결리스트의 장점

1. 크기가 고정되지 않는다. 배열을 사용하면 처음 선언한 크기로 고정되는데 비해 연결 리스트는 메모리를 할당할 수 있는 한 계속 자료를 넣을 수 있다.

2. 중간에 자료를 삽입하는 것이 용이하다.

연결 리스트의 특징

1. 노드들은 메모리의 어느 곳에나 위치할 수 있다. 즉, 노드들의 주소가 연결 리스트 상의 순서와 동일하지 않다.

2. 연속적인 기억공간이 없어도 데이터를 저장하는 것이 가능하고 미리 공간을 확보할 필요도 없다. 필요할 때마다 동적으로 노드를 생성해 연결하기 때문이다.

3. 링크 필드를 위한 추가 공간이 필요하다.

4. 연산의 구현이나 사용 방법이 배열에 비해 복잡하다. 이것은 프로그래밍이 어려워지고 오류가 발생할 가능성도 많아지는 것을 의미한다.

연결된 스택 테스트 프로그램

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

typedef int Element;

typedef struct LinkedNode {
	Element data;
	struct LinkedNode* link;
}Node;

Node* top = NULL;

void error(char* str)
{
	fprintf(stderr, "%s\n", str);
	exit(1);
}

int is_empty() { return top == NULL; }
void init_stack() { top = NULL; }

void push(Element e)
{
	Node* p = (Node*)malloc(sizeof(Node));
	p->data = e;

	p->link = top;
	top = p;
}

Element pop()
{
	Node* p;
	Element e;
	if (is_empty())
		error("스택 공백 에러");
	
	p = top;
	top = p->link;
	e = p->data;
	free(p);
	return e;
}

Element peek()
{
	if (is_empty())
		error("스택 공백 에러");
	return top->data;
}

void destory_stack()
{
	while (is_empty() == 0)
		pop();
}

int size()
{
	Node* p;
	int count = 0;
	
	//for (p = top; p != NULL; p = p->link) count++;
	p = top;

	while (p != NULL)
	{
		p = p->link;
		count++;
	}

	return count;
}

void print_stack(char* msg)
{
	Node *p;
	printf("%s[%2d]= ", msg, size());
	for (p = top; p != NULL; p = p->link)
		printf("%2d ", p->data);
	printf("\n");
}

void main()
{
	int i;

	init_stack();
	for (i = 1; i < 10; i++)
		push(i);
	print_stack("연결된스택 push 9회");
	printf("\tpop() --> %d\n", pop());
	printf("\tpop() --> %d\n", pop());
	printf("\tpop() --> %d\n", pop());
	print_stack("연결된스택 pop 3회");
	destory_stack();
	print_stack("연결된스택 destroy");

	
}

학생 정보 큐 테스트 프로그램

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

typedef struct Student {
	int id;
	char name[32];
	char dept[32];
}Student;

typedef Student Element;

typedef struct LinkedNode {
	Element data;
	struct LinkedNode* link;
}Node;

Node* front = NULL;
Node* rear = NULL;

void error(char* str)
{
	fprintf(stderr, "%s\n", str);
	exit(1);
}

int is_empty() { return front == NULL; }
void init_queue() { front = rear = NULL; }

int size()
{
	Node* p;
	int count = 0;
	for (p = front; p != NULL; p = p->link) count++;
	return count;
}

void enqueue(Element e)
{
	Node* p = (Node*)malloc(sizeof(Node));
	p->data = e;
	p->link = NULL;
	
	if (is_empty()) front = rear = p;
	else {
		rear->link = p;
		rear = p;
	}
}

Element dequeue()
{
	Node* p = (Node*)malloc(sizeof(Node));
	Element e;

	if (is_empty())
		error(" 큐 공백 에러");
	p = front;

	front = front->link;
	
	if (front == NULL) rear = NULL;

	e = p->data;
	free(p);
	return e;
}

Element peek()
{
	if (is_empty())
		error(" 큐 공백 에러");
	return front->data;
}

void destroy_queue()
{
	while (is_empty() == 0)
		dequeue();
}

void print_queue(char* msg)
{
	Node *p;
	printf("%s[%2d]= ", msg, size());
	for (p = front; p != NULL; p = p->link)
		printf("\n\t%-15d %-10s %-20s", p->data.id, p->data.name, p->data.dept);
	printf("\n");
}

Student get_student(int id, char* name, char* dept)
{
	Student s;
	s.id = id;
	strcpy(s.name, name);
	strcpy(s.dept, dept);
	return s;
}

void main()
{
	init_queue();
	enqueue(get_student(2018130007, "홍길동", "컴공"));
	enqueue(get_student(2018130007, "홍길동2", "컴공"));
	enqueue(get_student(2018130007, "홍길동3", "컴공"));
	enqueue(get_student(2018130007, "홍길동4", "컴공"));
	
	print_queue("연결된큐 학생큐(4명 삽입)");
	dequeue();
	print_queue("연결된큐 학생큐(1명 삭제)");
	destroy_queue();
	print_queue("연결된큐 destroy ");


}