【數(shù)據(jù)結(jié)構(gòu)經(jīng)典題目】—兩個隊列實現(xiàn)棧與兩個棧實現(xiàn)隊列

這篇具有很好參考價值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)經(jīng)典題目】—兩個隊列實現(xiàn)棧與兩個棧實現(xiàn)隊列。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

【數(shù)據(jù)結(jié)構(gòu)經(jīng)典題目】—兩個隊列實現(xiàn)棧與兩個棧實現(xiàn)隊列,數(shù)據(jù)結(jié)構(gòu)與算法煉體淬體中,數(shù)據(jù)結(jié)構(gòu),c語言

?????????????????????????????????????????食用指南：本文在有C基礎(chǔ)的情況下食用更佳??

??????????????????????????????????????????這就不得不推薦此專欄了：C語言

??????????????????????????????????????????本文前置知識：?C語言實現(xiàn)棧與隊列

??????????????????????????????????????????今日夜電波：怪獣の花唄—Vaundy

?????????????????????????????????????????3:12?━━━━━━???──────── 4:13? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?????????? ?? ? ?? ? ? ? ?? ? ??

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?????關(guān)注??點贊??收藏您的每一次鼓勵都是對我莫大的支持???

??兩個隊列實現(xiàn)棧

問題的描述以及要求

思路整理

具體的思路：

?每個操作的實現(xiàn)

?初始化

判空

入棧

?出棧

?取棧頂元素

?銷毀棧

??整體代碼

??兩個棧實現(xiàn)隊列

問題的描述以及要求

思路整理

具體的思路：??????????????

每個操作的實現(xiàn)?

?初始化

判空

入隊

出隊

?取隊頭元素

?銷毀隊列

??整體代碼

??兩個隊列實現(xiàn)棧

問題的描述以及要求

? ? ? ? 使用兩個隊列實現(xiàn)一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop?和?empty）。

思路整理

? ? ? ? 首先理清一點，隊列實現(xiàn)是先進先出，而棧是后進先出，我們需要使用兩個隊列來實現(xiàn)棧。對此，我的思路是一個隊列用于入棧用，而另外一個隊列用于出棧。對此，在這個基礎(chǔ)上設立了如下的結(jié)構(gòu)體：

typedef struct QNode//隊列節(jié)點
{
    int data;
    struct QNode* next;
}QNode;

typedef struct Queue//隊列
{
    QNode* front;
    QNode* tail;
}Queue;

typedef struct {
    QNode q1;
    QNode q2;
} MyStack;

具體的思路：

????????保持一個隊列在出棧前為空的狀態(tài)，而另外一個隊列則是出棧前一直用于入隊。然后，當程序需要出棧了，我們將不為空的那個隊列，也就是用于入隊的隊列的前N-1個數(shù)據(jù)出隊，將原本為空的那個隊列入隊這N-1個數(shù)據(jù)。在此之后，我們發(fā)現(xiàn)原本作為入隊的隊列僅僅剩下了最后一個數(shù)據(jù)，而原本為空的隊列擁有了N-1個數(shù)據(jù)，此時那剩下的一個數(shù)據(jù)不就是棧頂?shù)臄?shù)據(jù)嗎？我們只需要將這個數(shù)據(jù)進行出隊操作便可。而在這個數(shù)據(jù)出隊操作完成后，這個兩個隊列的性質(zhì)進行了交換，原本為空的隊列，現(xiàn)在擁有N-1個數(shù)據(jù)，原本不為空的隊列，現(xiàn)在為空了，因此，在接下來的操作需要轉(zhuǎn)換兩個隊列的入隊性質(zhì)。

????????一圖帶你了解~?

?每個操作的實現(xiàn)

?初始化

MyStack* myStackCreate() {
    MyStack* new=(MyStack*)malloc(sizeof(MyStack));
    if(new==NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    QueueInit(&new->q1);
    QueueInit(&new->q2);
    return new;
}

? ? ? ? 這里對于為什么對new->q1,new->q2取地址做出解釋：由于前面結(jié)構(gòu)體的定義為?QNode q1;QNode q2;而QueueInit內(nèi)傳參為指針所以取地址&。

判空

bool myStackEmpty(MyStack* obj) {
    assert(obj);
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

入棧

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }else
    {
        QueuePush(&obj->q2,x);
    }
}

