solutions/The Last Algorithms Course You'll Need/8. Queue.c

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

typedef int BOOL;
#define TRUE 1
#define FALSE 0

typedef struct node 
{
	int value;
	struct node *next;
} Node;

typedef struct
{
	int value;
	BOOL flag;
} ListValue;

static Node* HEAD;
static Node* TAIL;

static int LENGTH = 0;

// O(1) operation, no growth by input
BOOL enqueue(int value)
{
	Node* new_head = malloc(sizeof(Node));
	if (new_head == NULL)
		return FALSE;

	new_head->value = value;

	if (HEAD != NULL)
		HEAD->next = new_head;
	else
		TAIL = new_head;

	HEAD = new_head;
	++LENGTH;

	return TRUE;
}

// O(1) operation, no growth by input
ListValue deque()
{
	ListValue value = { 0, FALSE };
	Node* iterator = TAIL; 
	if (iterator == NULL)
		return value;

	if (HEAD != TAIL)
	{
		TAIL = iterator->next;
	}
	else
	{
		HEAD = NULL;
		TAIL = NULL;
	}

	value.value = iterator->value;
	value.flag = TRUE;

	free(iterator);
	iterator = NULL;

	--LENGTH;
	return value;
}

// O(1) operation, no growth by input
ListValue peek()
{
	ListValue value = { 0, FALSE };
	Node* iterator = TAIL; 
	if (iterator == NULL)
		return value;

	value.value = iterator->value;
	value.flag = TRUE;

	return value;
}

int main()
{
	enqueue(5);
	enqueue(22);
	enqueue(66);
	enqueue(122);
	enqueue(9);

	printf("peek: %d\n", peek().value);

	deque();

	printf("peek: %d\n", peek().value);

	deque();

	printf("peek: %d\n", peek().value);
}