软件工程公司排名,简述搜索引擎优化,wordpress+手机端,目前网站开发怎么兼顾手机LeetCode链接#xff1a;232. 用栈实现队列 - 力扣#xff08;LeetCode#xff09; 注#xff1a;本文默认读者已掌握栈与队列的基本操作
可以看这篇文章熟悉知识点#xff1a;【数据结构】栈与队列_字节连结的博客-CSDN博客
目录
做题思路
代码实现
1. MyQueue
2. … LeetCode链接232. 用栈实现队列 - 力扣LeetCode 注本文默认读者已掌握栈与队列的基本操作
可以看这篇文章熟悉知识点【数据结构】栈与队列_字节连结的博客-CSDN博客
目录
做题思路
代码实现
1. MyQueue
2. myQueueCreate 3. myQueuePush
4. myQueuePeek
5. myQueuePop
6. myQueueEmpty
7. myQueueFree
全部代码 做题思路
简单来说就是把一个栈栈1的数据捯入另一个栈栈2此时栈2出数据的顺序就和队列是一样的。
为了更方便理解我会画图来演示一下具体思路。
我们需要两个栈来实现队列 push栈专门入数据的栈pop栈专门出数据的栈 如下图 插入数据直接在push栈内插入即可 push栈内插入数据1、2、3、4、5 删除数据需要把push栈内的数据捯入pop栈 栈是后入先出的当push栈的数据捯入pop栈后数据顺序会改变 如下图 可以看到数据顺序逆转了
但是栈的这些操作跟队列有什么联系呢
不妨来看看pop栈与队列的对比 由此可见pop栈出数据的顺序是和队列一样的 到这里思路已经很清晰了我们需要两个栈一个专门用来push一个专门用来pop捯数据后pop栈出数据的顺序就跟队列是一样的。 那么如何用代码C来实现这个思路呢 代码实现
由于我们使用的是C语言不能直接使用栈的操作
所以先把之前模拟实现过的栈复制过来
//C语言模拟实现栈typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;//初始化栈
void STInit(ST* ps);
//销毁栈
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空如果为空返回非零结果如果不为空返回0
bool STEmpty(ST* ps);void STInit(ST* ps)
{assert(ps);ps-a NULL;ps-capacity 0;ps-top 0;
}void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity 0;ps-top 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);if (ps-top ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;ps-top;
}void STPop(ST* ps)
{assert(ps);assert(ps-top 0);ps-top--;
}STDataType STTop(ST* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}int STSize(ST* ps)
{assert(ps);return ps-top;
}bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}
复制完成之后就是本题的重点内容了。
本题要求 实现 MyQueue 类 void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空返回 true 否则返回 false 1. MyQueue
由于我们是用两个栈实现队列
所以这里需要定义两个栈
//两个栈模拟实现队列
typedef struct
{ST pushst;ST popst;
} MyQueue;
2. myQueueCreate
这个函数要求我们开辟空间并初始化栈
//开辟空间并初始化
MyQueue* myQueueCreate()
{MyQueue* obj (MyQueue*)malloc(sizeof(MyQueue));STInit(obj-pushst);STInit(obj-popst);return obj;
} 3. myQueuePush
直接把数据插入到push栈即可
//将元素X推到队列的末尾
void myQueuePush(MyQueue* obj, int x)
{STPush(obj-pushst, x);
}4. myQueuePeek
本函数要求返回队列开头的元素
如果pop栈为空要把push栈的数据捯入pop栈才能找到队列的首元素如果pop栈不为空pop栈的栈顶元素就是队列的首元素 //返回队列开头的元素
int myQueuePeek(MyQueue* obj)
{if (STEmpty(obj-popst)){//捯数据while (!STEmpty(obj-pushst)){STPush(obj-popst, STTop(obj-pushst));STPop(obj-pushst);}}return STTop(obj-popst);
}
5. myQueuePop
要求删除队头元素也就是pop栈的栈顶元素直接删除即可并且要返回队头元素的值需要先定义一个临时变量来保存队头元素的值最后返回这个临时变量
//从队列的开头移除并返回元素
int myQueuePop(MyQueue* obj)
{int front myQueuePeek(obj);STPop(obj-popst);return front;
}
6. myQueueEmpty
判断队列是否为空返回一个bool值true/false
如果push栈和pop栈都为空则说明队列为空
//如果队列为空返回true否则返回false
bool myQueueEmpty(MyQueue* obj)
{return STEmpty(obj-popst) STEmpty(obj-pushst);
}
7. myQueueFree
销毁队列
销毁push栈和pop栈释放动态开辟的空间
//销毁队列
void myQueueFree(MyQueue* obj)
{STDestroy(obj-popst);STDestroy(obj-pushst);free(obj);
}
到这里全部函数已经实现完毕提交代码 成功通过
下面我会把本题的全部代码整合在一起发出来 全部代码
//C语言模拟实现栈typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;//初始化栈
void STInit(ST* ps);
//销毁栈
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空如果为空返回非零结果如果不为空返回0
bool STEmpty(ST* ps);void STInit(ST* ps)
{assert(ps);ps-a NULL;ps-capacity 0;ps-top 0;
}void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity 0;ps-top 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);if (ps-top ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;ps-top;
}void STPop(ST* ps)
{assert(ps);assert(ps-top 0);ps-top--;
}STDataType STTop(ST* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}int STSize(ST* ps)
{assert(ps);return ps-top;
}bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}////两个栈模拟实现队列
typedef struct
{ST pushst;ST popst;
} MyQueue;//开辟空间并初始化
MyQueue* myQueueCreate()
{MyQueue* obj (MyQueue*)malloc(sizeof(MyQueue));STInit(obj-pushst);STInit(obj-popst);return obj;
}//将元素X推到队列的末尾
void myQueuePush(MyQueue* obj, int x)
{STPush(obj-pushst, x);
}//返回队列开头的元素
int myQueuePeek(MyQueue* obj)
{if (STEmpty(obj-popst)){//捯数据while (!STEmpty(obj-pushst)){STPush(obj-popst, STTop(obj-pushst));STPop(obj-pushst);}}return STTop(obj-popst);
}//从队列的开头移除并返回元素
int myQueuePop(MyQueue* obj)
{int front myQueuePeek(obj);STPop(obj-popst);return front;
}//如果队列为空返回true否则返回false
bool myQueueEmpty(MyQueue* obj)
{return STEmpty(obj-popst) STEmpty(obj-pushst);
}//销毁队列
void myQueueFree(MyQueue* obj)
{STDestroy(obj-popst);STDestroy(obj-pushst);free(obj);
} 本文完
