隊列的各演算法的實現

Ⅰ 使用棧和隊列解決演算法設計問題，對於怎樣的應用問題，需要使用棧和隊列，以及怎樣使用。遞歸演算法設計。

隊列在輸入、輸出管理中的應用
在計算機進行數據輸入、輸出處理時，由於外部設備的速度遠遠低於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; }