4. 队列
#include <stdafx.h>
#include <iostream>
using namespace std;
//通过链表来实现队列
struct Node
{
int data;
Node *next;
Node(int _data=0, Node *_next=NULL):data(_data), next(_next){}
};
struct LQueue//代表linked queue
{
Node *front;
Node *rear;
LQueue(Node *_front=NULL, Node *_rear=NULL):front(_front), rear(_rear){}
void insertNode(const int item);//在队尾插入
void deleteNode();//在队首删除
};
void LQueue::insertNode(const int item)
{
Node *newNode = new Node(item);
//队列只允许在队末插入新结点
if(NULL == rear)//特殊情况：空队列
{
front = newNode;
rear = newNode;
}
else
{
rear->next = newNode;
rear = newNode;
}
}
void LQueue::deleteNode()
{
if(NULL == front)//特殊情况：空队列
return;
Node *p = front;
front = p->next;
delete p;
}
int main()
{
//一个队列本身只存放两个数据，即队首front和队尾rear，至于队列的具体实现过程则交给链表去执行，
//因此，构造队列只比构造单链表多了一步定义front和rear的过程。
LQueue *lq = new LQueue;
Node *newNode, *p;//p为遍历队列的指针（如果不是插入、删除结点等需要前后指针作辅助的情况下不要用currPtr来遍历）
newNode = new Node;
lq->front = newNode; //保存队首地址
p = newNode;
for(int i=1; i<10; ++i)
{
newNode = new Node(i);
p->next = newNode;
p = newNode;
}
lq->rear = p; //保存队尾地址
for(p=lq->front; p!=NULL; p=p->next)
{
cout << p->data << " ";
}
cout << endl;
lq->insertNode(11);//在队尾插入
lq->deleteNode();//将队首删除
for(p=lq->front; p!=NULL; p=p->next)
{
cout << p->data << " ";
}
cout << endl;
}