Lab46 Wiki

The purpose of this programme is much like the stack demo programme, to gain familiarity with the basic nature of the queue by capturing input at the console and regurgitating it. This time, however, the output will be in the same order as the input because of the first in, first out nature of the queue.

A clip of it running:

doug@slackware:~/src/queue_demo$ ./queue_demo 
abcdef
abcdef

Combined with the source code beneath it, the command to compile it:

g++ -o queue_demo queue_demo.cpp -g

#ifndef _LTNODES
#define _LTNODES
#include <cstddef>

template <class T> struct SNode{
	public:
		T data;
		SNode* next;
		
		SNode(){
			next = NULL;
		}
		
		SNode(T d){
			data = d;
			next = NULL;
		}
};

template <class T> struct DNode{
	public:
		T data;
		DNode *next, *prev;
		
		DNode(){
			next = NULL;
			prev = NULL;
		}
		
		DNode(T d){
			data = d;
			next = NULL;
			prev = NULL;
		}
};

#endif

#ifndef _LTQUEUE
#define _LTQUEUE
#include <cstddef>
#include "ltnodes.hpp"

template <class T> class Queue{
	private:
		DNode<T>* head, *tail;
		unsigned long long size, capacity;
		// size is the current size of our queue, whereas capacity is the maximum
		// size of it. If capacity is zero, however, it is an unlimited queue.
		
	public:
		Queue(unsigned long long c = 0){
			head = NULL;
			tail = NULL;
			size = 0;
			capacity = c;
		}
		
		unsigned long long get_size(){
			return size;
		}
		
		unsigned long long get_capacity(){
			return capacity;
		}
		
		void set_capacity(unsigned long long c){
			capacity = c;
		}
		
		DNode<T>* dequeue(){
			DNode<T>* curr = head;
			if (head != NULL){
				head = head->prev;
				if (head != NULL){
					head->next = NULL;
				}
				curr->prev = curr->next = NULL;
				size--;
			}
			return curr;
		}
		
		DNode<T>* front(){
			return this->head;
		}
		
		DNode<T>* back(){
			return this->tail;
		}
		
		bool enqueue(DNode<T>* node){
			if (size < capacity || capacity == 0){
				node->next = this->tail;
				if (this->tail != NULL){
					this->tail->prev = node;
				}
				else {
					this->head = node;
				}
				node->prev = NULL;
				this->tail = node;
				size++;
				return true;
			}
			return false;
		}
};

#endif

#include <iostream>
#include <cstdio>
#include "../include/ltqueue.hpp"

int main(){
	Queue<char> queue;
	DNode<char>* curr = new DNode<char>;
	char tmp = 'a';
	
	while (tmp != '\n'){
		tmp = fgetc(stdin);
		curr->data = tmp;
		queue.enqueue(curr);
		if (tmp != '\n'){
			curr = new DNode<char>;
		}
	}
	
	if (queue.front() != NULL){
		curr = queue.dequeue();
		while (curr != NULL){
			std::cout << curr->data;
			delete curr;
			curr = queue.dequeue();
		}
	}
	std::cout << std::endl;
	
	return false;
}