队列的各算法的实现

Ⅰ 使用栈和队列解决算法设计问题，对于怎样的应用问题，需要使用栈和队列，以及怎样使用。递归算法设计。

队列在输入、输出管理中的应用
在计算机进行数据输入、输出处理时，由于外部设备的速度远远低于CPU数据处理的速度，此时可以设定一个“队列缓冲区”进行缓冲。当计算机要输出数据时，将计算机的数据按块（例如每块512B）逐个添加到“队列缓冲区”的尾端，而外部设备则按照其输出速度从队首逐个取出数据块输出。这样，虽然输出数据速度较慢，但却能保证与计算机输出的数据有完全相同的次序，而不致发生输出次序的混乱或数据的丢失。
对CPU的分配管理
一般的计算机系统只有一个CPU，如果在系统中有多个进程都满足运行条件，这就可以用一个就绪队列来进行管理。当某个进程需要运行时，它的进程名就被插入到就绪队列的尾端。如果此队列是空的，CPU就立即执行该进程；如果此队列非空，则该进程就需要排在队列的尾端进行等待。CPU总是首先执行排在队首的进程，一个进程分配的一段时间执行完了，又将它插入到队尾等待，CPU转而为下一个出现在队首的进程服务。如此，按“先进先出”的原则一直进行下去，直到执行完的进程从队列中逐个删除掉。

栈的应用
数制转换
数值进位制的换算是计算机实现计算和处理的基本问题。比如将十进制数N转换为j进制的数，其解决的方法很多，其中一个常用的算法是除j取余法。将十进制数每次除以j，所得的余数依次入栈，然后按“后进先出”的次序出栈便得到转换的结果。
其算法原理是：
N =（N / j）* j + N % j
其中： / 为整除，%为求余
算法思想如下：
（1） 若 N<>0，则将N % j 取得的余数压入栈s中 ，执行（2）；
若N=0，将栈s的内容依次出栈，算法结束。
（2）  用N / j 代替 N
（3） 当N>0，则重复步骤（1）、（2）
算法的实现：
void Conversion(int n) // 将十进制数n转换为二进制数
{ linkstack s;
int x;
s.top=NULL;
do
{ x=n%2; // 除2取余
n=n/2;
stacknode *p=new stacknode; // 申请一个新结点
p->next=s.top; // 修改栈顶指针
s.top=p;
s.top->data=x; } // 入栈
while(n);
printf("转换后的二进制数值为：");
while(s.top) // 余数出栈处理
{
printf("%d",s.top->data); // 输出栈顶的余数
stacknode* p=s.top; // 修改栈顶指针
s.top=s.top->next;
delete p; // 回收一个结点，C语言中用free p
}
}

Ⅱ Java队列入队和堆栈出栈算法实现

class LinkedList //定义双项链表{char data;LinkedList back;LinkedList forward;}interface Access //定义从队列和栈存取操作的接口{void put(char c);char get();}class Queue implements Access //定义队列类{private LinkedList QHead=new LinkedList();private LinkedList QRear=QHead; //初始化队头和队尾public void put(char c) //实现向队列存数的方法{QRear.forward=new LinkedList();QRear.forward.data=c;QRear.forward.back=QRear;QRear=QRear.forward;}public char get() //实现从队列取数的方法{if(QHead!=QRear) //如果队列不为空则取数{QHead.forward.back=null;QHead=QHead.forward;return QHead.data;}else{System.out.println("The queue is empty! ");return '\0';}}}class Stack implements Access //定义栈类{private LinkedList bottom=new LinkedList();private LinkedList top=bottom; //初始化栈顶与斩底public void put(char c) //实现从栈中存数的方法{top.forward=new LinkedList();top.forward.data=c;top.forward.back=top;top=top.forward;}public char get() //实现从栈中取数的方法{if(top!=bottom) //如果栈不为空则取数{char ch=top.data;top.back.forward=null;top=top.back;return ch;}else{System.out.println("The stack is empty! ");return '\0';}}}public class StackQueue{public static void main(String[] args){char ch;Queue q=new Queue(); //创建一个队列qStack s=new Stack(); //创建一个栈sq.put('x');q.put('y');q.put('z'); //向队列q存入3个字符s.put('x');s.put('y');s.put('z'); //向栈s存入3个字符System.out.println("Queue: ");if((ch=q.get())!='\0')System.out.println(ch);if((ch=q.get())!='\0')System.out.println(ch);if((ch=q.get())!='\0')System.out.println(ch);if((ch=q.get())!='\0')System.out.println(ch);//从队列q中取数并显示System.out.println("Stack: ");if((ch=s.get())!='\0')System.out.println(ch);if((ch=s.get())!='\0')System.out.println(ch);if((ch=s.get())!='\0')System.out.println(ch);if((ch=s.get())!='\0')System.out.println(ch);//从栈s中取数并显示}}引自： http://wenwen.soso.com/z/q104863.htm?ch=w.xg.ll

