这里是栈的源代码:栈和队列的实现
当然,自己也可以写一个栈来用,对题目来说不影响,只要符合栈的特点就行。
题目:
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push
、pop
、peek
、empty
):
实现 MyQueue
类:
-
void push(int x)
将元素 x 推到队列的末尾 -
int pop()
从队列的开头移除并返回元素 -
int peek()
返回队列开头的元素 -
boolean empty()
如果队列为空,返回true
;否则,返回false
题解:
做题前需要的栈:
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int DataType; typedef struct Stack { DataType* data; int top; int capacity; }Stack; void Init(Stack *st); void Push(Stack* st, DataType x); void Pop(Stack* st); DataType GetTop(Stack* st); bool Empty(Stack* st); void Destroy(Stack* st); int Size(Stack* st); void Init(Stack* st) { assert(st); st->data = NULL; st->top = 0; st->capacity = 0; } void Push(Stack* st, DataType x) { assert(st); if (st->capacity == st->top) { int newcapacity = (st->capacity == 0) ? 4 : st->capacity * 2; DataType* temp = (DataType*)realloc(st->data, sizeof(DataType) * newcapacity); if (temp == NULL) { perror("realloc fail"); exit(-1); } st->data = temp; st->capacity = newcapacity; } st->data[st->top++] = x; } void Pop(Stack* st) { assert(st); assert(st->top > 0); st->top--; } DataType GetTop(Stack* st) { assert(st); assert(st->top > 0); return st->data[st->top - 1]; } bool Empty(Stack* st) { assert(st); return (st->top == 0); } void Destroy(Stack* st) { assert(st); free(st->data); st->data = NULL; st->top = st->capacity = 0; } int Size(Stack* st) { assert(st); return st->top; }
题目正题: 文章来源:https://www.toymoban.com/news/detail-636604.html
//定义出两个栈
typedef struct
{
Stack push;
Stack pop;
} MyQueue;
//初始化队列
MyQueue* myQueueCreate()
{
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
Init(&obj->push);
Init(&obj->pop);
return obj;
}
//向队列中插入元素
void myQueuePush(MyQueue* obj, int x)
{
Push(&obj->push,x);
}
//元素出队列
int myQueuePop(MyQueue* obj)
{
int ret = myQueuePeek(obj);
Pop(&obj->pop);
return ret;
}
//返回队列开头的元素
int myQueuePeek(MyQueue* obj)
{
if(Empty(&obj->pop))
{
int size = Size(&obj->push);
for(int i=0; i<size; i++)
{
Push(&obj->pop,GetTop(&obj->push));
Pop(&obj->push);
}
}
return GetTop(&obj->pop);
}
//判断队列是否为空
bool myQueueEmpty(MyQueue* obj)
{
return Empty(&obj->pop) && Empty(&obj->push);
}
//销毁队列
void myQueueFree(MyQueue* obj)
{
free((&obj->push)->data);
free((&obj->pop)->data);
free(obj);
}
Lei宝啊:我的主页鸭
愿所有美好如期而遇文章来源地址https://www.toymoban.com/news/detail-636604.html
到了这里,关于(力扣)用两个栈实现队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!