? ? ? ? 入棧操作主要在于對于兩個隊列進行判斷，判斷出入上文思路所述，其中一個為空，以此，將空的隊列作為入棧操作。

?出棧

int myStackPop(MyStack* obj) {
    assert(obj);

    MyStack* empty=&obj->q1;
    MyStack* nonempty=&obj->q2;

    if(!QueueEmpty(empty))
    {
        empty=&obj->q2;
        nonempty=&obj->q1;
    }
    while(QueueSize(nonempty)>1)
    {
        QueuePush(empty,QueueTop(nonempty));
        QueuePop(nonempty);
    }
    int re=QueueTop(nonempty);
    QueuePop(nonempty);
    return re;
}

? ? ? ? 出棧操作是用兩個隊列實現(xiàn)棧的最關(guān)鍵的一步。首先創(chuàng)建兩個結(jié)構(gòu)體指針，一個用于存放空的隊列，另外一個存不為空的隊列。這時候有人就要問了，你怎么知道哪個是空的哪個不是空的。別急，這不有個if的判斷語句來判斷嗎？(*^▽^*)。接著，按照思路，將不為空的隊列N-1個數(shù)據(jù)入隊到原來為空的的隊列，最后再對剩下的一個數(shù)據(jù)進行出棧。

?取棧頂元素

int myStackTop(MyStack* obj) {
    assert(obj);
    assert(!myStackEmpty(obj));
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

? ? ? ? 這個簡單，只需要將不為空的隊列的最后一個元素給出去就好了！

?銷毀棧

void myStackFree(MyStack* obj) {
    assert(obj);
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
    obj=NULL;
}

??整體代碼

typedef struct QNode//隊列節(jié)點
{
    int data;
    struct QNode* next;
}QNode;
typedef struct Queue//隊列
{
    QNode* front;
    QNode* tail;
}Queue;
//初始化
void QueueInit(Queue* queue);
//隊列是否為空
bool QueueEmpty(Queue* queue);
//進隊
void QueuePush(Queue* queue, int x);
//出隊
void QueuePop(Queue* queue);
//隊列頭部元素
int QueueTop(Queue* queue);
//隊列尾部元素
int QueueBack(Queue* queue);
//隊列有效元素個數(shù)
int QueueSize(Queue* queue);
//銷毀隊列
void QueueDestroy(Queue* queue);

void QueueInit(Queue* queue)//初始化
{
    assert(queue);
    queue->front = NULL;
    queue->tail = NULL;
}
//隊列是否為空
bool QueueEmpty(Queue* queue)
{
    assert(queue);
    return queue->tail == NULL;
}
//進隊
void QueuePush(Queue* queue, int x)
{
    assert(queue);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    assert(newnode);
    newnode->data = x;
    newnode->next = NULL;
    if(queue->tail == NULL)
    {
        queue->front = queue->tail = newnode;
    }
    else
    {
        queue->tail->next = newnode;
        queue->tail = newnode;
    }
}
//出隊
void QueuePop(Queue* queue)
{
    assert(queue);
    QNode* next = queue->front->next;
    free(queue->front);
    queue->front = next;
    if(queue->front == NULL)
    {
        queue->tail = NULL;
    }
}
//隊列頭部元素
int QueueTop(Queue* queue)
{
    assert(queue);
    assert(queue->front);
    return queue->front->data;
}
//隊列尾部元素
int QueueBack(Queue* queue)
{
    assert(queue);
    assert(queue->tail);
    return queue->tail->data;
}
//隊列有效元素個數(shù)
int QueueSize(Queue* queue)
{
    assert(queue);
    int size = 0;
    QNode* cur = queue->front;
    while(cur != NULL)
    {
        ++size;
        cur = cur->next;
    }
    return size;
}
//銷毀隊列
void QueueDestroy(Queue* queue)
{
    assert(queue);
    QNode* next = queue->front;
    while(next != NULL)
    {
        next = queue->front->next;
        free(queue->front);
        queue->front = next;
    }
    queue->tail = NULL;
}


typedef struct {
    QNode q1;
    QNode q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* new=(MyStack*)malloc(sizeof(MyStack));
    if(new==NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    QueueInit(&new->q1);
    QueueInit(&new->q2);
    return new;
}

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }else
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    assert(obj);
    MyStack* empty=&obj->q1;
    MyStack* nonempty=&obj->q2;
    if(!QueueEmpty(empty))
    {
        empty=&obj->q2;
        nonempty=&obj->q1;
    }
    while(QueueSize(nonempty)>1)
    {
        QueuePush(empty,QueueTop(nonempty));
        QueuePop(nonempty);
    }
    int re=QueueTop(nonempty);
    QueuePop(nonempty);
    return re;
}  