Ⅲ 队列的队列的基本运算

（1）初始化队列：Init_Queue(q) ，初始条件：队q 不存在。操作结果：构造了一个空队；
（2）入队操作： In_Queue(q,x),初始条件： 队q 存在。操作结果： 对已存在的队列q，插入一个元素x 到队尾，队发生变化；
（3）出队操作： Out_Queue(q,x)，初始条件: 队q 存在且非空，操作结果： 删除队首元素，并返回其值，队发生变化；
（4）读队头元素：Front_Queue(q,x)，初始条件: 队q 存在且非空，操作结果： 读队头元素，并返回其值，队不变；
（5）判队空操作：Empty_Queue(q)，初始条件： 队q 存在，操作结果： 若q 为空队则返回为1，否则返回为0。 操作 类型 作用 返回值 例子 length(s) 函数 求字符串s的长度 整型 s:='123456789';
l:=length(s);{l的值为9} （s,w,k) 函数 复制s中从w开始的k位 字符串 s:='123456789';
s1:=(s,3,5);{s1的值是'34567'} val(s,k,code) 过程 将字符串s转为数值，存在k中；code是错误代码 var s:string;k,code:integer;
begin
s:='1234';
val(s,k,code);
write(k);{k=1234} str(i,s) 过程 将数值i转为字符串s i:=1234;
str(i,s);
write(s);{s='1234'} Delete(s,w,k) 过程 在s中删除从第w位开始的k个字符 s := 'Honest Abe Lincoln';
Delete(s,8,4);
Writeln(s); { 'Honest Lincoln' } Insert(s1, S, w) 过程 将s1插到s中第w位 S := 'Honest Lincoln';
Insert('Abe ', S, 8); { 'Honest Abe Lincoln' } Pos(c, S) 函数 求字符c在s中的位置 整型 S := ' 123.5';
i :=Pos(' ', S);{i的值为1} + 运算符 将两个字符串连接起来 s1:='1234';
s2:='5678';
s:=s1+s2;{'12345678'} 在STL中，对队列的使用很是较完美
下面给出循环队列的运算算法:
(1)将循环队列置为空
//将队列初始化
SeQueue::SeQueue()
{ front=0;
rear=0;
cout<<init!<<endl;
}
(2)判断循环队列是否为空
int SeQueue::Empty()
{ if(rear==front) return(1);
else return(0);
}
(3)在循环队列中插入新的元素x
void SeQueue::AddQ(ElemType x)
{ if((rear+1) % MAXSIZE==front) cout<< QUEUE IS FULL! <<endl;
else{ rear=(rear+1) % MAXSIZE;
elem[rear]=x;
cout<< OK!;
}
}
(4)删除队列中队首元素
ElemType SeQueue::DelQ()
{ if(front==rear)
{ cout<< QUEUE IS EMPTY! <<endl; return -1;}
else{ front=(front+1) % MAXSIZE;
return(elem[front]);
}
}
(5)取队列中的队首元素
ElemType SeQueue::Front()
{ ElemType x;
if(front== rear)
cout<<QUEUE IS EMPTY <<endl;
else x= elem[(front+1)%MAXSIZE];
return (x);
}

Ⅳ 循环队列的定义及其相关操作算法的实现

