leetcode 栈和队列的互相实现

1. 用队列实现栈
- 1.1 题目描述
- 1.1.1 接口函数
- 1.2 大致框架
- - 1.2.1 想法和思路
  - 1.2.2 具体步骤
  - - 先实现一个栈
    - `MyStack`
    - `myStackCreate`
    - `myStackPush`
    - `myStackPop`
    - `myStackTop`
    - `myStackEmpty`
    - `myStackFree`
  - 1.2.3 测试时发生的错误
  - - 解决第一个错误
    - 解决第二个错误
    - 解决第三个错误
- 1.3 整体实现
2. 用栈实现队列
- 2.1 题目描述
- - 2.1.1 接口函数
- 2.2 大致框架
- - 2.2.1 想法和思路
  - 2.2.2 具体步骤
  - - 先实现一个栈
    - `myQueueCreate`
    - `myQueuePush`
    - `myQueuePop`
    - `myQueuePeek`
    - `myQueueEmpty`
    - `myQueueFree`
- 2.3 整体实现

1. 用队列实现栈

本题目来源于leetcode225. 用队列实现栈

1.1 题目描述

示例

注意和提示

1.1.1 接口函数

typedef struct {

} MyStack;


MyStack* myStackCreate() {

}

void myStackPush(MyStack* obj, int x) {

}

int myStackPop(MyStack* obj) {

}

int myStackTop(MyStack* obj) {

}

bool myStackEmpty(MyStack* obj) {

}

void myStackFree(MyStack* obj) {

}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/

1.2 大致框架

注意要实现功能，利用先进先出的队列达成后进先出的栈

这里还是同样的，用c语言的话肯定是要先实现一下队列

1.2.1 想法和思路

这两个队列，保证在插入数据的时候，往不为空的那个队列插入，保持另一个队列是空的，出队列的时候，使前size-1个导入空队列，删除最后一个

1.2.2 具体步骤

先实现一个栈

#include <stdbool.h>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;

}QueueNode;

typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;

void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		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)
	{
		printf("malloc fail\n");
		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(!QueueEmpty(pq));//空
	if (pq->head->next == NULL)//一个节点的时候要特殊考虑
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data; 
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL && pq->tail==NULL;
}
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

然后处理实现栈过程

`MyStack`

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

`myStackCreate`

MyStack* myStackCreate() {
    MyStack*pst=(MyStack*)malloc(sizeof(MyStack));
    QueueInit1(&pst->q1); 
    QueueInit2(&pst->q2);
    return pst;
}

`myStackPush`

往不为空的队列里面入数据

void myStackPush(MyStack* obj, int x) {
 if(！QueueEmpty(&obj->q1))//谁空放哪里
 {
     QueuePush(&obj->q1,x);
 }
 else
 {
     QueuePush(&obj->q2,x);
 }
}

`myStackPop`

后入的先出，所以，想法是把数据按照队列的方式先出，出到另外一个队列里面

如图，假如数据进入的顺序是1，2，3，4

先把123放到另外一个队列之中，然后把4用队列的删除pop掉就可以了

int myStackPop(MyStack* obj) {
    Queue*pEmpty=&obj->q1;
    Queue*pNonEmpty=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        pNonEmpty=&obj->q1;
        pEmpty=&obj->q2;
    }
    while(QueueSize(pNonEmpty)>1)
    {//取一个插一个删一个，取一个插一个删一个
        QueuePush(pEmpty,QueueFront(pNonEmpty));
        QueuePop(pNonEmpty);
    }
    //最后一个干掉
    int front=QueueFront(pNonEmpty);
    QueuePop(pNonEmpty);
    return front;
}

`myStackTop`

int myStackTop(MyStack* obj) {
if(！QueueEmpty(&obj->q1))
 {//队尾的数据就是栈顶
     return QueueBack(&obj->q1);
 }
 else
 {
    return QueueBack(&obj->q2);
 }
}

`myStackEmpty`

都是空的才说明是空的

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

`myStackFree`

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

1.2.3 测试时发生的错误

解决第一个错误

显然是一个测试用例都没有通过

int myStackTop(MyStack* obj) {
if(QueueEmpty(&obj->q1))//检查了一遍发现缺了感叹号，也就是Top，那如果没有！就返回了空队列肯定不对
 {//队尾的数据就是栈顶
     return QueueBack(&obj->q1);
 }
 else
 {
    return QueueBack(&obj->q2);
 }
}

但是显然这不会使得超出时间限制，所以继续检查

解决第二个错误

