赞
踩
队列:只允许在一端进行插入操作,在另一端进行删除操作。允许插入(入队、进队)的一段端称为队尾,允许删除(出队)的一端称为队首(队头)。
队列具有
先进先出的特点。
题目:设计以不带头结点的循环链表表示队列,并且只设置一个指针指向队尾结点,但不设头指针。设计相应的入队和出队操作的算法。
C++的实现:
- #include<iostream>
- using namespace std;
- struct note
- {
- int data;
- note *next;
- };
- class LinkQueue
- {
- public:
- LinkQueue(int a[],int n);//初始化链队列
- ~LinkQueue() {};
- void EnQueue(int x);//将x入队
- int DeQueue();//出队操作
- void print();//遍历链队列
- private:
- note *rear;
- };
- LinkQueue::LinkQueue(int a[],int n)
- {
- note *first;
- first = new note;//生成头结点
- rear = first;//尾指针初始化
- for (int i = 0; i < n; i++)
- {
- note *s;
- s = new note; s->data = a[i];//为每个数组元素建立一个结点
- rear->next = s; rear = s;//将结点s插入到终端结点之后
- }//与尾插法建立单链表类似
- rear->next = first->next;//数据初始化结束后,尾指针指向存有数据的第一个结点,删除first指针指向的数据域为空的头结点
- delete first;//尾插法建立循环链表
- }
- void LinkQueue::EnQueue(int x)
- {
- note *s;
- s = new note; s->data = x;//生成新结点
- s->next = rear->next;
- rear->next = s;//入队操作,将新建的结点插入队尾,和在单链表中任意位置插入结点一样
- rear = s;//尾指针后移
- }
- int LinkQueue::DeQueue()
- {
- note *p;
- int x;
- p = rear->next;//工作指针指向队首
- x = p->data;
- rear->next = p->next;
- delete p;//队首元素出队,和单链表中删除任意结点一样
- return x;//返回出队的队首元素
- }
- void LinkQueue::print()
- {
- note *q,*p;
- q=p=rear->next;
- do
- {
- cout << q->data<<'\t';//输出当前数据
- q = q->next;//指针后移
- } while (p != q);//p,q指针指向同一结点时遍历结束
- cout << endl;
- }
-
- int main()
- {
- int a[] = { 1,2,3,4,5 };
- int x = 6;
- LinkQueue test(a, 5);
- cout << "输出链队列:" << endl;
- test.print();
- cout <<"将 x="<<x<<" 入队并取出队首元素 a="<<test.DeQueue()<<endl;
- test.EnQueue(x);
- cout << "输出链队列:" << endl;
- test.print();
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。