malloc这个函数的头文件你忘记包含了，在文件的开始处添加如下代码即可：
#include "malloc.h"

另外你的主函数main的返回类型没有给出，缺省时作为int型的返回值，但你的main中无返回一个int型值的语句，程序会给出一个警告，因此你最好将main函数设计为void类型的函数。

Ⅳ 用带尾指针的单循环链表作为队列的存储结构 设计算法以实现队列的各运算

typedef struct LNode {
//定义链表节点
int data;
struct LNode *next;
}LNode, *LinkList;

LinkList Head; //定义全局变量链表头

//构造空链表
LinkList InitList( )
{
static LinkList head;
head = (LinkList) malloc (sizeof(LNode));
if( ! head) exit (OVERFLOW);
head->next = NULL;
return head;
}

//输入数据插入到链表后，创建循环链表
Status CreateList(LinkList head ,int m)
{
LinkList p,q;
int i;
p = head;
for(i=1;i<m+1;i++) {
q = (LinkList)malloc(sizeof(LNode));
q->data = i;
q->next = NULL;
p->next = q;
p = p->next;
if(i == m) { p->next = Head->next; } //链成循环链表
}
return OK;
}

Ⅵ 多级队列调度算法的模拟，用C语言实现

多级反馈队列调度算法 多级反馈队列调度算法是一种CPU处理机调度算法，UNIX操作系统采取的便是这种调度算法。 多级反馈队列调度算法即能使高优先级的作业得到响应又能使短作业(进程)迅速完成。（对比一下FCFS与高优先响应比调度算法的缺陷）。 多级(假设为N级)反馈队列调度算法可以如下原理： 1、设有N个队列（Q1,Q2....QN），其中各个队列对于处理机的优先级是不一样的，也就是说位于各个队列中的作业(进程)的优先级也是不一样的。一般来说，优先级Priority(Q1) > Priority(Q2) > ... > Priority(QN)。怎么讲，位于Q1中的任何一个作业(进程)都要比Q2中的任何一个作业(进程)相对于CPU的优先级要高（也就是说，Q1中的作业一定要比Q2中的作业先被处理机调度），依次类推其它的队列。 2、对于某个特定的队列来说，里面是遵循时间片轮转法。也就是说，位于队列Q2中有N个作业，它们的运行时间是通过Q2这个队列所设定的时间片来确定的（为了便于理解，我们也可以认为特定队列中的作业的优先级是按照FCFS来调度的）。 3、各个队列的时间片是一样的吗？不一样，这就是该算法设计的精妙之处。各个队列的时间片是随着优先级的增加而减少的，也就是说，优先级越高的队列中它的时间片就越短。同时，为了便于那些超大作业的完成，最后一个队列QN(优先级最高的队列)的时间片一般很大(不需要考虑这个问题)。 多级反馈队列调度算法描述： 1、进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。 2、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。 3、对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。 4、在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。 我们来看一下该算法是如何运作的： 假设系统中有3个反馈队列Q1,Q2,Q3，时间片分别为2，4，8。 现在有3个作业J1,J2,J3分别在时间 0 ，1，3时刻到达。而它们所需要的CPU时间分别是3，2，1个时间片。 1、时刻0 J1到达。于是进入到队列1 ， 运行1个时间片 ， 时间片还未到，此时J2到达。 2、时刻1 J2到达。 由于时间片仍然由J1掌控，于是等待。 J1在运行了1个时间片后，已经完成了在Q1中的 2个时间片的限制，于是J1置于Q2等待被调度。现在处理机分配给J2。 3、时刻2 J1进入Q2等待调度，J2获得CPU开始运行。 4、时刻3 J3到达，由于J2的时间片未到，故J3在Q1等待调度，J1也在Q2等待调度。 5、时刻4 J2处理完成，由于J3，J1都在等待调度，但是J3所在的队列比J1所在的队列的优先级要高，于是J3被调度，J1继续在Q2等待。 6、时刻5 J3经过1个时间片，完成。 7、时刻6 由于Q1已经空闲，于是开始调度Q2中的作业，则J1得到处理器开始运行。 8、时刻7 J1再经过一个时间片，完成了任务。于是整个调度过程结束。