void myStackPush(MyStack* obj, int x) {
 if(QueueEmpty(&obj->q1))//谁空放哪里
 {
     QueuePush(&obj->q1,x);
 }
 else
 {
     QueuePush(&obj->q2,x);
 }
}

很尴尬😅这里也忘了，一样的问题

但是还没完

解决第三个错误

既然都不是那一定是队列写错了

然后一找发现bug后直接吐血😭

为什么会在while（cur）后面加一个；

怪不得程序停不下来

int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QueueNode* cur = pq->head;
	while (cur)；
	{
		++size;
		cur = cur->next;
	}
	return size;
}

总算解决了心，队列要好好写啊

1.3 整体实现

#include <stdbool.h>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;

}QueueNode;

typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;

void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
void QueueDestroy(Queue* pq)
{
	assert(pq);

	QueueNode* cur = pq->head;
	while (cur)
	{
		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)
	{
		printf("malloc fail\n");
		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(!QueueEmpty(pq));//空
	if (pq->head->next == NULL)//一个节点的时候要特殊考虑
	{
		free(pq->head);
		pq->head  = pq->tail = NULL;
	}
	else
	{
		QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data; 
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head ==  NULL && pq->tail==NULL;
}
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

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


MyStack* myStackCreate() {
    MyStack*pst=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1); 
    QueueInit(&pst->q2);
    return pst;
}

void myStackPush(MyStack* obj, int x) {
 if(!QueueEmpty(&obj->q1))//谁空放哪里
 {
     QueuePush(&obj->q1,x);
 }
 else
 {
     QueuePush(&obj->q2,x);
 }
}

int myStackPop(MyStack* obj) {
    Queue*pEmpty=&obj->q1;
    Queue*pNonEmpty=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        pNonEmpty=&obj->q1;
        pEmpty=&obj->q2;
    }
    while(QueueSize(pNonEmpty)>1)
    {//取一个插一个删一个，取一个插一个删一个
        QueuePush(pEmpty,QueueFront(pNonEmpty));
        QueuePop(pNonEmpty);
    }
    //最后一个干掉
    int front=QueueFront(pNonEmpty);
    QueuePop(pNonEmpty);
    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);
}

2. 用栈实现队列

本题目来源于leetcode 232. 用栈实现队列

2.1 题目描述

实例和提示

2.1.1 接口函数

typedef struct {

} MyQueue;


MyQueue* myQueueCreate() {

}

void myQueuePush(MyQueue* obj, int x) {

}

int myQueuePop(MyQueue* obj) {

}

int myQueuePeek(MyQueue* obj) {

}

bool myQueueEmpty(MyQueue* obj) {

}

void myQueueFree(MyQueue* obj) {

}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

2.2 大致框架

注意要实现功能，利用后进先出的栈达成先进先出的队列

这里还是同样的，用c语言的话肯定是要先实现一下栈

2.2.1 想法和思路

假如我们按12345的顺序放入栈中

效仿之前的一道题目，我们先按栈的性质，后进先出，尝试进到空栈的栈底

此时发现想要出栈恰好变成了12345的顺序出栈，那么就是队列的功能，恰巧实现，只需要换一次位置即可

假如继续存入新数据也是，先把右边出栈出空，就可以把左边的数据换到右边

所以数据只要转移一次就可以解决了

2.2.2 具体步骤

先实现一个栈

#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int STDataType;
struct Stack
{
	STDataType* a;
	int capacity;	//容量，方便增容
	int top;	//栈顶
};

typedef struct Stack Stack;

void StackInit(Stack *pst);
void StackDestroy(Stack* pst);
void StackPush(Stack* pst,STDataType x);
//性质决定了在栈顶数据出入
STDataType StackTop(Stack* pst);
void  StackPop(Stack* pst);

bool StackEmpty(Stack* pst);
int StzckSize(Stack* pst);
void StackInit(Stack* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;

}
void StackDestroy(Stack* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}
void StackPush(Stack* pst,STDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;//容量翻倍
		STDataType* tmp = realloc(pst->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		pst->a = tmp;
		pst->capacity =newCapacity;
	} 
	pst->a[pst->top] = x;
	pst->top++;
}

STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	return pst->a[pst->top - 1];//从高下标往低下标  
}
void StackPop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));

	pst->top--;
}
bool StackEmpty(Stack* pst)
{
	assert(pst);
	return pst->top == 0;//布尔来判断
}

int StackSize(Stack* pst)
{
	assert(pst);
	return pst->top;//恰好是size
}

`myQueueCreate`

typedef struct {
Stack pushST;
Stack popST;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue*q=(MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&q->pushST);
    StackInit(&q->popST);
    return q;
}

`myQueuePush`

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

`myQueuePop`