bool myStackEmpty(MyStack* obj);

int myStackTop(MyStack* obj) {
    assert(obj);
    assert(!myStackEmpty(obj));
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

bool myStackEmpty(MyStack* obj) {
    assert(obj);
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    assert(obj);
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
    obj=NULL;
}

??兩個棧實現(xiàn)隊列

問題的描述以及要求

????????僅使用兩個棧實現(xiàn)先入先出隊列。隊列應當支持一般隊列支持的所有操作（push、pop、peek、empty）。

思路整理

????????首先理清一點，棧實現(xiàn)是后進先出，而隊列是先進先出，我們需要使用兩個棧來實現(xiàn)隊列。對此，我的思路是一個棧用于入隊用，而另外一個棧用于出隊。對此，在這個基礎(chǔ)上設立了如下的結(jié)構(gòu)體：

typedef int STDataType;
typedef struct Stack//變長的數(shù)組棧
{
	STDataType* a;
	int top;
	int capacity;
}SLtack;

typedef struct {
    SLtack push;
    SLtack pop;
} MyQueue;

具體的思路：??????????????

?????????將一個棧當作輸入棧，用于壓入push 傳入的數(shù)據(jù)；另一個棧當作輸出棧，用于 pop操作。每次 pop?時，若輸出棧為空則將輸入棧的全部數(shù)據(jù)依次彈出并壓入輸出棧，這樣輸出棧從棧頂往棧底的順序就是隊列從隊首往隊尾的順序。若不為空，則只有將所有輸出棧的數(shù)據(jù)都pop完后，才將輸入棧的數(shù)據(jù)彈入輸出棧。再對輸出棧進行pop操作。

????????一圖讓你了然~

? 【數(shù)據(jù)結(jié)構(gòu)經(jīng)典題目】—兩個隊列實現(xiàn)棧與兩個棧實現(xiàn)隊列,數(shù)據(jù)結(jié)構(gòu)與算法煉體淬體中,數(shù)據(jù)結(jié)構(gòu),c語言

每個操作的實現(xiàn)?

?初始化

MyQueue* myQueueCreate() {
    MyQueue* new=(MyQueue*)malloc(sizeof(MyQueue));
    if(new==NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    StackInit(&new->push);
    StackInit(&new->pop);
    return new;
}

? ? ? ? 這里對于為什么對new->push,new->pop取地址做出解釋：由于前面結(jié)構(gòu)體的定義為SLtack push;SLtack pop;而StackInit內(nèi)傳參為指針所以取地址&。

判空

bool myQueueEmpty(MyQueue* obj) {

    return StackEmpty(&obj->push)&&StackEmpty(&obj->pop);
}

入隊

void myQueuePush(MyQueue* obj, int x) {
    
    StackPush(&obj->push,x);
}

? ? ? ? 入隊操作只需要對push棧進行入棧操作即可

出隊

int myQueuePop(MyQueue* obj) {

    assert(obj);
    assert(!myQueueEmpty(obj));
    if(StackEmpty(&obj->pop))
    {
        while(!StackEmpty(&obj->push))
        {
            StackPush(&obj->pop,StackTop(&obj->push));
            StackPop(&obj->push);
        }
    }
    int re=StackTop(&obj->pop);
    StackPop(&obj->pop);
    return re;
}

????????出隊操作是實現(xiàn)兩個棧實現(xiàn)隊列的關(guān)鍵。需要將push棧中的數(shù)據(jù)全都壓棧道pop棧，注意只有pop為空時才進行以上操作。然后就是對于pop棧進行正常的出棧操作即可。

?取隊頭元素

int myQueuePeek(MyQueue* obj) {
    assert(obj);
    assert(!myQueueEmpty(obj));
    if(StackEmpty(&obj->pop))
    {
        while(!StackEmpty(&obj->push))
        {
            StackPush(&obj->pop,StackTop(&obj->push));
            StackPop(&obj->push);
        }
    }
    return StackTop(&obj->pop);
}

? ? ? ? 這里主要還是同出隊操作差不多，取隊頭的元素需要在pop棧上的top?。?/p>

?銷毀隊列

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->push);
    StackDestroy(&obj->pop);
    free(obj);
    obj==NULL;
}

