C語言數(shù)據(jù)結(jié)構(gòu)之棧與隊(duì)列的相互實(shí)現(xiàn)
一、用對(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ì)列的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
類模版std::function是一種通用的多態(tài)函數(shù)包裝器std::function的實(shí)例可以對(duì)任何可以調(diào)用的目標(biāo)實(shí)體進(jìn)行存儲(chǔ)、復(fù)制、和調(diào)用操作，本文詳細(xì)的介紹一下，感興趣的可以了解一下2021-06-06
這篇文章主要介紹了VS2019中QT連接及使用的方法步驟，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08
C++服務(wù)器和客戶端交互的項(xiàng)目實(shí)踐
本文主要介紹了C++服務(wù)器和客戶端交互的項(xiàng)目實(shí)踐，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
本篇文章是對(duì)最長(zhǎng)公共子字符串的使用進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了c++中的std::move函數(shù),在探討c++11中的Move函數(shù)前，先介紹兩個(gè)概念（左值和右值），對(duì)c++?std::move函數(shù)相關(guān)知識(shí)感興趣的朋友一起看看吧2022-07-07
C++獲取特定進(jìn)程CPU使用率的實(shí)現(xiàn)代碼
寫一個(gè)小程序在后臺(tái)記錄每個(gè)進(jìn)程的CPU使用情況，揪出鎖屏后占用CPU的進(jìn)程，于是自己寫了一個(gè)C++類CPUusage，方便地監(jiān)視不同進(jìn)程的CPU占用情況。本人編程還只是個(gè)新手，如有問題請(qǐng)多多指教2019-04-04
這篇文章主要給大家介紹了關(guān)于C語言二叉樹與堆的相關(guān)資料,文章詳細(xì)記錄了他們的相關(guān)概念以及如何實(shí)現(xiàn)的,通過圖文介紹的非常詳細(xì),需要的朋友可以參考下2021-06-06
push與push_back是STL中常見的方法，都是向數(shù)據(jù)結(jié)構(gòu)中添加元素，本文還將簡(jiǎn)述push對(duì)應(yīng)的stack與queue系列，常見方法的介紹，以及與push_back相對(duì)應(yīng)的vector系列常見方法介紹，感興趣的朋友跟隨小編一起看看吧2022-11-11
C++實(shí)現(xiàn)循環(huán)隊(duì)列
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)循環(huán)隊(duì)列，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-01-01
這篇文章主要介紹了C++中友元的實(shí)例詳解的相關(guān)資料,希望通過本文大家能掌握友元的使用方法，需要的朋友可以參考下2017-09-09