【数据结构经典题目】—两个队列实现栈与两个栈实现队列-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构经典题目】—两个队列实现栈与两个栈实现队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【数据结构经典题目】—两个队列实现栈与两个栈实现队列,数据结构与算法炼体淬体中,数据结构,c语言

食用指南：本文在有C基础的情况下食用更佳

🔥这就不得不推荐此专栏了：C语言

🍀本文前置知识： C语言实现栈与队列

♈️今日夜电波：怪獣の花唄—Vaundy

3:12 ━━━━━━️💟──────── 4:13 🔄 ◀️ ⏸ ▶️ ☰

💗关注👍点赞🙌收藏您的每一次鼓励都是对我莫大的支持😍

🍂两个队列实现栈

问题的描述以及要求

思路整理

具体的思路：

每个操作的实现

初始化

判空

入栈

出栈

取栈顶元素

销毁栈

🍁整体代码

🍃两个栈实现队列

问题的描述以及要求

思路整理

具体的思路：

每个操作的实现

初始化

判空

入队

出队

取队头元素

销毁队列

🌿整体代码

🍂两个队列实现栈

问题的描述以及要求

使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

思路整理

首先理清一点，队列实现是先进先出，而栈是后进先出，我们需要使用两个队列来实现栈。对此，我的思路是一个队列用于入栈用，而另外一个队列用于出栈。对此，在这个基础上设立了如下的结构体：

typedef struct QNode//队列节点
{
    int data;
    struct QNode* next;
}QNode;

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

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

具体的思路：

保持一个队列在出栈前为空的状态，而另外一个队列则是出栈前一直用于入队。然后，当程序需要出栈了，我们将不为空的那个队列，也就是用于入队的队列的前N-1个数据出队，将原本为空的那个队列入队这N-1个数据。在此之后，我们发现原本作为入队的队列仅仅剩下了最后一个数据，而原本为空的队列拥有了N-1个数据，此时那剩下的一个数据不就是栈顶的数据吗？我们只需要将这个数据进行出队操作便可。而在这个数据出队操作完成后，这个两个队列的性质进行了交换，原本为空的队列，现在拥有N-1个数据，原本不为空的队列，现在为空了，因此，在接下来的操作需要转换两个队列的入队性质。

一图带你了解~

【数据结构经典题目】—两个队列实现栈与两个栈实现队列,数据结构与算法炼体淬体中,数据结构,c语言

每个操作的实现

初始化

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取地址做出解释：由于前面结构体的定义为 QNode q1;QNode q2;而QueueInit内传参为指针所以取地址&。

判空

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

出栈操作是用两个队列实现栈的最关键的一步。首先创建两个结构体指针，一个用于存放空的队列，另外一个存不为空的队列。这时候有人就要问了，你怎么知道哪个是空的哪个不是空的。别急，这不有个if的判断语句来判断吗？(*^▽^*)。接着，按照思路，将不为空的队列N-1个数据入队到原来为空的的队列，最后再对剩下的一个数据进行出栈。

取栈顶元素

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//队列节点
{
    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);
//队列有效元素个数
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;
}
//队列有效元素个数
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;
}

🍃两个栈实现队列

问题的描述以及要求

仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。

思路整理

首先理清一点，栈实现是后进先出，而队列是先进先出，我们需要使用两个栈来实现队列。对此，我的思路是一个栈用于入队用，而另外一个栈用于出队。对此，在这个基础上设立了如下的结构体：

typedef int STDataType;
typedef struct Stack//变长的数组栈
{
	STDataType* a;
	int top;
	int capacity;
}SLtack;

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

具体的思路：

将一个栈当作输入栈，用于压入push 传入的数据；另一个栈当作输出栈，用于 pop操作。每次 pop 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。若不为空，则只有将所有输出栈的数据都pop完后，才将输入栈的数据弹入输出栈。再对输出栈进行pop操作。

一图让你了然~

【数据结构经典题目】—两个队列实现栈与两个栈实现队列,数据结构与算法炼体淬体中,数据结构,c语言

每个操作的实现

初始化

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取地址做出解释：由于前面结构体的定义为SLtack push;SLtack pop;而StackInit内传参为指针所以取地址&。

判空

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

出队操作是实现两个栈实现队列的关键。需要将push栈中的数据全都压栈道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取！

销毁队列

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

🌿整体代码

typedef int STDataType;
typedef struct Stack//变长的数组栈
{
	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);
// 获取栈中有效元素个数 
int StackSize(SLtack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回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指向栈顶的下一个元素
}

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

感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！

【数据结构经典题目】—两个队列实现栈与两个栈实现队列,数据结构与算法炼体淬体中,数据结构,c语言