在編程語言中怎樣定義隊列及其使用(C++)
隊列在編程語言中是如何定義的呢？小編與大家分享自己的經(jīng)驗。
隊列的定義
隊列是限制結點插入操作固定在一端進行,而結點的刪除操作固定在另一端進行的線性表.
隊列猶如一個兩端開口的管道.允許插入的一端稱為隊頭,允許刪除的一端稱為隊尾.隊頭和隊尾各用一個”指針”指示,稱為隊頭指針和隊尾指針.不含任何結點的隊列稱為”空隊列”.隊列的特點是結點在隊列中的排隊次序和出隊次序按進隊時間先后確定,即先進隊者先出隊.因此,隊列又稱先進先出表.簡稱FIFO(first in first out)表.
步驟
隊列是用來存儲暫未處理但需要按一定順序處理的元素的一種數(shù)據(jù)結構。
隊列是一種先進先出（First In First Out，F(xiàn)IFO）的線性表，特點是先進隊的元素先出隊。
隊列只允許在表的一端進行插入，而在另一端刪除元素。
隊尾是隊列中允許插入的一端；隊首是隊列中允許刪除的一端。
一般用順序表q[m]存儲隊列中的元素，m是隊列能存儲元素的最大數(shù)量。
front隊首指針指向隊首元素存儲的位置；rear隊尾指針指向隊尾元素的下一個位置。
順序隊列及其操作
隊列的順序存儲結構
順序存儲結構存儲的隊列稱為順序隊列.和順序表一樣,用一個一維數(shù)組存.對頭在數(shù)組的低下標端,隊尾設在高下表端.隊頭,隊尾指針值是數(shù)組元素的下標.對頭指針始終指向對頭結點的前一個結點位置,初始值為0.隊尾指針是指向隊尾結點位置,初始值也為0.
隊列初始條件:隊頭指針=隊尾指針=0
隊列滿條件:隊尾指針=m(設隊列當前容量為m)
隊列空條件:隊頭指針=隊尾指針
在QueueCs.c文件中定義了結構
#define DT char
#define M 100
typedef struct {
DT data[M];
int front,rear;
}SEQUEUE;
data[M]也為數(shù)組為隊列,front為隊頭指針,rear為隊尾指針.(注意:front和rear是整數(shù)類型,不是指針類型),當front=rear=0時,為初始隊列.因為C語言中數(shù)組的第一個元素下標為0,而不是1;所以這里約定數(shù)組元素data[0]閑置不用.
順序隊列上的操作
(1)創(chuàng)建隊列
初始化隊列,隊頭指針和隊尾指針=0.
在QueueControl.h寫出方法聲明
/* 創(chuàng)建隊列 */ SEQUEUE initQueue();
在QueueControl.c中實現(xiàn)此方法
#include "QueueControl.h"
/*
創(chuàng)建隊列
*/
SEQUEUE initQueue(){
SEQUEUE Q;
//1.初始化隊列,隊頭指針=隊尾指針=0
Q.front=Q.rear=0;
return Q;
}
(2)插入
在QueueControl.h寫出方法聲明
/* 插入 */ SEQUEUE inQueue(SEQUEUE Q,DT x);
在QueueControl.c中實現(xiàn)此方法
#include "QueueControl.h"
SEQUEUE inQueue(SEQUEUE Q,DT x){
//1.判斷隊列是上溢,就是隊尾指針是否等于最大申請的空間
if(Q.rear==M){
printf("Up Overflow\n");
}else{
//2.從隊尾插入結點
Q.rear++;
Q.data[Q.rear]=x;
printf("in success\n");
}
return Q;
}
(3)刪除
在QueueControl.h寫出方法聲明
/* 刪除 */ SEQUEUE outQueue(SEQUEUE Q); /* 打印隊列元素 */ void printQueue(SEQUEUE Q);
在QueueControl.c中實現(xiàn)此方法
#include "QueueControl.h"
SEQUEUE outQueue(SEQUEUE Q){
//1.首先判斷是否是空隊列
if(Q.front==Q.rear){
printf("queue is empty\n");
}else{
//2.刪除結點是從隊頭刪除
Q.front++;
printf("out success\n");
}
return Q;
}
/*
打印隊列元素
*/
void printQueue(SEQUEUE Q){
//1.從隊頭開始打印數(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[]) {})調用此方法,并且進行判斷
#include "QueueControl.h"
int main(int argc, const char * argv[]) {
//初始化順序隊列
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;
}
打印結果:
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
從插入隊列和刪除隊列操作的打印結果來看,隊列的特點確實是:先進先出.
循環(huán)隊列及其操作
循環(huán)隊列的存儲結構
根據(jù)順序隊列的操作和敘述可以看出,隊尾指針=m表示隊滿,不能再插入結點了,當隊頭指針等于隊尾指針表示對空.但是當隊尾指針和隊尾指針都等于m的時候,那么此時表示對空,那么也不能插入了其他的結點,但是此時0-m之間的結點已經(jīng)空閑,這樣許多空閑的結點不能被利用,浪費存儲空間.
循環(huán)隊列是把順序隊列的頭尾相接形成一個圓環(huán).邏輯上吧1號結點作為m號結點的后繼結點處理.
循環(huán)隊列初始條件:隊頭指針=隊尾指針=0
循環(huán)隊列隊滿條件:MOD(隊尾指針+1,m)=隊頭指針
循環(huán)隊列空條件:隊頭指針=隊尾指針
隊頭指針推進計算:隊頭指針=MOD(隊頭指針+1,m)
隊尾指針推進計算:隊尾指針=MOD(隊尾指針+1,m)
在QueueCycleCs.c文件中定義了結構
#define CDT char
#define CM 5
typedef struct {
CDT data[CM];
int front,rear;
}SECYCLEQUEUE;
循環(huán)隊列上的操作
(1)創(chuàng)建循環(huán)隊列
初始化隊列,隊頭指針和隊尾指針=0.
在QueueCycyleControl.h寫出方法聲明
#include "QueueCycleCs.c" /* 創(chuàng)建循環(huán)隊列 */ SECYCLEQUEUE initCycleQueue();
在QueueCycyleControl.c中實現(xiàn)此方法
#include "QueueCycleControl.h"
/*
創(chuàng)建循環(huán)隊列
*/
SECYCLEQUEUE initCycleQueue(){
SECYCLEQUEUE Q;
//隊頭指針=隊尾指針=0;
Q.front=Q.rear=0;
return Q;
}
(2)插入
在QueueCycyleControl.h寫出方法聲明
#include "QueueCycleCs.c" /* 循環(huán)隊列插入 */ SECYCLEQUEUE inCycleQueue(SECYCLEQUEUE Q,char x);
在QueueCycyleControl.c中實現(xiàn)此方法
#include "QueueCycleControl.h"
SECYCLEQUEUE inCycleQueue(SECYCLEQUEUE Q,CDT x){
//1.判斷循環(huán)隊列是否已經(jīng)滿了,MOD(隊尾指針+1,m)=隊頭指針
if((Q.rear+1)%CM==Q.front){
printf("queue is full!\n");
}else{
//2.在隊尾插入,計算隊尾指針的
Q.rear=(Q.rear+1)%CM;
//3.設置插入結點的值數(shù)值
Q.data[Q.rear]=x;
printf("in Cycle queue Success!\n");
}
return Q;
}
(3)刪除
在QueueCycyleControl.h寫出方法聲明
#include "QueueCycleCs.c" /* 循環(huán)隊列刪除 */ SECYCLEQUEUE outCycleQueue(SECYCLEQUEUE Q); /* 打印循環(huán)隊列 */ void printCycleQueue(SECYCLEQUEUE Q);
在QueueCycyleControl.c中實現(xiàn)此方法
#include "QueueCycleControl.h"
SECYCLEQUEUE outCycleQueue(SECYCLEQUEUE Q){
//1.判斷循環(huán)隊列是否是空
if(Q.front==Q.rear){
printf("Cycle queue is Empty!\n");
}else{
//2.刪除結點從隊頭刪除,計算隊頭指針:隊頭指針=MOD(隊頭指針+1,m)
Q.front=(Q.front+1)%CM;
printf("out cycle queue success!\n");
}
return Q;
}
/*
打印循環(huán)隊列
*/
void printCycleQueue(SECYCLEQUEUE Q){
//M=5;
//1.從隊頭開始打印數(shù)據(jù)
SECYCLEQUEUE temp=Q;
printf("queue={");
//2.判斷的條件是,隊頭指針!=隊尾指針
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[]) {})調用此方法,并且進行判斷
#include "QueueCycleControl.h"
int main(int argc, const char * argv[]) {
//創(chuàng)建循環(huán)隊列
SECYCLEQUEUE CQ=initCycleQueue();
//插入數(shù)據(jù)5個結點,但是最大是5,一個空閑,最后一個添加不進去,
CQ=inCycleQueue(CQ, 'a');
CQ=inCycleQueue(CQ, 'b');
CQ=inCycleQueue(CQ, 'c');
CQ=inCycleQueue(CQ, 'd');
CQ=inCycleQueue(CQ, 'e');
printCycleQueue(CQ);
//刪除節(jié)點-三個結點
CQ=outCycleQueue(CQ);
CQ=outCycleQueue(CQ);
CQ=outCycleQueue(CQ);
printCycleQueue(CQ);
//插入-兩個結點
CQ=inCycleQueue(CQ, 'e');
CQ=inCycleQueue(CQ, 'f');
printCycleQueue(CQ);
//刪除節(jié)點--刪除四個結點,現(xiàn)在此時是三個結點,最后一個刪除不了
CQ=outCycleQueue(CQ);
CQ=outCycleQueue(CQ);
CQ=outCycleQueue(CQ);
CQ=outCycleQueue(CQ);
printCycleQueue(CQ);
return 0;
}
打印結果:
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=vvxyksv9kd
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
鏈隊列及其操作
隊列的鏈存儲結構
鏈存儲結構存儲的隊列稱為鏈隊列.隊頭指針指向鏈隊列的頭結點,頭結點的指針域若為空,則為空隊列;若不為空,則為指向隊首結點的指針.
鏈隊列設有一個隊頭指針,其值指向隊列的頭結點.也是唯一地標示一個鏈隊.設置一個隊尾指針方便插入結點.隊頭指針和隊尾指針都是指針型變量.
鏈隊列沒有容量的限制,所以在可用的存儲空間范圍內,一般不會出現(xiàn)上溢問題,也不存在如順序隊列的假溢出問題.
在QueueLinkCs.c中定義了結構
#define LDT char
//結點類型
typedef struct llnode{
LDT data;
struct llnode *next;
}LINKNODE;
//鏈隊列結構
typedef struct{
LINKNODE *front,*rear;
}LINKQUEUE;
鏈隊列上的操作
(1)創(chuàng)建鏈隊列
在QueueLinkControl.h寫出方法聲明
#include <stdio.h> #include "QueueLinkCs.c" /* 創(chuàng)建鏈隊 */ LINKQUEUE * initLinkQueue(LINKQUEUE *LQ);
在QueueLinkControl.c中實現(xiàn)此方法
#include "QueueLinkControl.h"
#include <stdlib.h>
/*
創(chuàng)建鏈隊
*/
LINKQUEUE *initLinkQueue(LINKQUEUE *LQ){
//設置隊頭指針
LQ->front=(LINKNODE *)malloc(sizeof(LINKNODE));
LQ->front->data='#';//設置隊頭指針,也是頭結點的指針域
LQ->front->next=NULL;
//初始條件:隊頭指針和隊尾指針一致
LQ->rear=LQ->front;
return LQ;
}
(2)插入
在QueueLinkControl.h寫出方法聲明
/* 鏈隊插入:隊尾 */ LINKQUEUE * inLinkQueue(LINKQUEUE *LQ,LDT x);
在QueueLinkControl.c中實現(xiàn)此方法
(3)刪除
在QueueLinkControl.h寫出方法聲明
/* 鏈隊刪除:隊頭 */ LINKQUEUE *outLinkQueue(LINKQUEUE *LQ); /* 打印鏈表結點 */ void printLinkQueue(LINKQUEUE *LQ);
在QueueLinkControl.c中實現(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.獲取首結點
LINKNODE *frontNextNode;
frontNextNode=LQ->front->next;
//2.將首節(jié)點的next指針域的值存儲頭結點的next域
LQ->front->next=frontNextNode->next;
//3.如果隊尾結點等于首節(jié)點的next指針域的值,那么表示是空棧,根據(jù)空鏈隊列的結構,還需修改隊尾指針,使指向頭結點.
if(LQ->rear==frontNextNode){
LQ->rear=LQ->front;
}
//4.釋放刪除的結點
free(frontNextNode);
printf("out link queue success!\n");
return LQ;
}
/*
打印鏈表結點
*/
void printLinkQueue(LINKQUEUE *Q){
//實例化一個LQ,為了不改變原來鏈隊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.鏈頭指針向后移動
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[]) {})調用此方法,并且進行判斷
#include "QueueLinkControl.h"
int main(int argc, const char * argv[]) {
//創(chuàng)建鏈隊列
LINKQUEUE *LQ=(LINKQUEUE *)malloc(sizeof(LINKQUEUE));
LQ=initLinkQueue(LQ);
//向鏈隊插入結點
LQ=inLinkQueue(LQ,'a');
LQ=inLinkQueue(LQ,'b');
LQ=inLinkQueue(LQ,'c');
LQ=inLinkQueue(LQ,'d');
printLinkQueue(LQ);
//刪除結點--從隊頭
LQ=outLinkQueue(LQ);
LQ=outLinkQueue(LQ);
printLinkQueue(LQ);
return 0;
}
打印結果:
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
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
這篇文章主要為大家詳細介紹了C語言如何實現(xiàn)為無聲avi視頻添加wave音樂,文中的示例代碼講解詳細,具有一定的參考價值,感興趣的小伙伴可以了解一下2023-11-11
C++實現(xiàn)LeetCode(123.買股票的最佳時間之三)
這篇文章主要介紹了C++實現(xiàn)LeetCode(123.買股票的最佳時間之三),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-07-07
這篇文章主要為大家詳細介紹了C語言實現(xiàn)彈跳小球項目，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
這篇文章主要為大家詳細介紹了C++多線程實現(xiàn)電子詞典，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-03-03
這篇文章主要介紹了算法之排列算法與組合算法詳解,本文以字典序法、遞歸法為例講解了排列算法、全組合算法等,需要的朋友可以參考下2014-08-08
關于C/C++中的side effect(負效應)和sequence point(序列點)
不知你在寫code時是否遇到這樣的問題？int i = 3; int x = (++i) + (++i) + (++i); 問x值為多少？進行各種理論分析，并在編譯器上實踐，然而可能發(fā)現(xiàn)最終的結果是不正確的，也是不穩(wěn)定的，不同的編譯器可能會產(chǎn)生不同的結果。這讓人很頭疼2013-10-10
在C語言中，常量和變量都是可以用來存儲和表示數(shù)據(jù)的，常量值在程序執(zhí)行的過程中是不可變的，而變量是可變的2017-10-10
這篇文章主要介紹了C++中explict關鍵字用法的相關資料，本文介紹的非常詳細，具有參考借鑒價值，感興趣的朋友一起學習吧2016-05-05
本文主要介紹了?C語言取模取整的深入理解，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
OpenMP中For Construct對dynamic的調度方式詳解
在本篇文章當中主要給大家介紹 OpenMp for construct 的實現(xiàn)原理，與他相關的動態(tài)庫函數(shù)分析以及對 dynamic 的調度方式進行分析，希望對大家有所幫助2023-02-02