C語言資料結構之棧與佇列的相互實現

2022-07-05 10:00:02

一、用對列實現棧

題幹要求：

細節分析：佇列是先進先出；要實現的棧是先進後出。

解題思路：假設：先用一個佇列儲存資料 N 個，然後將前 N-1 個資料匯入到另一個佇列，

此時，原始佇列中僅剩一個，是最後剩的資料，便可將其匯出，這便是一次後進先出。

細節點：每次匯出資料時，都需要一個佇列向另一個佇列傳入資料，因此輸入佇列和輸出佇列需要輪換，要對其進行判定。

具體過程gif動態圖如下：

程式碼實現

1.初始化棧：先初始化兩個佇列

//棧的結構是由兩個佇列構成
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. 插入資料

因為儲存資料的佇列不是固定的，因此在一個佇列有資料的前提下，就繼續向該佇列插入資料，

空的佇列負責在匯出資料時進行輪轉。（哪個不空向哪個插入）

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

3.匯出資料（實現先進後出）

第一步：將有資料的佇列中除最後進的資料，依次匯入到另一個空佇列；

匯入空佇列，刪除原佇列，保留最後資料。

第二布：將原佇列中最後一個資料匯出。

注：這裡先假設了兩個佇列中，一個是原佇列和一個是空佇列，再進行判定，若與實際不符，則交換。

int myStackPop(MyStack* obj) {
    int temp = 0;
    //假設原佇列和空佇列
    Quetail* existque = &obj->q1,*nullque = &obj->q2;
    if((&obj->q1)->head == NULL)      //判斷與實際是否相符
    {
        existque = nullque;
        nullque = &obj->q1;
    } 
    for(;existque->head->Next;)       //保留最後一個資料
    {
        Que_push(nullque,existque->head->data);  //向空佇列匯入資料  
        Que_pop(existque);                       //刪除原佇列資料
    }
    temp = existque->head->data;      
    Que_pop(existque);                //匯出最後進的資料
    return temp;
}

4.查詢棧頂資料

找到不空的佇列 >> 返回其隊尾的資料

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

5.判斷棧是否為空：

判斷兩個佇列是否均為空

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

6.銷燬棧：

銷燬兩個佇列

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

二、用棧實現佇列

題幹要求：

細節分析：這次是用兩個棧，實現先進先出。

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

其次，資料正序入口棧，由於棧是先進後出，因此將資料再逆序進入出口棧，

然後，此時資料再出口棧中是逆序，所以，便可以正序從出口棧中依次排出。

程式碼實現

1.初始化雙棧佇列

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.插入資料

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

3.刪除資料（先進先出）

將入口棧資料記錄 >> 刪除入口棧資料 >> 匯入出口棧 >> 從出口棧匯出資料

int myQueuePop(MyQueue* obj) {
    if(Stack_Empty(&obj->T2))          //判斷是否為空
    {
        int k = 0;
        for(;!Stack_Empty(&obj->T1);)  
        {
            k = Stack_Top(&obj->T1);   //記錄入口站資料
            Stack_pop(&obj->T1);       //刪除入口棧資料
            Stack_push(&obj->T2,k);    //匯入出口棧
        }
    }
    int temp = 0;
    temp = Stack_Top(&obj->T2);        
    Stack_pop(&obj->T2);               //從出口棧匯出資料
    return temp;                       //題幹要求返回匯出的值
}

4.查詢佇列頭部資料

這裡的頭部資料是正序的頭資料，因此要先將入口棧中的逆序資料匯入出口棧，

變成正序，再返回出口棧的棧頂資料。

int myQueuePeek(MyQueue* obj) {
    if(Stack_Empty(&obj->T2))         //判斷出口棧中是否有資料
    {
        int k = 0;
        for(;!Stack_Empty(&obj->T1);) //向出口棧匯入資料
        {
            k = Stack_Top(&obj->T1);
            Stack_pop(&obj->T1);
            Stack_push(&obj->T2,k);
        }
    }
    return Stack_Top(&obj->T2);       //返回出口棧棧頂資料
}

5.判斷佇列是否為空及銷燬佇列

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

以上就是C語言資料結構之棧與佇列的相互實現的詳細內容，更多關於C語言棧佇列的資料請關注it145.com其它相關文章！

C語言資料結構之棧與佇列的相互實現

目錄

一、用對列實現棧

程式碼實現

二、用棧實現佇列

程式碼實現

熱門文章