C語言數(shù)據(jù)結(jié)構(gòu)之棧與隊(duì)列的相互實(shí)現(xiàn)

更新時(shí)間：2022年07月05日 08:46:02 作者：MT_125

這篇文章主要為大家詳細(xì)介紹了如何利用C語言相互實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的棧與隊(duì)列，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下

一、用對(duì)列實(shí)現(xiàn)棧

題干要求：

細(xì)節(jié)分析：隊(duì)列是先進(jìn)先出；要實(shí)現(xiàn)的棧是先進(jìn)后出。

解題思路：假設(shè)：先用一個(gè)隊(duì)列儲(chǔ)存數(shù)據(jù) N 個(gè)，然后將前 N-1 個(gè)數(shù)據(jù)導(dǎo)入到另一個(gè)隊(duì)列，

此時(shí)，原始隊(duì)列中僅剩一個(gè)，是最后剩的數(shù)據(jù)，便可將其導(dǎo)出，這便是一次后進(jìn)先出。

細(xì)節(jié)點(diǎn)：每次導(dǎo)出數(shù)據(jù)時(shí)，都需要一個(gè)隊(duì)列向另一個(gè)隊(duì)列傳入數(shù)據(jù)，因此輸入隊(duì)列和輸出隊(duì)列需要輪換，要對(duì)其進(jìn)行判定。

具體過程gif動(dòng)態(tài)圖如下：

代碼實(shí)現(xiàn)

1.初始化棧：先初始化兩個(gè)隊(duì)列

//棧的結(jié)構(gòu)是由兩個(gè)隊(duì)列構(gòu)成
typedef struct Nystack{
   Quetail q1;
   Quetail q2;
} MyStack;
 
//棧的初始化
MyStack* myStackCreate() {
   MyStack* Newstack = (MyStack*)malloc(sizeof(MyStack));
   Que_Init(&Newstack->q1);
   Que_Init(&Newstack->q2);
   return Newstack;
}

2. 插入數(shù)據(jù)

因?yàn)榇鎯?chǔ)數(shù)據(jù)的隊(duì)列不是固定的，因此在一個(gè)隊(duì)列有數(shù)據(jù)的前提下，就繼續(xù)向該隊(duì)列插入數(shù)據(jù)，

空的隊(duì)列負(fù)責(zé)在導(dǎo)出數(shù)據(jù)時(shí)進(jìn)行輪轉(zhuǎn)。（哪個(gè)不空向哪個(gè)插入）

//插入數(shù)據(jù)
void myStackPush(MyStack* obj, int x) {
     //if((&obj->q1)->head == NULL) //法一：直接判斷是否為空
     if(Que_Empty(&obj->q1))        //法二：后續(xù)函數(shù)的復(fù)用
     Que_push(&obj->q2,x);
     else
     Que_push(&obj->q1,x);
}

3.導(dǎo)出數(shù)據(jù)（實(shí)現(xiàn)先進(jìn)后出）

第一步：將有數(shù)據(jù)的隊(duì)列中除最后進(jìn)的數(shù)據(jù)，依次導(dǎo)入到另一個(gè)空隊(duì)列；

導(dǎo)入空隊(duì)列，刪除原隊(duì)列，保留最后數(shù)據(jù)。

第二布：將原隊(duì)列中最后一個(gè)數(shù)據(jù)導(dǎo)出。

注：這里先假設(shè)了兩個(gè)隊(duì)列中，一個(gè)是原隊(duì)列和一個(gè)是空隊(duì)列，再進(jìn)行判定，若與實(shí)際不符，則交換。

int myStackPop(MyStack* obj) {
    int temp = 0;
    //假設(shè)原隊(duì)列和空隊(duì)列
    Quetail* existque = &obj->q1,*nullque = &obj->q2;
    if((&obj->q1)->head == NULL)      //判斷與實(shí)際是否相符
    {
        existque = nullque;
        nullque = &obj->q1;
    } 
    for(;existque->head->Next;)       //保留最后一個(gè)數(shù)據(jù)
    {
        Que_push(nullque,existque->head->data);  //向空隊(duì)列導(dǎo)入數(shù)據(jù)  
        Que_pop(existque);                       //刪除原隊(duì)列數(shù)據(jù)
    }
    temp = existque->head->data;      
    Que_pop(existque);                //導(dǎo)出最后進(jìn)的數(shù)據(jù)
    return temp;
}

4.查找棧頂數(shù)據(jù)

找到不空的隊(duì)列 >> 返回其隊(duì)尾的數(shù)據(jù)

