数据结构--队列

队列是一种先进先出的数据结构（FIFO），队列的主要特点是在队尾进行入队，在队首进行出队。队列的实现方式主要有数组实现和链表实现。

数组实现：首先定义一个数组，front和rear用来表示队首和队尾，对于入队操作，即将元素插入数组的第rear个位置，然后将rear加1，继续指向队尾。

对于出队操作，即将队首的元素去除，但是还需要将数组其他的元素向前移从而得到新的队首元素，同时，rear也需要减1。

#include <iostream>
using namespace std;
int front=0,rear =0;
int queue[10];
//队首出队（front），队尾入队(rear)
void enque(int x)
{
    if(rear==10)
    {
        cout<<"overflow"<<endl;
    }
    else
    {
        queue[rear++]=x;
    }

}

void deque()
{
    if(front==rear)
    {
        cout<<"no elements"<<endl;
    }
    else
    {
        cout<<"deleted:"<<queue[front++]<<endl;
        for(int i=front;i<rear;i++)
        {
            queue[i-front]=queue[i];
        }
        rear=rear-front;
        front=0;
    }

}
void show()
{

        for(int i=front;i<rear;i++)
        {
            cout<<queue[i]<<"\t";
        }

}

int main()
{
    int c, x;
    do
    {
        cout << "\n1. Enque";
        cout << "\n2. Deque";
        cout << "\n3. Print";
        cout << "\nEnter Your Choice : ";
        cin >> c;
        if (c == 1)
        {
            cout << "\nInsert : ";
            cin >> x;
            enque(x);
        }
        else if (c == 2)
        {
            deque();
        }
        else if (c == 3)
        {
            show();
        }
    } while (c != 0);

    return 0;
}

链表实现：首先定义两个节点队首节点和队尾节点，对于入队操作，首先判断队尾节点是不是为空指针，如果是，则将队首和队尾节点都等于插入的元素节点，如果不是，则将入队的元素首先插入到rear->next，再令插入的元素节点指向队尾。

对于出队操作，首先判断队列是否为空，如果不为空，将队首节点指向其下一个节点，删除原先队首节点。

#include <iostream>
using namespace std;
struct node
{
    int data;
    node *next;
};

node *front,*rear; //队首和队尾  //队首出队（front），队尾入队(rear)

void enque(int x)
{

    if(rear==NULL)
    {
        node *n=new node;
        n->data=x;
        n->next=NULL;
        rear=n;
        front=n;
    }
    else
    {
        node *n=new node;
        n->data=x;
        n->next=NULL;
        rear->next=n;
        rear=n;
    }
}

void deque()
{
    if(rear==NULL&&front==NULL)
    {
        cout<<"no elements"<<endl;
    }
    else
    {
        node *t=front;
        cout<<"delete:"<<t->data<<endl;
        front=front->next;
        delete t;
        if(front==NULL)  //如果只有一个元素，出队后都指向null
        {
            rear=NULL;
        }
    }

}

void show()
{
    node *n=front;
    while (n!=NULL)
    {
        cout<<n->data<<"\t";
        n=n->next;
    }

}



int main()
{
    int ch ,x;
    do
    {
        cout << "\n1. Enque";
        cout << "\n2. Deque";
        cout << "\n3. Print";
        cout<<"\n choice:"<<endl;
        cin>>ch;
        if(ch==1)
        {
            cout<<"\nInsert:";
            cin>>x;
            enque(x);
        }
        else if(ch==2)
        {
            deque();
        }
        else if(ch==3)
        {
            show();
        }
    }while(ch!=0);
    return 0;
}