重慶分公司
重慶分公司，新征程啟航
為企業(yè)提供網(wǎng)站建設(shè)、域名注冊(cè)、服務(wù)器等服務(wù)
c++的棧和隊(duì)列怎么實(shí)現(xiàn)
這篇文章主要介紹“c++的棧和隊(duì)列怎么實(shí)現(xiàn)”，在日常操作中，相信很多人在c++的棧和隊(duì)列怎么實(shí)現(xiàn)問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”c++的棧和隊(duì)列怎么實(shí)現(xiàn)”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！
創(chuàng)新互聯(lián)公司是一家專業(yè)從事成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)的品牌網(wǎng)絡(luò)公司。如今是成都地區(qū)具影響力的網(wǎng)站設(shè)計(jì)公司,作為專業(yè)的成都網(wǎng)站建設(shè)公司,創(chuàng)新互聯(lián)公司依托強(qiáng)大的技術(shù)實(shí)力、以及多年的網(wǎng)站運(yùn)營(yíng)經(jīng)驗(yàn),為您提供專業(yè)的成都網(wǎng)站建設(shè)、營(yíng)銷(xiāo)型網(wǎng)站建設(shè)及網(wǎng)站設(shè)計(jì)開(kāi)發(fā)服務(wù)！
第一節(jié)：棧（Stack）
棧是限制在表一端進(jìn)行插入和刪除操作的線性表。允許進(jìn)行插入、刪除操作的這一端稱為棧頂（Top），另一個(gè)固定端稱為棧底。
例如棧中有三個(gè)元素，進(jìn)棧的順序是a1、a2、a3，當(dāng)需要出棧時(shí)順序?yàn)閍3,a2,a1, 所以棧又稱“后進(jìn)先出”或“先進(jìn)后出”的線性表，簡(jiǎn)稱“LIFO表”或“FILO表”。
1.1：棧的基本運(yùn)算：
（1）棧初始化：
Init_Stack(s)
(2）判?？眨?/p>
Empty_Stack(s)
(3）入棧：
Push_Stack(s,x)
(4）出棧：
Pop_Stack(s)
(5)讀棧頂元素：
Top_Stack(s)
1.2 棧的存儲(chǔ)結(jié)構(gòu)和基本運(yùn)算
由于棧是運(yùn)算受限的線性表(各個(gè)元素依次存放在一組地址連續(xù)的存儲(chǔ)單元中)，因此線性表的存儲(chǔ)結(jié)構(gòu)對(duì)棧也是適用的，只是操作不同而已。
（1）順序棧
利用順序存儲(chǔ)方式實(shí)現(xiàn)的棧稱為順序棧。類(lèi)似于順序表的定義，棧中的數(shù)據(jù)元素用一個(gè)預(yù)設(shè)的足夠長(zhǎng)度的一維數(shù)組來(lái)實(shí)現(xiàn)：datatype data[MAXSIZE]，棧底位置可以設(shè)置在數(shù)組的任意一個(gè)端點(diǎn)，而棧頂隨著插入和刪除而變化的，用int top來(lái)作為棧頂?shù)闹羔?，指明?dāng)前棧頂?shù)奈恢茫瑯訉ata和top封裝在一個(gè)結(jié)構(gòu)中，順序棧的類(lèi)型描述如下：
typedef struct{
datatype data[MAXSIZE];
int top;
}SeqStack定義一個(gè)指向順序棧的指針。
SeqStack *s;
通常將0下標(biāo)端設(shè)為棧底，這樣空棧時(shí)棧頂指標(biāo)top=-1；入棧時(shí)，棧頂指針加1，即s->top++；出棧時(shí)，棧頂指針減1，即s->top--。棧頂指針與棧中數(shù)據(jù)元素如下圖所示：
基本操作實(shí)現(xiàn)如下：
1）置空棧：首先建立棧空間，然后初始化棧頂指針。
SeqStack *Init_SeqStack()
{
SeqStack *s;
s=malloc(sizeof(SeqStack));
s->top = -1;
return s;
}2）判空棧：
int Empty_SeqStack(SeqStack *s){
if(s->top ==-1){
return 1;
}
else{
return 0;
}
}3）入棧：
int Push_SeqStack(SeqStack *s,datatype x){
if(s->top ==MAXSIZE-1){ //防止空間溢出——上溢
return 0;
}else{
s->top++;
s->data[s->top]=x;
return 1;
}
}4）出棧：
int Pop_SeqStack(SeqStack *s,datatype *x){
if(Empty_SeqStack)(s)){
return 0;
}
else{
*x =s ->data[s->top];
s->top--;
return 1;
}
}5)取棧頂元素：
datatype Top_SeqStack(SeqStack *s){
if(Empty_SeqStack(s)){
return 0;
}
else{
return (s->data[s->top]);
}
}（2）鏈棧
用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧稱為鏈棧。通過(guò)鏈棧用單鏈表表示，因此其結(jié)點(diǎn)結(jié)構(gòu)與單鏈表的結(jié)點(diǎn)結(jié)構(gòu)相同，在此用LinkStack表示：既有：
typedef struck node{
datatype data;
struct node *next;
}StackNode * LinkStack;基本操作如下：
1）置空棧：
LinkStack Init_LinkStack(){
return NULL；
}判?？?
int Empty_LinkStack(LinkStack top){
if(top==NULL)
return 1;
else
return 0;
}3)入棧：
LinkStack Push_LinkStack(LinkStack top , datatype x){
StackNode *s;
s = malloc(sizeof(StackNode));
s->data=x ;
s->next=top;
top=s;
return top;
}出棧：
LinkStack Pop_LinkStack(LinkStack top , datatype *x){
StackNode *p;
if(top ==NULL)
return NULL;
else
*x = top->data;
p =top;
top= top->next;
free(p);
return top;
}第二節(jié) ：隊(duì)列
2.1：定義及基本運(yùn)算
棧是講一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，而在實(shí)際問(wèn)題中還經(jīng)常使用一種“先進(jìn)先出”的數(shù)據(jù)結(jié)構(gòu)：即插入在表一端進(jìn)行，而刪除在表的另一端進(jìn)行，這叫數(shù)據(jù)結(jié)構(gòu)被稱為隊(duì)列（Queue [kju]）。允許插入的一端被稱為隊(duì)尾（rear）,允許刪除的一端成為隊(duì)頭（front）。如一個(gè)隊(duì)列入隊(duì)順序依次為：a1;a2;a3;a4;a5，出隊(duì)時(shí)順序?qū)⒁廊皇莂1;a2;a3;a4;a5。就像超市排隊(duì)的人結(jié)賬。
隊(duì)列也是一種運(yùn)算受限的線性表，又叫先進(jìn)先出表，簡(jiǎn)稱“FIFO表”。
基本操作：
（1）初始化：
Init_Queue(q)
(2）入隊(duì)操作：
In_Queue(q,x)
(3）出隊(duì)操作：
Out_Queue(q,x)
(4）讀隊(duì)頭元素：
Front_Queue(q,x)
(5）判隊(duì)空操作：
Empty_Queue（q）
2.2：隊(duì)列的存儲(chǔ)結(jié)構(gòu)和基本運(yùn)算
（1）順序隊(duì)
順序存儲(chǔ)的隊(duì)列稱為順序隊(duì)。因?yàn)殛?duì)列的隊(duì)頭和隊(duì)尾都是活動(dòng)的，因此，除了隊(duì)列的數(shù)據(jù)區(qū)外還有隊(duì)頭、隊(duì)尾兩個(gè)指針。順序隊(duì)定義如下：
define MAXSIZE 100;//容量
typedef stuct{
datatype data[MAXSIZE];//存儲(chǔ)空間
int rear,font;//隊(duì)尾指針
}SeQueue;
SeQueue *sq;//指針
sq = malloc（sizeof（SeQueue）)); //申請(qǐng)存儲(chǔ)空間
sq ->data[0]~ sq->data[MAXSIZE -1];; //存儲(chǔ)區(qū)
sq->front //隊(duì)頭
sq ->rear //隊(duì)尾
sq->front =sq->rear = -1 ; //置空
//sq->rear++;//順序隊(duì)
sq->rear = (sq->rear+1) % MAXSIZE;//循環(huán)隊(duì)
sq->data[sq->rear] =x; //入隊(duì)
//sq->front++;
sq->front = (sq ->front+1)%MAXSIZE;
x=sq->data[sq->front]; //出隊(duì)
m =(sq->rear) - (q->font);//隊(duì)長(zhǎng)1）置空隊(duì)：
c_SeQueue* Init_SeQueue(){
q =malloc(sizeof(c_SeQueue));
q ->font =q ->rear =-1;
q->num = 0;
return q;
}2)入隊(duì)：
int In_SeQueue(c_SeQueue *q , datatype x){
if(num == MAXSIZE){
return -1;
}
else{
q ->rear =(q ->rear+1)%MAXSIZE:
q ->data[q ->rear] = x;
num++;
return 1;
}
}3)出隊(duì)：
int Out_SeQueue(c_SeQueue *q , datatype *x){
if(num ==0){
return -1;
}
else{
q->fornt =(q->front+1)%MAXSIZE;
*x =q ->data[q->front];//讀出隊(duì)頭元素
num--;
return 1;
}
}4)判空：
int Empty_Sequeue(c_SeQueue *q){
if(num==0)
return 1;
else
return 0;
}(2) 鏈隊(duì)列
鏈?zhǔn)酱鎯?chǔ)的隊(duì)列稱為鏈隊(duì)列。和鏈棧類(lèi)似，鏈隊(duì)列可以用單鏈表來(lái)實(shí)現(xiàn)，根據(jù)隊(duì)的FIFO原則，為了操作上的方便，可以分別設(shè)置一個(gè)頭指針和一個(gè)尾指針。
鏈隊(duì)列定義如下：
typedef struct node{
datatype data;
struct node next;
}QNode;
typedef struct{
QNode *front , *rear;
}LQueue;
LQueue *q; //定義一個(gè)指向鏈隊(duì)列的指針1）創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的空隊(duì)：
LQueue *Init_LQueue(){
LQueue *q,*p;
q = malloc(sizeof(LQueue));//申請(qǐng)頭尾指針結(jié)點(diǎn)
p = malloc(sizeof(QNode)); //申請(qǐng)鏈隊(duì)頭結(jié)點(diǎn)
p->next = NULL;
q->front = p;
q->rear =p ;
return q;
}2)入隊(duì)：
void In_LQueue(LQueue *q , datatype x){
QNode *p;
p = malloc(sizeof (QNode));//申請(qǐng)新結(jié)點(diǎn)
p->data =x;
p->next =NULL;
q->rear ->next =p;
q->rear =p;
}3)判隊(duì)空：
int Empty_LQueue(LQueue *q){
if(q->front ==q->rear)
return 0;
else
return 1;
}4)出隊(duì)：
int Out_LQueue(LQueue *q , datatype *x){
QNode *p;
if(Empty_Lqueue(q)){
return 0;
}
else{
p=q->front->next;
q->front->next=p->next;
*x = p->data;//隊(duì)頭元素放x中
free(p);
if(q->front->next ==NULL){//只有一個(gè)元素時(shí)，出隊(duì)后隊(duì)空
q->rear = q->front;
return 1;
}
}到此，關(guān)于“c++的棧和隊(duì)列怎么實(shí)現(xiàn)”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！
文章標(biāo)題：c++的棧和隊(duì)列怎么實(shí)現(xiàn)
標(biāo)題網(wǎng)址：http://www.xueling.net.cn/article/pehjhd.html