循环链队列

时间 2019-11-19 标签循环链队列

描述

假设以带头节点的循环链表表示队列，而且只设一个指针指向队尾元素节点（不设头指针），节点元素这里设为整型，编写队列的初始化、入队和出队算法。其中入队元素个数n及其节点数据，和出队元素个数m都是从键盘输入（默认n、m都不小于0）,而后输出出队元素，出队不合法(本身想一想什么状况下不合法）则输出Error。

要求：能进行屡次的入队、出队操做。无元素入队时，n=0；无元素出队时m=0。m=0 n=0时，算法结束。c++

提示：元素出队时的相应各类状况的处理。算法

输入

6 （n的值) 3 （m的值)
-2 0 1 7 10 -1
2 3
4 3

输出

-2 0 1 （出队元素）
7 10 -1

样例输入

6 4
0 3 1 21 9 -1
2 3
5 6
0 0

样例输出

0 3 1 21 
9 -1 5

提示

当队列中有n个元素，但要求出队m个，而且，m>n时，直接Error，不输出队中元素，可是，该入队的还要入队。（不能由于m>n 就不进行入队操做）

PS：这个题的一个bug改了一下午，看错了题意觉得不设头指针误理解为不设头结点。结果可想而知，很长时间才找到bug。作题之后要仔细读题和注意思惟的严密性。

#include<bits/stdc++.h>
using namespace std;
template<class T>
struct Node
{
    T data;
    Node<T> *next;
};
template<class T>
class LinkQueue
{
private:
    int length;
    Node<T> *front,*rear;

public:
    LinkQueue();
    ~LinkQueue();
    void Insert_Queue(T x);
    T Delete_Queue();
    int Get_Length(){return length;}

};
/*      构造队列     */
template<class T>
LinkQueue<T>::LinkQueue()
{
    front=new Node<T>;
    front->next=NULL;
    rear=front;
    length=0;
}
/*      析构       */
template<class T>
LinkQueue<T>::~LinkQueue()
{
     Node<T> *p;
    while(front)
    {
        p=front->next;
        front=front->next;
        delete p;
    }
}
/*        入队       */
template<class T>
void LinkQueue<T>::Insert_Queue(T x)
{
    Node<T>*s;
    s=new Node<T>;
    s->data=x;
    s->next=NULL;
    rear->next=s;
    rear=s;
    length++;
}
/*      出队       */
template<class T>
T LinkQueue<T>::Delete_Queue()
{
    if(rear==front) throw "Error";
    Node<T> *p;
    p=front->next;
    T x=p->data;
    front->next=p->next;
    delete p;
    if(front->next==NULL) rear=front;///删除只有一个元素的时候
    length--;
    return x;
}
int main()
{
    int n,m,x;
    LinkQueue<int> My_queue;
    while(scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0) break;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            My_queue.Insert_Queue(x);
        }
        if(m>My_queue.Get_Length())
        {
            printf("Error\n");
        }
        else
        {
            for(int i=1;i<=m;i++)
            {
                if(i==m)
                {
                    printf("%d\n",My_queue.Delete_Queue());
                }
                else
                {
                     printf("%d ",My_queue.Delete_Queue());
                }
            }
        }


    }
    My_queue.~LinkQueue();
    return 0;
}