[Data Structure] 연결리스트 응용 : 덱

연결리스트 덱

- 연결리스트를 이용한 덱 (이중 연결 리스트)

- front, rear 둘다 삽입/삭제가 되기 때문에 이중 연결 리스트로 구현

 

 

[코드 - C]

#include <stdio.h>
#include <stdlib.h>
// 연결리스트를 이용한 덱 (이중 연결 리스트)
// front, rear 둘다 삽입/삭제가 되기 때문에 이중 연결 리스트로 구현

typedef int element;
typedef struct dnode{
	element data;
	struct dnode* llink;
	struct dnode* rlink;
}dnode;

dnode* front;
dnode* rear;

int is_empty() {
	return front == NULL; // 공백 상태이면 front == NULL
}

void add_rear(element item) {
	dnode* new_node = (dnode*)malloc(sizeof(dnode));
	new_node->data = item;
	if (is_empty()) {
		front = new_node;
		rear = new_node;
		new_node->llink = NULL;
		new_node->rlink = NULL;
	}
	else {
		new_node->rlink = NULL;
		new_node->llink = rear;
		rear->rlink = new_node;
		rear = new_node;
	}
}

void add_front(element item) {
	dnode* new_node = (dnode*)malloc(sizeof(dnode));
	new_node->data = item;
	if (is_empty()) {
		front = new_node;
		rear = new_node;
		new_node->llink = NULL;
		new_node->rlink = NULL;
	}
	else {
		new_node->llink = NULL;
		new_node->rlink = front;
 		front->llink = new_node;
		front = new_node;
	}
}

element delete_front() {
	if (is_empty()) {
		fprintf(stderr, "Error : Stack is empty\n\n");
		return;
	}
	else {
		dnode* removed = front;
		element item = removed->data;
		if (removed->rlink == NULL) {
			front = NULL;
			rear = NULL;
			free(removed);
			return item;
		}
		else {
			front = removed->rlink;
			removed->rlink->llink = NULL;
			free(removed);
			return item;
		}
	}
}

element delete_rear() {
	if (is_empty()) {
		fprintf(stderr, "Error : Stack is empty\n\n");
		return;
	}
	else {
		dnode* removed = rear;
		element item = removed->data;
		if (removed->llink == NULL) {
			front = NULL;
			rear = NULL;
			free(removed);
			return item;
		}
		else {
			rear = removed->llink;
			removed->llink->rlink = NULL;
			free(removed);
			return item;
		}
	}
}

element peek_rear() {
	if (is_empty()) {
		fprintf(stderr, "Error : Queue is empty\n\n");
		return;
	}
	else
		return rear->data;
}

element peek_front() {
	if (is_empty()) {
		fprintf(stderr, "Error : Queue is empty\n\n");
		return;
	}
	else
		return front->data;
}

void print_deque() {
	if (is_empty()) {
		fprintf(stderr, "Deque is empty\n\n");
		return;
	}
	else {
		dnode* p = front;
		printf("(front) <-> |");
		while (p) {
			printf(" %d ", p->data);
			p = p->rlink;
		}
		printf("| <-> (rear)\n\n");
	}
}

int main(void) {
	print_deque();
	printf(">>> add_rear 10\n"); add_rear(10); // 10
	print_deque();
	printf(">>> add_rear 20\n"); add_rear(20); // 10 20
	print_deque();
	printf(">>> add_front 30\n"); add_front(30); // 30 10 20
	print_deque();
	printf(">>> add_front 40\n"); add_front(40); // 40 30 10 20
	print_deque();

	printf(">>> peek_rear()\n>>> peek_rear된 data : %d\n\n", peek_rear());
	printf(">>> peek_front()\n>>> peek_front된 data : %d\n\n", peek_front());

	printf(">>> delete_rear\n>>> delete_rear된 data : %d\n", delete_rear()); // 40 30 10 
	print_deque();
	printf(">>> delete_front\n>>> delete_front된 data : %d\n", delete_front()); // 30 10
	print_deque();
	printf(">>> delete_rear\n>>> delete_rear된 data : %d\n", delete_rear()); // 30
	print_deque();
	printf(">>> peek_rear()\n>>> peek_rear된 data : %d\n\n", peek_rear());
	printf(">>> peek_front()\n>>> peek_front된 data : %d\n\n", peek_front());
	print_deque();
	printf(">>> delete_front\n>>> delete_front된 data : %d\n\n", delete_front());
	print_deque();
}