int myStackTop(MyStack* obj) {
    if((&obj->q1)->head == NULL)
    {
        return (&obj->q2)->tail->data;
    }
    return (&obj->q1)->tail->data;
}

5.判斷棧是否為空：

判斷兩個(gè)隊(duì)列是否均為空

bool myStackEmpty(MyStack* obj) {
    assert(obj);
    //法一：直接判斷
    //if((&obj->q1)->head == NULL&& (&obj->q2)->head == NULL)
    //法二：復(fù)用隊(duì)列判空函數(shù)
    if(Que_Empty(&(obj->q1))&&Que_Empty(&(obj->q2)))
    return true;
    return false;
}

6.銷毀棧：

銷毀兩個(gè)隊(duì)列

void myStackFree(MyStack* obj) {
     Que_Destory(&obj->q1);
     Que_Destory(&obj->q2);
     free(obj);
}

二、用棧實(shí)現(xiàn)隊(duì)列

題干要求：

細(xì)節(jié)分析：這次是用兩個(gè)棧，實(shí)現(xiàn)先進(jìn)先出。

解題思路：首先，將兩個(gè)棧分為入口棧和出口棧，

其次，數(shù)據(jù)正序入口棧，由于棧是先進(jìn)后出，因此將數(shù)據(jù)再逆序進(jìn)入出口棧，

然后，此時(shí)數(shù)據(jù)再出口棧中是逆序，所以，便可以正序從出口棧中依次排出。

代碼實(shí)現(xiàn)

1.初始化雙棧隊(duì)列

typedef struct {
    Stack T1;
    Stack T2;
} MyQueue;
 
 
MyQueue* myQueueCreate() {
      MyQueue *Q1;
      Q1 = (MyQueue*)malloc(sizeof(MyQueue));
      Stack_init(&(Q1->T1));      // T1 做入口棧
      Stack_init(&(Q1->T2));      // T2 做出口棧
      return Q1;
}

2.插入數(shù)據(jù)

void myQueuePush(MyQueue* obj, int x) {
     Stack_push(&obj->T1,x);          //這里將棧 T1 作為入口棧
}

3.刪除數(shù)據(jù)（先進(jìn)先出）

將入口棧數(shù)據(jù)記錄 >> 刪除入口棧數(shù)據(jù) >> 導(dǎo)入出口棧 >> 從出口棧導(dǎo)出數(shù)據(jù)

int myQueuePop(MyQueue* obj) {
    if(Stack_Empty(&obj->T2))          //判斷是否為空
    {
        int k = 0;
        for(;!Stack_Empty(&obj->T1);)  
        {
            k = Stack_Top(&obj->T1);   //記錄入口站數(shù)據(jù)
            Stack_pop(&obj->T1);       //刪除入口棧數(shù)據(jù)
            Stack_push(&obj->T2,k);    //導(dǎo)入出口棧
        }
    }
    int temp = 0;
    temp = Stack_Top(&obj->T2);        
    Stack_pop(&obj->T2);               //從出口棧導(dǎo)出數(shù)據(jù)
    return temp;                       //題干要求返回導(dǎo)出的值
}

4.查找隊(duì)列頭部數(shù)據(jù)

這里的頭部數(shù)據(jù)是正序的頭數(shù)據(jù)，因此要先將入口棧中的逆序數(shù)據(jù)導(dǎo)入出口棧，

變成正序，再返回出口棧的棧頂數(shù)據(jù) 。

int myQueuePeek(MyQueue* obj) {
    if(Stack_Empty(&obj->T2))         //判斷出口棧中是否有數(shù)據(jù)
    {
        int k = 0;
        for(;!Stack_Empty(&obj->T1);) //向出口棧導(dǎo)入數(shù)據(jù)
        {
            k = Stack_Top(&obj->T1);
            Stack_pop(&obj->T1);
            Stack_push(&obj->T2,k);
        }
    }
    return Stack_Top(&obj->T2);       //返回出口棧棧頂數(shù)據(jù)
}

5.判斷隊(duì)列是否為空及銷毀隊(duì)列

//判斷隊(duì)列是否為空
bool myQueueEmpty(MyQueue* obj) {
     //判斷兩個(gè)棧是否均為空
     return Stack_Empty(&obj->T1)&&Stack_Empty(&obj->T2);
}
 
//銷毀釋放隊(duì)列
void myQueueFree(MyQueue* obj) {
     Stack_pop(&obj->T1);
     Stack_pop(&obj->T2);
     free(obj);
}

以上就是C語言數(shù)據(jù)結(jié)構(gòu)之棧與隊(duì)列的相互實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于C語言棧隊(duì)列的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: