本文目录一览
- 1、数据结构队列操作
- 2、关于队列和时间复杂度的问题
- 3、c语言题目。我已经排完顺序要怎么出队
- 4、数据结构C语言描述的链队列的基本操作（初始化，判空，入队，出队，取对头，输出队列所有值....）
- 5、数据结构c语言版，出队入队及依次输出一个队列的操作。
- 6、数据结构 第7讲 循环队列
- 7、1.编写顺序存储队列基本操作函数：①队列初始化②入队操作③出队操作④输出队头元素⑤判断队列是否为空
- 8、采用链式存储实现队列的初始化、入队、出队操作
数据结构队列操作
Q.base是干什么的哦。。这样够了吧应该入队嘛就是先看队满了没有（应该是定义里面那个tag跟MAXQSIZE来比较吧），满了的话返回失败，没满继续。。还是写代码吧我……
Status EnCQueue(CTagQueue Q, QElemType x) {
if (Q.tag==MAXQSIZE) return 0;
Q.tag++;
Q.rear++;
if (rearMAXQSIZE) Q.rear=0;/*到数组最后一个了，从最开始继续*/
Q.elem[rear]=x;
return 1;
}
Status DeCQueue(CTagQueue Q, QElemType x){
if (Q.tag==0) return 0;/*队列空，失败*/
Q.tag--;
x=Q.elem[front];
front++;
if (frontMAXQSIZE) front=0;
retrun 1;
}
补充阿：
还是不知道你说的Q.Base是啥，没有它为啥不能做
貌似入队的时候只要检查tag不是满，假如满的话失败，空的话可以入队，同时改变rear的值，再检查入队以后front与rear是不是相同了，如果相同，那说明这是最后一个空间，队列已经满了，那么就要翻转tag的值，表示已经满了。
出队也是一样，如果队列为满，那么出队以后同样要翻转tag的值，表示队列有空间。
至于比较，实在想不出来，仅仅有个rear和front有办法搞入队出队操作么？。。
关于队列和时间复杂度的问题
a) 如果只有头指针，且含头结点1. 出队: O(1)，因为只要把头结点的下一个结点删除就好了
2. 入队: O(n)，要把新的结点插入到队尾，必须把队列历遍，找到队尾，才能插入
b) 如果只有头指针，不含头结点
1. 出队: O(n)，要把头结点删除，必须历遍队列，找到队尾，才能更新头指针 (循环单链的缘故，如果仅仅是普通单链，则本操作也是O(1) )
2. 入队: O(n)，同 (a).2
c) 如果只有尾指针
1. 出队: O(1)，只要把尾指针的下一个结点(没有头结点的情况)或者下下个结点(有头结点的情况)删除即可
2. 入队: O(1)，只要在尾指针的后面插入新的结点，并更新尾结点，所以是O(1)
c语言题目。我已经排完顺序要怎么出队
你要是想让我们告诉你怎么出队，你需要把你的存储结构清楚地告诉我们吧。比如你是存在一个数组，还是类，对应类的结构，还是结构体？还是什么。每个结构的具体方法都不一样。
我能想到的大概思路：第一行到(1+N)行表示你所存的数据。然后第N+2行的值是M，第(N+3)至(N+M+1)行表示每次出队第几个人出。出队方法就是设计一个函数遍历第(N+3)至(N+M+1)行，使你的有序队列达到出队的效果。
而这个队列是存储在了数组里还是链表里还是什么结构？。
大概思路基本就是
让第几个人出队
找到他、他前面的人和他后面的人
让他前面的人的后面 ?变成他后面的人
数据结构C语言描述的链队列的基本操作（初始化，判空，入队，出队，取对头，输出队列所有值....）
void InitQueue(LiQueue *q){q=(LiQueue *)malloc(sizeof(LiQueue));
q-front=q-rear-NULL;} //初始化
int QueueEmpty(LiQueue *q)
{if(q-rear==NULL)
return 1;
else
return 0;} //判空
void enQueue( LiQueue *q,ElemType e)
{QNode *s;
s=(QNode *)malloc(sizeof(QNode));
s-data=e;
s-next=NULL;
if(q-rear==NULL)
q-front=q-rear=s;
else
{q-rear-next=s;
q-rear=s;
}} //入队
int deQueue( LiQueue *q,ElemType e)
{QNode *t;
if(q-rear==NULL)
return 0;
t=q-front;
if(q-front==q-rear)
q-front=q-rear=NULL;
else
q-front=q-front-next;
e=t-data;
free(t);
return 1;} //出队
int deQueue( LiQueue *q,ElemType e)
{QNode *t;
if(q-rear==NULL)
return 0;
t=q-front;
if(q-front==q-rear)
q-front=q-rear=NULL;
else
q-front=q-front-next;
e=t-data;break;
free(t);
return 1;} //取队头
输出队列所有数就是出队
数据结构c语言版，出队入队及依次输出一个队列的操作。
黑色的提示框是程序运行结果窗口，不是错误的窗口
代码错误说明如下：
while(Q-front!=Q-rear)//在本循环体之中，Q-front?Q-rear的值始终没有变化//故而在这里肯定是一个死循环
{
????printf("%d,??",?Q-front-next-data);
????Q-front-next=Q-front-next-next;
}
//改正后的代码如下：
QNode*?s?=?Q-front;
while(s!=Q-rear)
{
????printf("%d,??",?s-data);
????s=s-next;
}
另外，所有的函数当中不应该有exit
exit是一个系统函数，表示结束程序，而不是退出函数
如果需要退出函数可以使用return来达到该目的
数据结构 第7讲 循环队列
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?数据结构 第7讲 循环队列过了一段时间，小张再也受不了这种"起早贪黑"的有车生活。为了解决胡同停车问题，小张跑了无数次居委会，终于将挡在胡同口的建筑清除，这样住在胡同尽头的小张，就可以早早回家停在家门口，每天第一个开车上班去了。
现在胡同打通了，但仍然很窄，只能通过一辆车，但是可以从一端进，另一端出，画图：
小汽车是线性排列，而且只能从一端进，另一端出，这就是"队列"，队列也是一种线性表，只不过它是操作受限的线性表，只能在两端操作，先进先出（First In First Out，FIFO）。
进的一端称为队尾（rear），出的一端称为队头（front）。队列可以用顺序存储，也可以用链式存储。
1. 顺序队列
队列的顺序存储形式，可以用一个一维数组存储数据元素，用两个整型变量记录队头和队尾元素的下标。
顺序存储方式：
顺序队列的结构体定义：
2. 完美图解
接下来看看顺序队列的入队和出队情况：
假设现在顺序队列Q分配了6个空间，然后进行入队出队操作，过程如图所示：
(1)开始时为空队，Q.front=Q.rear，如图所示：
(2)元素 a 1进队，放入尾指针Q.rear（整型下标）的位置，Q.rear后移一位，如图所示：
(3)元素 a 2进队，放入尾指针Q.rear（整型下标）的位置，Q.rear后移一位，如图所示：
(4)元素 a 3， a 4， a 5分别按顺序进队，尾指针Q.rear依次后移，如图所示：
(5)元素 a 1出队，头指针Q.front（整型下标）后移一位，如图所示：
(6)?元素 a 2出队，头指针Q.front（整型下标）后移一位，如图所示：
(7)元素 a 6进队，放入尾指针rear（整型下标）的位置，rear后移一位，如图所示：
(8)?元素 a 7进队，此时尾指针Q.rear已经超过了数组的下标，无法再存储进队，但是我们发现前面明明有2个空间，却出现了队满的情况，这种情况称为"假溢出"。
那么如何解决该问题呢？
能否利用前面的空间继续存储入队呢？
试试看…～
上面第（7）步元素 a 6进队之后，尾指针Q.rear要后移一个位置，此时已经超过了数组的下标，即Q.rear+1=Maxsize（最大空间数6），那么如果前面有空闲，Q.rear可以转向前面0的位置，如图所示：
然后元素 a 7进队，放入尾指针Q.rear（整型下标）的位置，Q.rear后移一位，如图所示：
元素 a 8进队，放入尾指针Q.rear（整型下标）的位置，Q.rear后移一位，如图所示：
这时候虽然队列空间存满了，但是出现了一个大问题，队满时Q.front=Q.rear，这和队空的条件一模一样，无法区分队空还是队满，如何解决呢？有两种办法：一是设置一个标志，标记队空和队满；另一种办法是浪费一个空间，当尾指针Q.rear的下一个位置Q.front是时，就认为是队满。如图所示：
3. 循环队列
上述到达尾部又向前存储的队列称为循环队列，为了避免"假溢出"，我们通常采用 循环队列。
循环队列无论入队还是出队，队尾、队头加1后都要取模运算，例如入队后队尾后移一位：Q.rear =(Q.rear+1)%Maxsize。
为什么要%Maxsize呢？
主要是为了处理临界状态，即Q.rear向后移动一个位置Q.rear+1后，很有可能超出了数组的下标，这时它的下一个位置其实是0，如果将一维数组画成环形图，如图所示：
上图中最大空间Maxsize，当Q.rear=Maxsize-1时，(Q.rear+1)%Maxsize=0，而且Q.front=0，正好满足队满的条件：(Q.rear+1) %Maxsize= Q.front，此时为队满。
因此无论是front还是rear向后移动一个位置时，都要加1与最大空间Maxsize取模运算，处理临界问题。
总结：
队空 ：Q.front=Q.rear; // Q.rear和Q.front指向同一个位置
队满 ： (Q.rear+1) %Maxsize=Q.front; // Q.rear向后移一位正好是Q.front
入队 ：
Q.base[Q.rear]=x; //将元素放入Q.rear所指空间，
Q.rear =( Q.rear+1) %Maxsize; // Q.rear向后移一位
出队 ：
e= Q.base[Q.front]; //用变量记录Q.front所指元素，
Q.front=(Q.front+1) %Maxsize // Q. front向后移一位
循环队列中到底存了多少个元素呢？
因为队列是循环的，所以存在两种情况：
（1）Q.rear= Q.front，如下图所示：
这种情况队列中元素个数为：Q.rear-Q.front=4-1=3。
（2）Q.rear Q.front，如下图所示：
此时，Q.rear=4，Q.front=Maxsize-2，Q.rear-Q.front=6-Maxsize。但是我们可以看到循环队列中的元素实际上为6个，那怎么办呢？当两者之差为负数时，可以将差值+Maxsize计算元素个数，即：Q.rear-Q.front+Maxsize=6-Maxsize+Maxsize =6，元素个数为6。
那么在计算元素个数时，可以分两种情况判断：
Q.rear= Q.front：元素个数为Q.rear-Q.front；
Q.rearQ.front：元素个数为Q.rear-Q.front+ Maxsize；
也可以采用取模的方法把两种情况统一为一个语句：
队列中元素个数 ：(Q.rear-Q.front+Maxsize)% Maxsize
当Q.rear-Q.front为负数时，加上Maxsize再取余正好是元素个数，如(-2+6)%6=4；当Q.rear-Q.front为正数时，加上Maxsize超过了最大空间数，取余后正好是元素个数，如(3+6)%6=3。
4. 队列的基本操作
队列的基本操作包括初始化、入队、出队、取队头元素、求队列长度。
(1)初始化
bool?InitQueue(SqQueue?Q)//注意使用引用参数，否则出了函数，其改变无效??
{??
? ? ? ? Q.base=new?int[Maxsize];//分配空间??
? ? ? ?if(!Q.base)?return?false;??
? ? ? ? Q.front=Q.rear=0;//头指针和尾指针置为零，队列为空??
? ? ? ? ?return?true;??
}??
(2)入队
bool?EnQueue(SqQueue?Q,int?e)//将元素e放入Q的队尾 ?
{ ?
? ? ? ? ?if((Q.rear+1)%Maxsize==Q.front)?//尾指针后移一位等于头指针，表明队满 ?
? ? ? ? ? ? ? ? ?return?false; ?
? ? ? ?Q.base?[Q.rear]=e;//新元素插入队尾 ?
? ? ? ?Q.rear=(Q.rear+1)%Maxsize;//队尾指针后移一位 ?
? ? ? return?true; ?
}??
(3)出队
bool?DeQueue(SqQueue?Q,?int?e)?//删除Q的队头元素，用e返回其值 ?
{ ?
? ? if?(Q.front==Q.rear) ?
? ? ? ? ? return?false;?//队空 ?
? ? e=Q.base[Q.front];//保存队头元素 ?
? ? Q.front=(Q.front+1)%Maxsize;//队头指针后移一位 ?
? ?return?true; ?
}??
(4)取队头元素
int?GetHead(SqQueue?Q)//返回Q的队头元素，不修改队头指针 ?
{ ?
? ? ? ? ? ?if?(Q.front!=Q.rear)?//队列非空 ?
? ? ? ? ? ? ? ? ?return?Q.base[Q.front];??
? ? ? ? ? ? return?-1; ?
}??
(5)循环队列的长度
int?QueueLength(SqQueue?Q) ?
{ ?
? ? ? return?(Q.rear-Q.front+Maxsize)%Maxsize; ?
} ?
1.编写顺序存储队列基本操作函数：①队列初始化②入队操作③出队操作④输出队头元素⑤判断队列是否为空
(VC6下编译通过)#include stdio.h
main()
{
int a[1000],top,tail;
int i,n=1;
do
{
switch (n)
{
case 1:top=tail=0;break;
case 2:printf("输入要插入的元素：");scanf("%d",a[++top]);break;
case 3:if (tailtop) tail++;break;
case 4:printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n队头为： %d\n",a[top]);break;
case 5:printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");if (tail==top) printf("空队列\n"); else printf("非空队列.\n");
}
if (n!=5n!=4)
printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");
printf("队列现在状态：");
for (i=tail+1;i=top;i++)
printf(" %d",a[i]);
if (tail==top)
printf("空队列");
printf("\n");
printf("\n1队列初始化\n2入队操作\n3出队操作\n4输出队头元素\n5判断队列是否为空\n0退出\n请输入代码：");
scanf("%d",n);
} while (n!=0);
}
采用链式存储实现队列的初始化、入队、出队操作
#includestdio.h#includestdlib.h
#define OVERFLOW -2
typedef struct QNode{//创建队成员
int data;//数据成员
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{//队头队尾指针
QueuePtr front;
QueuePtr rear;
}LinkQueue;
void InitQueue(LinkQueue Q)//初始化队列
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));//开辟空间
if(!Q.front) exit ( OVERFLOW);//开辟失败则退出
Q.front -next = NULL;
//return 1;
}
int EnQueue(LinkQueue Q)//入队操作
{
int e;
QueuePtr p;
printf("请输入入队元素:");
scanf("%d",e);
p=(QueuePtr)malloc(sizeof(QNode));
if (p==NULL) exit (OVERFLOW);
p-data = e; p-next = NULL;
Q.rear-next=p;//把p插入队尾
Q.rear=p;//把p变为队尾
return 1;
}
int DeQueue(LinkQueue Q)//出队操作
{
QueuePtr p;
int e;
if ( Q.front == Q.rear){
printf("队列为空\n");
return -1;
}
p=Q.front-next;//头指针为空
e=p-data;
printf("%d 出对\n",e);
Q.front-next =p-next;//指针后移
if (Q.rear == p) Q.rear = Q.front;//如果p为队尾
free(p);//释放p
return 1;
}
void tip()
{
printf("*************\n");
printf("*输入1 进队 *\n");
printf("*输入2 出对 *\n");
printf("*请选择: *\n");
printf("*************\n");
}
int main()
{
int k;
LinkQueue Q;
InitQueue(Q);//初始化队列
tip();
while(scanf("%d",k),k)
{
switch(k)
{
case 1:
EnQueue(Q);
tip();
printf("操作完毕\n");
break;
case 2:
DeQueue(Q);
tip();
printf("操作完毕\n");
break;
}
}
return 0;
}