这里是栈的源代码:栈和队列的实现
当然,自己也可以写一个栈来用,对题目来说不影响,只要符合栈的特点就行。
题目:
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(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); }