全国疫情风险区域汇总seo技术网
这里是栈的源代码:栈和队列的实现
当然,自己也可以写一个栈来用,对题目来说不影响,只要符合栈的特点就行。
题目:
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(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; }
题目正题:
//定义出两个栈
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宝啊:我的主页鸭
愿所有美好如期而遇