Ⅶ 怎么用C语言实现多级反馈队列调度算法

调度算法的实施过程如下所述：（1）应设置多个就绪队列，并为各个队列赋予不同的优先级。（2）当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS的原则排队等待调度。当轮到该进程执行时，如他能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列……，如此下去，当一个长作业进程从第一队列依次降到第N队列后，在第N队列中便采取时间片轮转的方式运行

Ⅷ 对于循环队列,试写出求队列含有多少个元素的算法,并将算法用C代码实现。

对于循环队列，求队列含有多少个元素的算法如下：

typedef struct
{
int tail,head;
int a[Max];
}queue;

void enqueue(int key,queue&q)
{
q.a[q.tail]=key;
q.tail=(q.tail+1)%Max;
}

int dequeue(queue&q)
{
int key;
key=q.a[q.head];
q.head=(q.head+1)%Max;
return key;
}

(8)队列的各算法的实现扩展阅读：

计算循环队列的元素个数：(尾－头＋表长)%表长

队列头指针为来front，队列尾指针为rear，队列容量为M，则元素个数为|rear-front+M|%M,注意，这个自%是求余运算。

设f为队头，r为队尾，m为队长，a为元素个数，则1. f>r时，a=m+r-f; 2. f<=r时，a=r-f

Ⅸ 用队列实现种子填充算法的非递归

一、种子填充算法（Seed Filling）
如果要填充的区域是以图像元数据方式给出的，通常使用种子填充算法（Seed Filling）进行区域填充。种子填充算法需要给出图像数据的区域，以及区域内的一个点，这种算法比较适合人机交互方式进行的图像填充操作，不适合计算机自动处理和判断填色。根据对图像区域边界定义方式以及对点的颜色修改方式，种子填充又可细分为几类，比如注入填充算法（Flood Fill Algorithm）、边界填充算法（Boundary Fill Algorithm）以及为减少递归和压栈次数而改进的扫描线种子填充算法等等。
所有种子填充算法的核心其实就是一个递归算法，都是从指定的种子点开始，向各个方向上搜索，逐个像素进行处理，直到遇到边界，各种种子填充算法只是在处理颜色和边界的方式上有所不同。在开始介绍种子填充算法之前，首先也介绍两个概念，就是“4-联通算法”和“8-联通算法”。既然是搜索就涉及到搜索的方向问题，从区域内任意一点出发，如果只是通过上、下、左、右四个方向搜索到达区域内的任意像素，则用这种方法填充的区域就称为四连通域，这种填充方法就称为“4-联通算法”。如果从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下全部八个方向到达区域内的任意像素，则这种方法填充的区域就称为八连通域，这种填充方法就称为“8-联通算法”。如图1（a）所示，假设中心的蓝色点是当前处理的点，如果是“4-联通算法”，则只搜索处理周围蓝色标识的四个点，如果是“8-联通算法”则除了处理上、下、左、右四个蓝色标识的点，还搜索处理四个红色标识的点。两种搜索算法的填充效果分别如如图1（b）和图1（c）所示，假如都是从黄色点开始填充，则“4-联通算法”如图1（b）所示只搜索填充左下角的区域，而“8-联通算法”则如图1（c）所示，将左下角和右上角的区域都填充了。

图（1） “4-联通”和“8-联通”填充效果

并不能仅仅因为图1的填充效果就认为“8-联通算法”一定比“4-联通算法”好，应该根据应用环境和实际的需求选择联通搜索方式，在很多情况下，只有“4-联通算法”才能得到正确的结果。
1.1 注入填充算法（Flood Fill Algorithm）
注入填充算法不特别强调区域的边界，它只是从指定位置开始，将所有联通区域内某种指定颜色的点都替换成另一种颜色，从而实现填充效果。注入填充算法能够实现颜色替换之类的功能，这在图像处理软件中都得到了广泛的应用。注入填充算法的实现非常简单，核心就是递归和搜索，以下就是注入填充算法的一个实现：

