덱(deque) 자료구조

Double Linked List 소스코드입니다.

#include "iostream"
using namespace std;

#define MAX_NODE 1000
#define INIT_DATA -1

typedef int T;
typedef struct _node {
	T data;
	struct _node *prev, *next;
} NODE;
NODE node_list[MAX_NODE + 1];
int node_idx;

NODE *head;
int node_count;

NODE *alloc_node() {
	NODE *new_node = &node_list[node_idx++];
	new_node->prev = new_node->next = 0;
	return new_node;
}

void init() {
	node_idx = 0;
	node_count = 0;
	head = new NODE();
	head->data = INIT_DATA;
	head->prev = head->next = head;
}

void push_next(NODE *node, T data) {
	NODE *next = node;
	NODE *before = node->prev;
	NODE *new_node = alloc_node();
	new_node->data = data;
	new_node->next = next;
	new_node->prev = before;

	before->next = new_node;
	next->prev = new_node;
	node_count++;
}

T remove_node(NODE *node) {
	NODE *before = node->prev;
	NODE *after = node->next;
	T result = node->data;
	node->next = node->prev = 0;

	before->next = after;
	after->prev = before;
	node_count--;

	return result;
}

void push_front(T data) {
	push_next(head->next, data);
}

void push_last(T data) {
	push_next(head, data);
}

T pop_front() {
	if (head == 0 || node_count == 0) {
		cout << "No data to pop front." << endl;
		return 0;
	}
	return remove_node(head->next);
}

T pop_last() {
	if (head == 0 || node_count == 0) {
		cout << "No data to pop front." << endl;
		return 0;
	}
	return remove_node(head->prev);
}

void disp() {
	if (node_count == 0) {
		cout << "no data to display" << endl;
		return;
	}
	NODE *cur = head->next;
	for (int i = 0; i < node_count; i++) {
		cout << cur->data << " ";
		cur = cur->next;
	}
	cout << endl;
}

int main() {
	init();

	push_front(1);
	push_front(2);
	push_front(3);
	push_last(100);

	disp();
	return 0;
}