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

aosei

发布于 2024-01-23 14:05:20

790

发布于 2024-01-23 14:05:20

文章被收录于专栏：csdn-nagiYcsdn-nagiY

一.【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);
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-01-23，如有侵权请联系 cloudcommunity@tencent.com 删除

assert