c++的棧和隊列怎么實現

這篇文章主要介紹“c++的棧和隊列怎么實現”，在日常操作中，相信很多人在c++的棧和隊列怎么實現問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”c++的棧和隊列怎么實現”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

第一節：棧（Stack）

棧是限制在表一端進行插入和刪除操作的線性表。允許進行插入、刪除操作的這一端稱為棧頂（Top），另一個固定端稱為棧底。

例如棧中有三個元素，進棧的順序是a1、a2、a3，當需要出棧時順序為a3,a2,a1, 所以棧又稱“后進先出”或“先進后出”的線性表，簡稱“LIFO表”或“FILO表”。

1.1：棧的基本運算：

（1）棧初始化：

Init_Stack(s)

(2）判棧空：

Empty_Stack(s)

(3）入棧：

Push_Stack(s,x)

(4）出棧：

Pop_Stack(s)

(5)讀棧頂元素：

Top_Stack(s)

1.2 棧的存儲結構和基本運算

由于棧是運算受限的線性表(各個元素依次存放在一組地址連續的存儲單元中)，因此線性表的存儲結構對棧也是適用的，只是操作不同而已。

（1）順序棧

利用順序存儲方式實現的棧稱為順序棧。類似于順序表的定義，棧中的數據元素用一個預設的足夠長度的一維數組來實現：datatype data[MAXSIZE]，棧底位置可以設置在數組的任意一個端點，而棧頂隨著插入和刪除而變化的，用int top來作為棧頂的指針，指明當前棧頂的位置，同樣將data和top封裝在一個結構中，順序棧的類型描述如下：

typedef struct{
    datatype data[MAXSIZE];
    int top;
}SeqStack

定義一個指向順序棧的指針。

SeqStack *s;

通常將0下標端設為棧底，這樣空棧時棧頂指標top=-1；入棧時，棧頂指針加1，即s->top++；出棧時，棧頂指針減1，即s->top--。棧頂指針與棧中數據元素如下圖所示：

基本操作實現如下：

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）鏈棧

用鏈式存儲結構實現的棧稱為鏈棧。通過鏈棧用單鏈表表示，因此其結點結構與單鏈表的結點結構相同，在此用LinkStack表示：既有：

typedef struck node{
    datatype data;
    struct node *next;
}StackNode * LinkStack;

基本操作如下：

1）置空棧：

LinkStack Init_LinkStack(){
    return NULL；
}

1. 判棧空:

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;
}

1. 出棧：

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;
 }

第二節 ：隊列

2.1：定義及基本運算

棧是講一種先進后出的數據結構，而在實際問題中還經常使用一種“先進先出”的數據結構：即插入在表一端進行，而刪除在表的另一端進行，這叫數據結構被稱為隊列（Queue [kju]）。允許插入的一端被稱為隊尾（rear）,允許刪除的一端成為隊頭（front）。如一個隊列入隊順序依次為：a1;a2;a3;a4;a5，出隊時順序將依然是a1;a2;a3;a4;a5。就像超市排隊的人結賬。

隊列也是一種運算受限的線性表，又叫先進先出表，簡稱“FIFO表”。

基本操作：

（1）初始化：

Init_Queue(q)

(2）入隊操作：

In_Queue(q,x)

(3）出隊操作：

Out_Queue(q,x)

(4）讀隊頭元素：

Front_Queue(q,x)

(5）判隊空操作：

Empty_Queue（q）

2.2：隊列的存儲結構和基本運算

（1）順序隊

順序存儲的隊列稱為順序隊。因為隊列的隊頭和隊尾都是活動的，因此，除了隊列的數據區外還有隊頭、隊尾兩個指針。順序隊定義如下：

define MAXSIZE 100;//容量
typedef stuct{
    datatype data[MAXSIZE];//存儲空間
    int rear,font;//隊尾指針
}SeQueue;
 
SeQueue *sq;//指針
 
sq = malloc（sizeof（SeQueue）)); //申請存儲空間
 
sq ->data[0]~ sq->data[MAXSIZE -1];; //存儲區
 
sq->front //隊頭
 
sq ->rear //隊尾
 
sq->front =sq->rear = -1 ; //置空
 
//sq->rear++;//順序隊
sq->rear = (sq->rear+1) % MAXSIZE;//循環隊
sq->data[sq->rear] =x; //入隊
 
//sq->front++;
sq->front = (sq ->front+1)%MAXSIZE;
x=sq->data[sq->front]; //出隊
 
m =(sq->rear) - (q->font);//隊長

1）置空隊：

c_SeQueue* Init_SeQueue(){
    q =malloc(sizeof(c_SeQueue));
    q ->font =q ->rear =-1;
    q->num = 0;
    return q;
}

2)入隊：

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)出隊：

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];//讀出隊頭元素
        num--;
        return 1;
    }
}

4)判空：

int Empty_Sequeue(c_SeQueue *q){
    if(num==0) 
        return 1;
    else
        return 0;
}

(2) 鏈隊列

鏈式存儲的隊列稱為鏈隊列。和鏈棧類似，鏈隊列可以用單鏈表來實現，根據隊的FIFO原則，為了操作上的方便，可以分別設置一個頭指針和一個尾指針。

鏈隊列定義如下：

typedef struct node{
    datatype data;
    struct node next;
}QNode;
 
typedef struct{
    QNode *front , *rear;
}LQueue;
 
LQueue *q; //定義一個指向鏈隊列的指針

1）創建一個帶頭結點的空隊：

LQueue *Init_LQueue(){
    LQueue *q,*p;
    q = malloc(sizeof(LQueue));//申請頭尾指針結點
    p = malloc(sizeof(QNode)); //申請鏈隊頭結點
    p->next = NULL;
    q->front = p;
    q->rear =p ;
    return q;
}

2)入隊：

void In_LQueue(LQueue *q , datatype x){
    QNode *p;
    p = malloc(sizeof (QNode));//申請新結點
    p->data =x;
    p->next =NULL;
    q->rear ->next =p;
    q->rear =p;
}

3)判隊空：

int Empty_LQueue(LQueue *q){
    if(q->front ==q->rear)
        return 0;
    else
        return 1;
 }

4)出隊：

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;//隊頭元素放x中
        free(p);
        if(q->front->next ==NULL){//只有一個元素時，出隊后隊空
            q->rear = q->front;
            return 1;
        }
}

到此，關于“c++的棧和隊列怎么實現”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！