queue_linklist

#include <iostream>
#include <stdlib.h>
using namespace std;
typedef int item;// kieu du lieu
struct Node
{
	item Data;
	Node *next;
};
struct Queue// tao hang cho
{
	Node *dau, *cuoi;// Node dau va node cuoi
	int count;// dem so phan tu
};
void taoQueue(Queue &q);
bool ktQueueRong(Queue q);
Node *CreateNode(item x);
void pushQueue(Queue &q, item x);
int popQueue(Queue &q);
void input(Queue &q);
void output(Queue q);

void taoQueue(Queue &q)// tao queue
{
	q.dau = q.cuoi = NULL;
	q.count = 0;
}
bool ktQueueRong(Queue q)
{
	if (q.count == 0)// so phan tu =0 -> rong
		return true;
	else
		return false;
}
Node *CreateNode(item x)
{
	Node *p = new Node;
	if (p == NULL)
	{
		return NULL;
	}
	else
	{
		p->Data = x;
		p->next = NULL;
	}
	return p;
}
void pushQueue(Queue &q, item x)// them phan tu vao cuoi queue
{
	Node *p = CreateNode(x);
	if (ktQueueRong(q))
	{
		q.dau = q.cuoi = p;// dau va cuoi deu tro den p
	}
	else// khong rong
	{
		q.cuoi->next = p;
		q.cuoi = p;
	}
	q.count++;
}
int popQueue(Queue &q)// loai bo phan tu dau khoi hang doi
{
	if (ktQueueRong(q))
	{
		cout << "hang doi rong";
		return 0;
	}
	else
	{
		item x = q.dau->Data;
		if (q.count == 1)// neu co 1 phan tu
			taoQueue(q);
		else
			q.dau = q.dau->next;
		q.count--;
		return x;// tra ve phan tu lay ra
	}
}
void input(Queue &q)
{
	int i = 0;
	item x;
	cout << "NHAP PHAN TU HANG CHO, NHAP 0 DE KET THUC";
	do
	{
		i++;
		cout << "\nnhap phan tu thu " << i << ": ";
		cin >> x;
		if (x != 0)
			pushQueue(q, x);
	} while (x != 0);// nhap khong de ket thuc
}
void output(Queue q)
{
	Node *p = q.dau;
	while (p != NULL)
	{
		cout << " " << p->Data;
		p = p->next;
	}
	cout << "\n";
}
int main()
{
	Queue q;
	taoQueue(q);
	input(q);
	output(q);
	int lua_chon;
	cout << "Moi Ban Chon Phep Toan Voi DS LKD";
	cout << "\n1: Kiem Tra Queue Rong";
	cout << "\n2: Them Phan Tu Vao Queue";
	cout << "\n3: Xoa Phan Tu Trong Queue";
	cout << "\n4: Xuat Queue";
	cout << "\n5: Thoat";
	do
	{
		cout << "\nBan Chon: ";
		cin >> lua_chon;
		switch (lua_chon)
		{
		case 1:
		{
			if (ktQueueRong(q))
				cout << "Queue rong";
			else
				cout << "Queue Khong Rong";
			break;
		}
		case 2:
		{
			item x;
			cout << "nhap phan tu can chen vao Queue: ";
			cin >> x;
			pushQueue(q, x);
			break;
		}
		case 3:
		{
			popQueue(q);
			break;
		}
		case 4:
		{
			output(q);
			break;
		}
		case 5:
		{
			break;
		}
		}
	} while (lua_chon != 5);
	return 0;
	system("pause");
}