164 void FloodSeedFill(int x, int y, int old_color, int new_color)
165 {
166 if(GetPixelColor(x, y) == old_color)
167 {
168 SetPixelColor(x, y, new_color);
169 for(int i = 0; i < COUNT_OF(direction_8); i++)
170 {
171 FloodSeedFill(x + direction_8[i].x_offset,
172 y + direction_8[i].y_offset, old_color, new_color);
173 }
174 }
175 }

for循环实现了向8个联通方向的递归搜索，秘密就在direction_8的定义：

15 typedef struct tagDIRECTION
16 {
17 int x_offset;
18 int y_offset;
19 }DIRECTION;

79 DIRECTION direction_8[] = { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1},{0, -1}, {-1, -1} };

这个是搜索类算法中常用的技巧，无需做太多说明，其实只要将其替换成如下direction_4的定义，就可以将算法改成4个联通方向填充算法：

80 DIRECTION direction_4[] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };

图2就是应用本算法实现的“4-联通”和“8-联通”填充效果：

Ⅹ 利用队列的基本操作，实现栈的逆置，写一算法

算法思想很简单，就是输入字符串依次入队列b，然后在把队列中元素依次做出对操作并把返回值入栈a，然后再依次出栈并把返回值入队列c。 最后输出逆置操作前，即b中的元素； 输出逆置操作后，即c中的元素； 代码如下： //--------------------------------------------------------------------------- #include <stdio.h> #include <stdlib.h> typedef struct node{ char data; struct node *next; }node; typedef struct { node *top; unsigned int size; } stack; typedef struct{ node *front; node *back; unsigned int size; } queue; char pops(stack *a) { node *tf=NULL; char rt=0; if (a->size) { tf=a->top; a->top=a->top->next; --a->size; rt=tf->data; free(tf); } return rt; } char popq(queue *a) { node *tf=NULL; char rt=0; if (a->size) { tf=a->front; a->front=a->front->next; --a->size; rt=tf->data; free(tf); } return rt; } void push(stack *a,const char c) { node *t=(node*)malloc(sizeof(node)); if (t) { t->data=c; t->next=a->top; a->top=t; ++a->size; } } void push_back(queue *a,const char c) { node *t=(node*)malloc(sizeof(node)); if (t) { t->data=c; t->next=NULL; if (!a->size) { a->front=a->back=t; } else { a->back->next=t; a->back=t; } ++a->size; } } int isempty(void *a,int tp) { if (tp==1) return !(((stack *)a)->size); else return !(((queue *)a)->size); } void initqs(void *a,int tp) { if (tp==1) { ((stack*)a)->top=NULL; ((stack*)a)->size=0; } else{ ((queue*)a)->front=((queue*)a)->back=NULL; ((queue*)a)->size=0; } } void del(void *a,int tp) { node *t; if (tp==1) { while (((stack*)a)->top){ t= ((stack*)a)->top; ((stack*)a)->top=((stack*)a)->top->next; free(t); } free(a); } else { while (((queue*)a)->front){ t= ((queue*)a)->front; ((queue*)a)->front=((queue*)a)->front->next; free(t); } free(a); } } void chk() { char ch; int fg=1,rt=0; stack *a=(stack*)malloc(sizeof(stack)); queue *b=(queue*)malloc(sizeof(queue)); queue *c=(queue*)malloc(sizeof(queue)); queue *temp = (queue *)malloc(sizeof(queue)); if (!a||!b||!c||!temp) { fprintf(stderr,"MEMORY ERROR"); exit(-1); } initqs(a,1); initqs(b,0); initqs(c,0); initqs(temp,0); puts("Enter a string ,end with @"); while ((ch=getchar())!='@') { push_back(b,ch); push_back(temp,ch); } while (!isempty(temp, 0)) push(a, popq(temp)); while (!isempty(a,1)) push_back(c, pops(a)); printf("执行逆序算法前："); while (!isempty(b, 0)) { printf("%c ", popq(b)); } printf("\n执行逆序算法后："); while (!isempty(c, 0)) printf("%c ", popq(c)); printf("\n"); del(a,1); del(b,0); del(c,0); del(temp,0); } int main(void) { chk(); return 0; }