队列是包含元素集合的抽象数据结构。队列执行FIFO机制,即,首先插入的元素也将首先删除。
队列拐杖是一种线性数据结构。但是如果我们使用数组实现队列,可能会产生一些问题。有时通过使用一些连续的插入和删除操作,前后位置将发生变化。在那一刻,队列看起来没有空间向其中插入元素。即使有一些可用空间,由于某些逻辑问题也不会使用。为了克服这个问题,我们将使用循环队列数据结构。
循环队列是一种队列,其中最后一个位置与第一个位置相连以形成一个圆圈。
#include <iostream> using namespace std; int cqueue[5]; int front = -1, rear = -1, n=5; void insertCQ(int val) { if ((front == 0 && rear == n-1) || (front == rear+1)) { cout<<"Queue Overflow \n"; return; } if (front == -1) { front = 0; rear = 0; } else { if (rear == n - 1) rear = 0; else rear = rear + 1; } cqueue[rear] = val ; } void deleteCQ() { if (front == -1) { cout<<"Queue Underflow\n"; return ; } cout<<"Element deleted from queue is : "<<cqueue[front<<endl; if (front == rear) { front = -1; rear = -1; } else { if (front == n - 1) front = 0; else front = front + 1; } } void displayCQ() { int f = front, r = rear; if (front == -1) { cout<<"Queue is empty"<<endl; return; } cout<<"Queue elements are :\n"; if (f <= r) { while (f <= r){ cout<<cqueue[f]<<" "; f++; } } else { while (f <= n - 1) { cout<<cqueue[f]<<" "; f++; } f = 0; while (f <= r) { cout<<cqueue[f]<<" "; f++; } } cout<<endl; } int main() { int ch, val; cout<<"1)Insert\n"; cout<<"2)Delete\n"; cout<<"3)Display\n"; cout<<"4)Exit\n"; do { cout<<"Enter choice : "<<endl; cin>>ch; switch(ch) { case 1: cout<<"Input for insertion: "<<endl; cin>>val; insertCQ(val); break; case 2: deleteCQ(); break; case 3: displayCQ(); break; case 4: cout<<"Exit\n"; break; default: cout<<"Incorrect!\n"; } } while(ch != 4); return 0; }
输出结果
1)Insert 2)Delete 3)Display 4)Exit Enter choice : 1 Input for insertion: 10 Enter choice : 1 Input for insertion: 20 Enter choice : 1 Input for insertion: 30 Enter choice : 1 Input for insertion: 40 Enter choice : 1 Input for insertion: 50 Enter choice : 3 Queue elements are : 10 20 30 40 50 Enter choice : 2 Element deleted from queue is : 10 Enter choice : 2 Element deleted from queue is : 20 Enter choice : 3 Queue elements are : 30 40 50 Enter choice : 4 Exit