欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

队列 FIFO

程序员文章站 2022-03-14 15:06:21
...
#include <iostream>
using namespace std;

typedef double T;

class List{
	struct Node{
		T data;
		Node* next;
		Node(const T& t=T()):data(t)
		{
			next = NULL;
		}
	};
	Node* head;
public:
	List():head(NULL)
	{
		
	}
	void clear()
	{
		while(head != NULL)
		{
			Node* q = head->next;
			delete head;
			head = q;
		}
	}
	~List()
	{
		clear();
	}
	void insert_front(const T& t)
	{
		Node* p = new Node(t);
		p->next= head;
		head = p;
	}
	
	void insert_back(const T& t)
	{
		Node* p = new Node(t);
		if (head==NULL)
			head = p;
		else
		{
			get_pointer(size()-1)->next = p;
		}
	}
	
	void travel()
	{
		Node* p=head;
		while(p != NULL)
		{
			cout << p->data << ' ';
			p = p->next; 
		}
		cout << endl;
	}
	int size()
	{
		int cnt = 0;
		Node* p = head;
		while(p != NULL)
		{
			cnt++;
			p = p->next;
		}
		return cnt;
	}
	
	T get_head()
	{
		if (head == NULL)
		{
			throw "no head";
		}	
		return head->data;
	}
	T get_tail()
	{
		if (head == NULL)
			throw "no tail";
		Node* p = head;
		while(p->next != NULL)
		{
			p = p->next;
		}
		return p->data;
	}
	
	bool empty()
	{
		return head == NULL;
	}
	
	int find(const T& t)
	{
		int pos = 0;
		Node* p = head;
		while(p != NULL)
		{
			if (p->data== t)
				return pos;
			p = p->next;
			pos++;
		}
		return -1;
	}
	bool update(const T& o, const T& n)
	{
		int pos = find(o);
		if (pos == -1)
			return false;
		Node* p = get_pointer(pos);
		p->data = n;
		
		return true;
	}
private:
	Node* get_pointer(int pos)
	{
		Node* p = head;
		for (int i=0; i<pos; i++)
			p = p->next;
		
		return p;
	}
public:
	bool erase(const T& t)
	{
		int pos = find(t);
		if (pos == -1)
			return false;
		if (pos ==0)
		{
			Node* q = head->next;
			delete head;
			head = q;
		}
		else
		{
			Node* pre = get_pointer(pos-1);
			Node *cur = pre->next;
			pre->next= cur->next;
			delete cur;
		}
	}	
};

class Queue{
	List l;
public:
	void push(const T& t)  //数据入队列 
	{
		l.insert_back(t);	
	}
	void pop()  //删除队首元素 
	{
		l.erase(l.get_head());
	}
	T front()  //取得队列首元素
	{
		return l.get_head();	
	} 
	T back()	//取得队列尾元素
	{
		return l.get_tail();	
	} 
	bool empty()  //判断队列是否为空 
	{
		return l.empty();
	} 
	int size()	//取得队列中的元素个数
	{
		return l.size();	
	} 
	void clear()	//清空整个队列
	{
		l.clear();
	} 
};

int main()
{
	Queue q;
	q.push(1.0);
	q.push(2.0);
	q.push(3.0);
	q.push(4.0);
	q.push(5.5);
	cout.setf(ios::showpoint);  //格式化输出,带小数部分 
	while(!q.empty())
	{
		cout << q.front() << ' ';
		q.pop();
	}
	cout << endl;
	return 0;
}

相关标签: 队列 FIFO