在編程語(yǔ)言中怎樣定義隊(duì)列及其使用(C++)
隊(duì)列在編程語(yǔ)言中是如何定義的呢？小編與大家分享自己的經(jīng)驗(yàn)。
隊(duì)列的定義
隊(duì)列是限制結(jié)點(diǎn)插入操作固定在一端進(jìn)行,而結(jié)點(diǎn)的刪除操作固定在另一端進(jìn)行的線性表.
隊(duì)列猶如一個(gè)兩端開(kāi)口的管道.允許插入的一端稱為隊(duì)頭,允許刪除的一端稱為隊(duì)尾.隊(duì)頭和隊(duì)尾各用一個(gè)”指針”指示,稱為隊(duì)頭指針和隊(duì)尾指針.不含任何結(jié)點(diǎn)的隊(duì)列稱為”空隊(duì)列”.隊(duì)列的特點(diǎn)是結(jié)點(diǎn)在隊(duì)列中的排隊(duì)次序和出隊(duì)次序按進(jìn)隊(duì)時(shí)間先后確定,即先進(jìn)隊(duì)者先出隊(duì).因此,隊(duì)列又稱先進(jìn)先出表.簡(jiǎn)稱FIFO(first in first out)表.
步驟
隊(duì)列是用來(lái)存儲(chǔ)暫未處理但需要按一定順序處理的元素的一種數(shù)據(jù)結(jié)構(gòu)。
隊(duì)列是一種先進(jìn)先出（First In First Out，F(xiàn)IFO）的線性表，特點(diǎn)是先進(jìn)隊(duì)的元素先出隊(duì)。
隊(duì)列只允許在表的一端進(jìn)行插入，而在另一端刪除元素。
隊(duì)尾是隊(duì)列中允許插入的一端；隊(duì)首是隊(duì)列中允許刪除的一端。
一般用順序表q[m]存儲(chǔ)隊(duì)列中的元素，m是隊(duì)列能存儲(chǔ)元素的最大數(shù)量。
front隊(duì)首指針指向隊(duì)首元素存儲(chǔ)的位置；rear隊(duì)尾指針指向隊(duì)尾元素的下一個(gè)位置。
順序隊(duì)列及其操作
隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)
順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的隊(duì)列稱為順序隊(duì)列.和順序表一樣,用一個(gè)一維數(shù)組存.對(duì)頭在數(shù)組的低下標(biāo)端,隊(duì)尾設(shè)在高下表端.隊(duì)頭,隊(duì)尾指針值是數(shù)組元素的下標(biāo).對(duì)頭指針始終指向?qū)︻^結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)位置,初始值為0.隊(duì)尾指針是指向隊(duì)尾結(jié)點(diǎn)位置,初始值也為0.
隊(duì)列初始條件:隊(duì)頭指針=隊(duì)尾指針=0
隊(duì)列滿條件:隊(duì)尾指針=m(設(shè)隊(duì)列當(dāng)前容量為m)
隊(duì)列空條件:隊(duì)頭指針=隊(duì)尾指針
在QueueCs.c文件中定義了結(jié)構(gòu)
#define DT char
#define M 100
typedef struct {
DT data[M];
int front,rear;
}SEQUEUE;
data[M]也為數(shù)組為隊(duì)列,front為隊(duì)頭指針,rear為隊(duì)尾指針.(注意:front和rear是整數(shù)類型,不是指針類型),當(dāng)front=rear=0時(shí),為初始隊(duì)列.因?yàn)镃語(yǔ)言中數(shù)組的第一個(gè)元素下標(biāo)為0,而不是1;所以這里約定數(shù)組元素data[0]閑置不用.
順序隊(duì)列上的操作
(1)創(chuàng)建隊(duì)列
初始化隊(duì)列,隊(duì)頭指針和隊(duì)尾指針=0.
在QueueControl.h寫出方法聲明
/* 創(chuàng)建隊(duì)列 */ SEQUEUE initQueue();
在QueueControl.c中實(shí)現(xiàn)此方法
#include "QueueControl.h"
/*
創(chuàng)建隊(duì)列
*/
SEQUEUE initQueue(){
SEQUEUE Q;
//1.初始化隊(duì)列,隊(duì)頭指針=隊(duì)尾指針=0
Q.front=Q.rear=0;
return Q;
}
(2)插入
在QueueControl.h寫出方法聲明
/* 插入 */ SEQUEUE inQueue(SEQUEUE Q,DT x);
在QueueControl.c中實(shí)現(xiàn)此方法
#include "QueueControl.h"
SEQUEUE inQueue(SEQUEUE Q,DT x){
//1.判斷隊(duì)列是上溢,就是隊(duì)尾指針是否等于最大申請(qǐng)的空間
if(Q.rear==M){
printf("Up Overflow\n");
}else{
//2.從隊(duì)尾插入結(jié)點(diǎn)
Q.rear++;
Q.data[Q.rear]=x;
printf("in success\n");
}
return Q;
}
(3)刪除
在QueueControl.h寫出方法聲明
/* 刪除 */ SEQUEUE outQueue(SEQUEUE Q); /* 打印隊(duì)列元素 */ void printQueue(SEQUEUE Q);
在QueueControl.c中實(shí)現(xiàn)此方法
#include "QueueControl.h"
SEQUEUE outQueue(SEQUEUE Q){
//1.首先判斷是否是空隊(duì)列
if(Q.front==Q.rear){
printf("queue is empty\n");
}else{
//2.刪除結(jié)點(diǎn)是從隊(duì)頭刪除
Q.front++;
printf("out success\n");
}
return Q;
}
/*
打印隊(duì)列元素
*/
void printQueue(SEQUEUE Q){
//1.從隊(duì)頭開(kāi)始打印數(shù)據(jù)
SEQUEUE temp=Q;
printf("queue={");
while (temp.front<temp.rear) {
temp.front++;
if(temp.front==Q.front+1){
printf("%c",temp.data[temp.front]);
}else{
printf(",%c",temp.data[temp.front]);
}
}
printf("}\n");
}
在main.c中的main方法(int main(int argc, const char * argv[]) {})調(diào)用此方法,并且進(jìn)行判斷
#include "QueueControl.h"
int main(int argc, const char * argv[]) {
//初始化順序隊(duì)列
SEQUEUE queue=initQueue();
printQueue(queue);
//插入
queue=inQueue(queue, 'a');
queue=inQueue(queue, 'b');
queue=inQueue(queue, 'c');
queue=inQueue(queue, 'd');
printQueue(queue);
//刪除
queue=outQueue(queue);
printQueue(queue);
return 0;
}
打印結(jié)果:
queue={}
in success
in success
in success
in success
queue={a,b,c,d}
out success
queue={b,c,d}
Program ended with exit code: 0
從插入隊(duì)列和刪除隊(duì)列操作的打印結(jié)果來(lái)看,隊(duì)列的特點(diǎn)確實(shí)是:先進(jìn)先出.
循環(huán)隊(duì)列及其操作
循環(huán)隊(duì)列的存儲(chǔ)結(jié)構(gòu)
根據(jù)順序隊(duì)列的操作和敘述可以看出,隊(duì)尾指針=m表示隊(duì)滿,不能再插入結(jié)點(diǎn)了,當(dāng)隊(duì)頭指針等于隊(duì)尾指針表示對(duì)空.但是當(dāng)隊(duì)尾指針和隊(duì)尾指針都等于m的時(shí)候,那么此時(shí)表示對(duì)空,那么也不能插入了其他的結(jié)點(diǎn),但是此時(shí)0-m之間的結(jié)點(diǎn)已經(jīng)空閑,這樣許多空閑的結(jié)點(diǎn)不能被利用,浪費(fèi)存儲(chǔ)空間.
循環(huán)隊(duì)列是把順序隊(duì)列的頭尾相接形成一個(gè)圓環(huán).邏輯上吧1號(hào)結(jié)點(diǎn)作為m號(hào)結(jié)點(diǎn)的后繼結(jié)點(diǎn)處理.
循環(huán)隊(duì)列初始條件:隊(duì)頭指針=隊(duì)尾指針=0
循環(huán)隊(duì)列隊(duì)滿條件:MOD(隊(duì)尾指針+1,m)=隊(duì)頭指針
循環(huán)隊(duì)列空條件:隊(duì)頭指針=隊(duì)尾指針
隊(duì)頭指針推進(jìn)計(jì)算:隊(duì)頭指針=MOD(隊(duì)頭指針+1,m)
隊(duì)尾指針推進(jìn)計(jì)算:隊(duì)尾指針=MOD(隊(duì)尾指針+1,m)
在QueueCycleCs.c文件中定義了結(jié)構(gòu)
#define CDT char
#define CM 5
typedef struct {
CDT data[CM];
int front,rear;
}SECYCLEQUEUE;
循環(huán)隊(duì)列上的操作
(1)創(chuàng)建循環(huán)隊(duì)列
初始化隊(duì)列,隊(duì)頭指針和隊(duì)尾指針=0.
在QueueCycyleControl.h寫出方法聲明
#include "QueueCycleCs.c" /* 創(chuàng)建循環(huán)隊(duì)列 */ SECYCLEQUEUE initCycleQueue();
在QueueCycyleControl.c中實(shí)現(xiàn)此方法
#include "QueueCycleControl.h"
/*
創(chuàng)建循環(huán)隊(duì)列
*/
SECYCLEQUEUE initCycleQueue(){
SECYCLEQUEUE Q;
//隊(duì)頭指針=隊(duì)尾指針=0;
Q.front=Q.rear=0;
return Q;
}
(2)插入
在QueueCycyleControl.h寫出方法聲明
#include "QueueCycleCs.c" /* 循環(huán)隊(duì)列插入 */ SECYCLEQUEUE inCycleQueue(SECYCLEQUEUE Q,char x);
在QueueCycyleControl.c中實(shí)現(xiàn)此方法
#include "QueueCycleControl.h"
SECYCLEQUEUE inCycleQueue(SECYCLEQUEUE Q,CDT x){
//1.判斷循環(huán)隊(duì)列是否已經(jīng)滿了,MOD(隊(duì)尾指針+1,m)=隊(duì)頭指針
if((Q.rear+1)%CM==Q.front){
printf("queue is full!\n");
}else{
//2.在隊(duì)尾插入,計(jì)算隊(duì)尾指針的
Q.rear=(Q.rear+1)%CM;
//3.設(shè)置插入結(jié)點(diǎn)的值數(shù)值
Q.data[Q.rear]=x;
printf("in Cycle queue Success!\n");
}
return Q;
}
(3)刪除
在QueueCycyleControl.h寫出方法聲明
#include "QueueCycleCs.c" /* 循環(huán)隊(duì)列刪除 */ SECYCLEQUEUE outCycleQueue(SECYCLEQUEUE Q); /* 打印循環(huán)隊(duì)列 */ void printCycleQueue(SECYCLEQUEUE Q);
在QueueCycyleControl.c中實(shí)現(xiàn)此方法
#include "QueueCycleControl.h"
SECYCLEQUEUE outCycleQueue(SECYCLEQUEUE Q){
//1.判斷循環(huán)隊(duì)列是否是空
if(Q.front==Q.rear){
printf("Cycle queue is Empty!\n");
}else{
//2.刪除結(jié)點(diǎn)從隊(duì)頭刪除,計(jì)算隊(duì)頭指針:隊(duì)頭指針=MOD(隊(duì)頭指針+1,m)
Q.front=(Q.front+1)%CM;
printf("out cycle queue success!\n");
}
return Q;
}
/*
打印循環(huán)隊(duì)列
*/
void printCycleQueue(SECYCLEQUEUE Q){
//M=5;
//1.從隊(duì)頭開(kāi)始打印數(shù)據(jù)
SECYCLEQUEUE temp=Q;
printf("queue={");
//2.判斷的條件是,隊(duì)頭指針!=隊(duì)尾指針
while (temp.front!=temp.rear) {
temp.front=(temp.front+1)%CM;
if(temp.front==((Q.front+1)%CM)){
printf("%c",temp.data[temp.front]);
}else{
printf(",%c",temp.data[temp.front]);
}
}
printf("}\n");
}
在main.c中的main方法(int main(int argc, const char * argv[]) {})調(diào)用此方法,并且進(jìn)行判斷
#include "QueueCycleControl.h"
int main(int argc, const char * argv[]) {
//創(chuàng)建循環(huán)隊(duì)列
SECYCLEQUEUE CQ=initCycleQueue();
//插入數(shù)據(jù)5個(gè)結(jié)點(diǎn),但是最大是5,一個(gè)空閑,最后一個(gè)添加不進(jìn)去,
CQ=inCycleQueue(CQ, 'a');
CQ=inCycleQueue(CQ, 'b');
CQ=inCycleQueue(CQ, 'c');
CQ=inCycleQueue(CQ, 'd');
CQ=inCycleQueue(CQ, 'e');
printCycleQueue(CQ);
//刪除節(jié)點(diǎn)-三個(gè)結(jié)點(diǎn)
CQ=outCycleQueue(CQ);
CQ=outCycleQueue(CQ);
CQ=outCycleQueue(CQ);
printCycleQueue(CQ);
//插入-兩個(gè)結(jié)點(diǎn)
CQ=inCycleQueue(CQ, 'e');
CQ=inCycleQueue(CQ, 'f');
printCycleQueue(CQ);
//刪除節(jié)點(diǎn)--刪除四個(gè)結(jié)點(diǎn),現(xiàn)在此時(shí)是三個(gè)結(jié)點(diǎn),最后一個(gè)刪除不了
CQ=outCycleQueue(CQ);
CQ=outCycleQueue(CQ);
CQ=outCycleQueue(CQ);
CQ=outCycleQueue(CQ);
printCycleQueue(CQ);
return 0;
}
打印結(jié)果:
in Cycle queue Success!
in Cycle queue Success!
in Cycle queue Success!
in Cycle queue Success!
queue is full!
queue={a,b,c,d}
out cycle queue success!
out cycle queue success!
out cycle queue success!
queue=l4l4wckh0sl
in Cycle queue Success!
in Cycle queue Success!
queue={d,e,f}
out cycle queue success!
out cycle queue success!
out cycle queue success!
Cycle queue is Empty!
queue={}
Program ended with exit code: 0
鏈隊(duì)列及其操作
隊(duì)列的鏈存儲(chǔ)結(jié)構(gòu)
鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的隊(duì)列稱為鏈隊(duì)列.隊(duì)頭指針指向鏈隊(duì)列的頭結(jié)點(diǎn),頭結(jié)點(diǎn)的指針域若為空,則為空隊(duì)列;若不為空,則為指向隊(duì)首結(jié)點(diǎn)的指針.
鏈隊(duì)列設(shè)有一個(gè)隊(duì)頭指針,其值指向隊(duì)列的頭結(jié)點(diǎn).也是唯一地標(biāo)示一個(gè)鏈隊(duì).設(shè)置一個(gè)隊(duì)尾指針?lè)奖悴迦虢Y(jié)點(diǎn).隊(duì)頭指針和隊(duì)尾指針都是指針型變量.
鏈隊(duì)列沒(méi)有容量的限制,所以在可用的存儲(chǔ)空間范圍內(nèi),一般不會(huì)出現(xiàn)上溢問(wèn)題,也不存在如順序隊(duì)列的假溢出問(wèn)題.
在QueueLinkCs.c中定義了結(jié)構(gòu)
#define LDT char
//結(jié)點(diǎn)類型
typedef struct llnode{
LDT data;
struct llnode *next;
}LINKNODE;
//鏈隊(duì)列結(jié)構(gòu)
typedef struct{
LINKNODE *front,*rear;
}LINKQUEUE;
鏈隊(duì)列上的操作
(1)創(chuàng)建鏈隊(duì)列
在QueueLinkControl.h寫出方法聲明
#include <stdio.h> #include "QueueLinkCs.c" /* 創(chuàng)建鏈隊(duì) */ LINKQUEUE * initLinkQueue(LINKQUEUE *LQ);
在QueueLinkControl.c中實(shí)現(xiàn)此方法
#include "QueueLinkControl.h"
#include <stdlib.h>
/*
創(chuàng)建鏈隊(duì)
*/
LINKQUEUE *initLinkQueue(LINKQUEUE *LQ){
//設(shè)置隊(duì)頭指針
LQ->front=(LINKNODE *)malloc(sizeof(LINKNODE));
LQ->front->data='#';//設(shè)置隊(duì)頭指針,也是頭結(jié)點(diǎn)的指針域
LQ->front->next=NULL;
//初始條件:隊(duì)頭指針和隊(duì)尾指針一致
LQ->rear=LQ->front;
return LQ;
}
(2)插入
在QueueLinkControl.h寫出方法聲明
/* 鏈隊(duì)插入:隊(duì)尾 */ LINKQUEUE * inLinkQueue(LINKQUEUE *LQ,LDT x);
在QueueLinkControl.c中實(shí)現(xiàn)此方法
(3)刪除
在QueueLinkControl.h寫出方法聲明
/* 鏈隊(duì)刪除:隊(duì)頭 */ LINKQUEUE *outLinkQueue(LINKQUEUE *LQ); /* 打印鏈表結(jié)點(diǎn) */ void printLinkQueue(LINKQUEUE *LQ);
在QueueLinkControl.c中實(shí)現(xiàn)此方法
#include "QueueLinkControl.h"
#include <stdlib.h>
LINKQUEUE *outLinkQueue(LINKQUEUE *LQ){
if(LQ==NULL || LQ->rear==LQ->front){
printf("LQ is empty!\n");
return LQ;
}
//1.獲取首結(jié)點(diǎn)
LINKNODE *frontNextNode;
frontNextNode=LQ->front->next;
//2.將首節(jié)點(diǎn)的next指針域的值存儲(chǔ)頭結(jié)點(diǎn)的next域
LQ->front->next=frontNextNode->next;
//3.如果隊(duì)尾結(jié)點(diǎn)等于首節(jié)點(diǎn)的next指針域的值,那么表示是空棧,根據(jù)空鏈隊(duì)列的結(jié)構(gòu),還需修改隊(duì)尾指針,使指向頭結(jié)點(diǎn).
if(LQ->rear==frontNextNode){
LQ->rear=LQ->front;
}
//4.釋放刪除的結(jié)點(diǎn)
free(frontNextNode);
printf("out link queue success!\n");
return LQ;
}
/*
打印鏈表結(jié)點(diǎn)
*/
void printLinkQueue(LINKQUEUE *Q){
//實(shí)例化一個(gè)LQ,為了不改變?cè)瓉?lái)鏈隊(duì)Q
LINKQUEUE *LQ;
LQ=(LINKQUEUE *)malloc(sizeof(LINKQUEUE));
LQ->front=Q->front;
LQ->rear=Q->rear;
printf("queue={");
//1.判斷不是空鏈表
if(LQ!=NULL && LQ->rear!=LQ->front){
int flag=0;
do{
//2.輸出數(shù)據(jù)
if(flag==0){
printf("%c",LQ->front->data);
flag=1;
}else{
printf(",%c",LQ->front->data);
}
//3.鏈頭指針向后移動(dòng)
LQ->front=LQ->front->next;
}while (LQ->front!=LQ->rear) ;
printf(",%c",LQ->front->data);
}
printf("}\n");
}
在main.c中的main方法(int main(int argc, const char * argv[]) {})調(diào)用此方法,并且進(jìn)行判斷
#include "QueueLinkControl.h"
int main(int argc, const char * argv[]) {
//創(chuàng)建鏈隊(duì)列
LINKQUEUE *LQ=(LINKQUEUE *)malloc(sizeof(LINKQUEUE));
LQ=initLinkQueue(LQ);
//向鏈隊(duì)插入結(jié)點(diǎn)
LQ=inLinkQueue(LQ,'a');
LQ=inLinkQueue(LQ,'b');
LQ=inLinkQueue(LQ,'c');
LQ=inLinkQueue(LQ,'d');
printLinkQueue(LQ);
//刪除結(jié)點(diǎn)--從隊(duì)頭
LQ=outLinkQueue(LQ);
LQ=outLinkQueue(LQ);
printLinkQueue(LQ);
return 0;
}
打印結(jié)果:
in link queue success!
in link queue success!
in link queue success!
in link queue success!
queue={#,a,b,c,d}
out link queue success!
out link queue success!
queue={#,c,d}
Program ended with exit code: 0
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持我們。
上一篇：C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之迷宮問(wèn)題
欄 目：C語(yǔ)言
下一篇：C語(yǔ)言合并兩個(gè)帶頭節(jié)點(diǎn)升序排列鏈表
本文標(biāo)題：在編程語(yǔ)言中怎樣定義隊(duì)列及其使用(C++)
本文地址：http://www.jygsgssxh.com/a1/Cyuyan/406.html
您可能感興趣的文章
- 04-02func函數(shù)+在C語(yǔ)言 func函數(shù)在c語(yǔ)言中
- 04-02c語(yǔ)言中對(duì)數(shù)函數(shù)的表達(dá)式 c語(yǔ)言中對(duì)數(shù)怎么表達(dá)
- 04-02C語(yǔ)言中怎么打出三角函數(shù) c語(yǔ)言中怎么打出三角函數(shù)的值
- 01-10APUE筆記之:進(jìn)程環(huán)境詳解
- 01-10c++中inline的用法分析
- 01-10深入理解堆排序及其分析
- 01-10深入C/C++浮點(diǎn)數(shù)在內(nèi)存中的存儲(chǔ)方式詳解
- 01-10深入解析Linux下\r\n的問(wèn)題
- 01-10基于getline()函數(shù)的深入理解
- 01-10深入理解C/C++混合編程
閱讀排行
- 1C語(yǔ)言 while語(yǔ)句的用法詳解
- 2java 實(shí)現(xiàn)簡(jiǎn)單圣誕樹(shù)的示例代碼(圣誕
- 3利用C語(yǔ)言實(shí)現(xiàn)“百馬百擔(dān)”問(wèn)題方法
- 4C語(yǔ)言中計(jì)算正弦的相關(guān)函數(shù)總結(jié)
- 5c語(yǔ)言計(jì)算三角形面積代碼
- 6什么是 WSH(腳本宿主)的詳細(xì)解釋
- 7C++ 中隨機(jī)函數(shù)random函數(shù)的使用方法
- 8正則表達(dá)式匹配各種特殊字符
- 9C語(yǔ)言十進(jìn)制轉(zhuǎn)二進(jìn)制代碼實(shí)例
- 10C語(yǔ)言查找數(shù)組里數(shù)字重復(fù)次數(shù)的方法
本欄相關(guān)
- 04-02c語(yǔ)言函數(shù)調(diào)用后清空內(nèi)存 c語(yǔ)言調(diào)用
- 04-02func函數(shù)+在C語(yǔ)言 func函數(shù)在c語(yǔ)言中
- 04-02c語(yǔ)言的正則匹配函數(shù) c語(yǔ)言正則表達(dá)
- 04-02c語(yǔ)言用函數(shù)寫分段 用c語(yǔ)言表示分段
- 04-02c語(yǔ)言中對(duì)數(shù)函數(shù)的表達(dá)式 c語(yǔ)言中對(duì)
- 04-02c語(yǔ)言編寫函數(shù)冒泡排序 c語(yǔ)言冒泡排
- 04-02c語(yǔ)言沒(méi)有round函數(shù) round c語(yǔ)言
- 04-02c語(yǔ)言分段函數(shù)怎么求 用c語(yǔ)言求分段
- 04-02C語(yǔ)言中怎么打出三角函數(shù) c語(yǔ)言中怎
- 04-02c語(yǔ)言調(diào)用函數(shù)求fibo C語(yǔ)言調(diào)用函數(shù)求
隨機(jī)閱讀
- 08-05織夢(mèng)dedecms什么時(shí)候用欄目交叉功能？
- 08-05dedecms(織夢(mèng))副欄目數(shù)量限制代碼修改
- 08-05DEDE織夢(mèng)data目錄下的sessions文件夾有什
- 01-11ajax實(shí)現(xiàn)頁(yè)面的局部加載
- 01-10SublimeText編譯C開(kāi)發(fā)環(huán)境設(shè)置
- 01-10delphi制作wav文件的方法
- 01-10使用C語(yǔ)言求解撲克牌的順子及n個(gè)骰子
- 04-02jquery與jsp,用jquery
- 01-11Mac OSX 打開(kāi)原生自帶讀寫NTFS功能(圖文
- 01-10C#中split用法實(shí)例總結(jié)