??整體代碼

typedef int STDataType;
typedef struct Stack//變長的數(shù)組棧
{
	STDataType* a;
	int top;
	int capacity;
}SLtack;

// 初始化棧 
void StackInit(SLtack* ps);
// 入棧 
void StackPush(SLtack* ps, STDataType data);
// 出棧 
void StackPop(SLtack* ps);
// 獲取棧頂元素 
STDataType StackTop(SLtack* ps);
// 獲取棧中有效元素個數(shù) 
int StackSize(SLtack* ps);
// 檢測棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0 
int StackEmpty(SLtack* ps);
// 銷毀棧 
void StackDestroy(SLtack* ps);

void StackInit(SLtack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;//top初始化為0，則top指向棧頂?shù)南乱粋€元素
}

void StackPush(SLtack* ps, STDataType data)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		ps->capacity =ps->capacity== 0 ? 4 : ps->capacity * 2;
		ps->a = (STDataType*)realloc(ps->a, sizeof(int) * ps->capacity);
	}
	ps->a[ps->top] = data;
	ps->top++;
}

void StackPop(SLtack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

STDataType StackTop(SLtack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

int StackSize(SLtack* ps)
{
	assert(ps);
	return ps->top;
}

int StackEmpty(SLtack* ps)
{
	assert(ps);
	return ps->top == 0;
}

void StackDestroy(SLtack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

typedef struct {
    SLtack push;
    SLtack pop;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* new=(MyQueue*)malloc(sizeof(MyQueue));
    if(new==NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    StackInit(&new->push);
    StackInit(&new->pop);
    return new;
}

void myQueuePush(MyQueue* obj, int x) {
    
    StackPush(&obj->push,x);
}

bool myQueueEmpty(MyQueue* obj);

int myQueuePop(MyQueue* obj) {

    assert(obj);
    assert(!myQueueEmpty(obj));
    if(StackEmpty(&obj->pop))
    {
        while(!StackEmpty(&obj->push))
        {
            StackPush(&obj->pop,StackTop(&obj->push));
            StackPop(&obj->push);
        }
    }
    int re=StackTop(&obj->pop);
    StackPop(&obj->pop);
    return re;
}

int myQueuePeek(MyQueue* obj) {
    assert(obj);
    assert(!myQueueEmpty(obj));
    if(StackEmpty(&obj->pop))
    {
        while(!StackEmpty(&obj->push))
        {
            StackPush(&obj->pop,StackTop(&obj->push));
            StackPop(&obj->push);
        }
    }
    return StackTop(&obj->pop);
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->push)&&StackEmpty(&obj->pop);
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->push);
    StackDestroy(&obj->pop);
    free(obj);
    obj==NULL;
}

?????????????????感謝你耐心的看到這里?( ′???` )比心，如有哪里有錯誤請?zhí)咭荒_作者o(╥﹏╥)o！?

??????????????????????????????????????????????? 【數(shù)據(jù)結(jié)構(gòu)經(jīng)典題目】—兩個隊列實現(xiàn)棧與兩個棧實現(xiàn)隊列,數(shù)據(jù)結(jié)構(gòu)與算法煉體淬體中,數(shù)據(jù)結(jié)構(gòu),c語言

????????????????????????????????????????????????????????????????????????????????給個三連再走嘛~???文章來源地址http://www.zghlxwxcb.cn/news/detail-636911.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)經(jīng)典題目】—兩個隊列實現(xiàn)棧與兩個棧實現(xiàn)隊列的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！