int myQueuePop(MyQueue* obj) {
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST); 
        }
    }
   int top=StackTop(&obj->popST);
       StackPop(&obj->popST);
   return top;
}

`myQueuePeek`

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

`myQueueEmpty`

bool myQueueEmpty(MyQueue* obj) {
 return StackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);
}

`myQueueFree`

void myQueueFree(MyQueue* obj) {
	StackDestroy(&obj->pushST);
	StackDestroy(&obj->popST);
	free(obj);
}

2.3 整体实现

#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef char STDataType;
struct Stack
{
	STDataType* a;
	int capacity;	//容量，方便增容
	int top;	//栈顶
};

typedef struct Stack Stack;

void StackInit(Stack *pst);
void StackDestroy(Stack* pst);
void StackPush(Stack* pst,STDataType x);
//性质决定了在栈顶数据出入
STDataType StackTop(Stack* pst);
void  StackPop(Stack* pst);
bool StackEmpty(Stack* pst);
void StackInit(Stack* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;

}
void StackDestroy(Stack* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}
void StackPush(Stack* pst,STDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;//容量翻倍
		STDataType* tmp = realloc(pst->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		pst->a = tmp;
		pst->capacity =newCapacity;
	} 
	pst->a[pst->top] = x;
	pst->top++;
}

STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	return pst->a[pst->top - 1];//从高下标往低下标  
}
void StackPop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));

	pst->top--;
}
bool StackEmpty(Stack* pst)
{
	assert(pst);
	return pst->top == 0;//布尔来判断
}

int StackSize(Stack* pst)
{
	assert(pst);
	return pst->top;//恰好是size
}
typedef struct {
Stack pushST;
Stack popST;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue*q=(MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&q->pushST);
    StackInit(&q->popST);
    return q;
}

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

int myQueuePop(MyQueue* obj) {
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST); 
        }
    }
   int top=StackTop(&obj->popST);
   StackPop(&obj->popST);
   return top;
}

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

bool myQueueEmpty(MyQueue* obj) {
 return StackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);
}

void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->pushST);
StackDestroy(&obj->popST);
free(obj);
}

一点补充:

这道题目的实现中其实可以复用一下

就是这个myQueuePop
int myQueuePop(MyQueue* obj) {
int top=myQueuePeek(&obj->popST);
    StackPop(&obj->popST);
return top;
}
就只是这样改，暂时还不对

既然遇到错误，我们假设不知道是pop的问题，这里试着通过测试用例来排个错，这是常用的排错方法：

对于这样一个错误

报了内存错误，修改一下输入，一个个看看是哪一个函数存在问题

说明这几个输入是没有问题的

当我尝试了pop的时候出错了，说明要改pop
int myQueuePop(MyQueue* obj) {
   int top=myQueuePeek(obj);
   StackPop(&obj->popST);
   return top;
}
当然应该是这么改，主要想展示一下怎么解决报错和服用代码

总结：

栈和队列互相实现的过程是类似的，都是通过两个栈或者两个队列的数据交换来实现栈顶栈底或是队列头或是队列尾功能

如果老铁们有收获的话，希望给个一键三连哦，谢谢

张士玉小黑屋

当前位置：首页 » 《随便一记》 » 正文

leetcode 栈和队列的互相实现_Allen9012的博客

7 人参与 2022年05月26日 12:00 分类 : 《随便一记》 评论

leetcode 栈和队列的互相实现

1. 用队列实现栈

1.1 题目描述

1.1.1 接口函数

1.2 大致框架

1.2.1 想法和思路

1.2.2 具体步骤

先实现一个栈

MyStack

myStackCreate

myStackPush

myStackPop

myStackTop

myStackEmpty

myStackFree

1.2.3 测试时发生的错误

解决第一个错误

解决第二个错误

解决第三个错误

1.3 整体实现

2. 用栈实现队列

2.1 题目描述

2.1.1 接口函数

2.2 大致框架

2.2.1 想法和思路

2.2.2 具体步骤

先实现一个栈

myQueueCreate

myQueuePush

myQueuePop

myQueuePeek

myQueueEmpty

myQueueFree

2.3 整体实现

评论（0） 赞助本站

search zhannei

最新文章

7 人参与 2022年05月26日 12:00 分类 : 《随便一记》评论

`MyStack`

`myStackCreate`

`myStackPush`

`myStackPop`

`myStackTop`

`myStackEmpty`

`myStackFree`

`myQueueCreate`

`myQueuePush`

`myQueuePop`

`myQueuePeek`

`myQueueEmpty`

`myQueueFree`

评论（0）

赞助本站