【Leetcode】队列实现栈和栈实现队列

 

  

目录

一.【Leetcode225】队列实现栈

1.链接

2.题目再现

 3.解法

二.【Leetcode232】栈实现队列

1.链接

2.题目再现

3.解法


一.【Leetcode225】队列实现栈

1.链接

队列实现栈

2.题目再现

 3.解法

这道题给了我们两个队列,要求去实现栈;

首先,我们要知道栈和队列的特征:

栈:后进先出,只能从栈顶入数据和出数据;

队列:先进先出,从队尾入数据,队头出数据;

根据这些特点,我们可以采用两边倒的方法来实现;

具体来说:

1.入栈时就是在不为空的队列插入数据,若两个队列都为空,就随便插入到一个队列中;

2.出栈时将不为空的队列的数据倒入为空的队列中,当不为空的队列就剩一个数据时,就停止向空队列倒数据,然后再删点那最后一个数据;

3.判空时,需要两个队列都为空,才算栈为空;

4.取栈顶元素即取不为空的队列的队尾元素,在取栈顶元素前要判断栈是否为空;

5.销毁栈时,要先销毁其中的两个队列,然后再销毁栈。

因为是用C语言实现的,所以得自己手搓个队列。

typedef int Qdatatype;

typedef struct QueueNode
{
	struct QueeuNode* next;
	Qdatatype data;
}QueueNode;

typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;
void Queueinit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}

void Queuedestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;

	while (cur != pq->tail)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->head = pq->tail = NULL;
}

void Queuepush(Queue* pq, Qdatatype x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

void Queuepop(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	QueueNode* next = pq->head->next;
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		free(pq->head);
		pq->head = next;
	}
}

Qdatatype Queuefront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->data;
}

Qdatatype Queueback(Queue* pq)
{
	assert(pq);
	assert(Queuesize(pq) > 0);

	return pq->tail->data;
}

int Queuesize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QueueNode* cur = pq->head;
	while (cur != pq->tail->next)
	{
		size++;
		cur = cur->next;
	}

	return size;
}

bool Queueempty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL;
}

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

MyStack* myStackCreate() {
    MyStack*obj=(MyStack*)malloc(sizeof(MyStack));
    if(obj==NULL)
        exit(-1);
    Queueinit(&obj->q1);
    Queueinit(&obj->q2);

    return obj;
}

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

int myStackPop(MyStack* obj) {
    Queue*empty=&obj->q1;
    Queue*noempty=&obj->q2;
    if(!Queueempty(&obj->q1))
    {
        empty=&obj->q2;
        noempty=&obj->q1;
    }
    while(Queuesize(noempty)>1)
    {
        Queuepush(empty,Queuefront(noempty));
        Queuepop(noempty);
    }
    int front=Queuefront(noempty);
    Queuepop(noempty);
    return front;
}

int myStackTop(MyStack* obj) {
    if(!Queueempty(&obj->q1))
    {
        return Queueback(&obj->q1);
    }
    else
    {
        return Queueback(&obj->q2);
    }
}
bool myStackEmpty(MyStack* obj) {
    
    return Queueempty(&obj->q1)&&Queueempty(&obj->q2);
}

void myStackFree(MyStack* obj) {

    Queuedestroy(&obj->q1);
    Queuedestroy(&obj->q2);

    free(obj);
}

二.【Leetcode232】栈实现队列

1.链接

栈实现队列

2.题目再现

3.解法

这个的解法和上面的类似,只不过这个不用总是来回倒;

根据栈和队列的特征,我们会发现将一个栈中的数据倒入另一个栈时,数据的顺序刚好符合队列的要求,不需要再重复地倒数据,所以我们可以让一个栈专门用来入数据(Pushst)一个栈专门用来出数据(Popst)当我们要出数据而这个栈为空时,我们才将用来入数据的栈中的数据倒入用来出数据的栈 。

如图:

1.判空时,需要两个栈都为空,队列才为空;

2.返回队头数据时,和出数据的操作类似,只是不需要删除队头的数据,还有在之前要判断队列是否为空;

3.销毁队列前,要先销毁两个栈。

同样,因为是C语言,得先手搓个栈。

#define MR_CAP 5
typedef int STdatatype;

typedef struct Stack
{
	STdatatype* arr;
	int top;
	int capacity;
}ST;

void Stackinit(ST* ps)
{
	assert(ps);

	ps->arr = (STdatatype*)malloc(MR_CAP * sizeof(STdatatype));
	if (ps->arr == NULL)
	{
		perror("Stackinit malloc");
		exit(-1);
	}

	ps->top = 0;
	ps->capacity = MR_CAP;
}

void Stackdestroy(ST* ps)
{
	assert(ps);

	free(ps->arr);
	ps->arr = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

void Stackpush(ST* ps, STdatatype x)
{
	assert(ps);

	if (ps->top == ps->capacity)
	{
		STdatatype* tmp = (STdatatype*)realloc(ps->arr, ps->capacity * 2 * sizeof(STdatatype));
		if (tmp == NULL)
		{
			perror("Stackpush realloc");
			exit(-1);
		}
		else
		{
			ps->arr = tmp;
			ps->capacity *= 2;
		}
	}

	ps->arr[ps->top] = x;
	ps->top++;
}

void Stackpop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);

	ps->top--;
}

STdatatype Stacktop(ST* ps)
{
	assert(ps);

	return ps->arr[ps->top - 1];
}

int Stacksize(ST* ps)
{
	assert(ps);

	return ps->top;

}

bool Stackempty(ST* ps)
{
	assert(ps);

	if (ps->top == 0)
	{
		return true;
	}
	else
		return false;
	 
}

typedef struct {
    ST Pushst;
    ST Popst;
} MyQueue;

MyQueue* myQueueCreate() {
    MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    if(obj==NULL)
        exit(-1);
    Stackinit(&obj->Pushst);
    Stackinit(&obj->Popst);

    return obj;
}

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

int myQueuePeek(MyQueue* obj) {
     if(Stackempty(&obj->Popst))
    {
        while(!Stackempty(&obj->Pushst))
        {
            Stackpush(&obj->Popst,Stacktop(&obj->Pushst));
            Stackpop(&obj->Pushst);
        }
    }

    return Stacktop(&obj->Popst);
    
}

int myQueuePop(MyQueue* obj) {
   
    int front=myQueuePeek(obj);
    Stackpop(&obj->Popst);
    return front;
}

bool myQueueEmpty(MyQueue* obj) {

    return Stackempty(&obj->Pushst)&&Stackempty(&obj->Popst);
}

void myQueueFree(MyQueue* obj) {
    Stackdestroy(&obj->Pushst);
    Stackdestroy(&obj->Popst);

    free(obj);
}

🐲👻这两道题的讲解就到这里了,若有错误或是建议欢迎小伙伴们指出。🐯🤖

🥰🤩希望小伙伴们可以多多支持博主哦。😍😃

😁😄谢谢你的阅读。😼😸

 

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码

)">
< <上一篇
下一篇>>