queue.cc

资深C++讲师授课代码

#include <iostream>
using namespace std;

typedef int T;
class List{
	struct Node{
		T data;
		Node* next;
		Node(const T& d):data(d),next(NULL){++cnt;}
		~Node(){--cnt;}
		static int cnt;
	};
	Node* head;
	Node*& getp(int pos){
		if(pos<0||pos>size()) pos=0;
		if(pos==0) return head;
		Node* p=head;
		for(int i=1; i<pos; i++)
			p = p->next;
		return p->next;
	}
public:
	List():head(NULL){}
	void clear(){
		while(head!=NULL){
			Node* q = head->next;
			delete head;
			head = q;
		}
	}
	~List(){clear();}
	void travel(){
		Node* p=head;
		while(p!=NULL){
			cout << p->data << ' ';
			p = p->next;
		}
		cout << endl;
	}
	void insert(const T& d, int pos){
		Node* p = new Node(d);
		Node*& q = getp(pos);
		p->next = q;
		q = p;
	}
	bool erase(const T& d){
		int pos=find(d);
		if(pos==-1) return false;
		Node*& pn=getp(pos);
		Node* q = pn;
		pn = pn->next;
		delete q;
	}
	int find(const T& d, int start=0){//返回指数据为d的节点的指针的编号
		int pos=0;
		Node* p=getp(start);//head;
		while(p!=NULL){
			if(p->data==d)
				return pos;
			else{
				p = p->next;
				++pos;
			}
		}
		return -1;//return size();
	}
	bool update(const T& olddata, const T& newdata){
		int pos = find(olddata);
		if(pos==-1) return false;
		getp(pos)->data = newdata;
		return true;
	}
	int size(){
		return Node::cnt;
	}
	T front(){
		if(head==NULL) throw "no head node!";
		return head->data;
	}
	T back(){
		if(head==NULL) throw "no tail node!";
		return getp(size()-1)->data;
	}
	bool empty(){return head==NULL;/*size()==0;*/}
};
int List::Node::cnt = 0;
class Queue{
	List l;
public:
	void push(const T& d){l.insert(d, l.size());}
	void pop(){l.erase(l.front());}
	T front(){return l.front();}
	T back(){return l.back();}
	int size(){return l.size();}
	bool empty(){return l.empty();}
	void clear(){l.clear();}
};
int main()
{
	Queue s;
	s.push(10); s.push(20);
	s.push(30); s.push(40);
	s.push(50);
	while(!s.empty()){
		cout << s.front() << endl;
		s.pop();
	}
}