【栈和队列】用栈实现队列

OJ链接

入队：往pushST中插入数据 出队：popST不为空直接出数据，否则将pushST中的数据导入到popST中再出数据 取队头：逻辑同出队操作，但是这里只取数据不删除数据

typedef int STDataType;
//定义栈的结构
typedef struct Stack
{
STDataType* arr;
int top; //指向栈顶的位置
int capacity;//栈的容量

}ST;

//初始化
void STInit(ST* ps)
{
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
//销毁
void StackDestroy(ST* ps)
{
if (ps->arr)
free(ps->arr);
ps->arr = NULL;
ps->capacity = ps->top = 0;

}

//入栈–栈顶
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
//增容
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity*sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
ps->arr[ps->top++] = x;
}
//栈是否为空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
//出栈
void StackPop(ST* ps)
{
assert(!StackEmpty(ps));
—ps->top;
}
//取栈顶元素
STDataType stackTop(ST* ps)
{
assert(!StackEmpty(ps));
return ps->arr[ps->top – 1];
}
//获取栈中有效的元素个数
int StackSize(ST* ps)
{
return ps->top;
}
//———————以上是栈的实现代码————————–

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

//队列的初始化
MyQueue* myQueueCreate() {
MyQueue* pq=(MyQueue*)malloc(sizeof(MyQueue));
STInit(&pq->pushST);
STInit(&pq->popST);

return pq;
}

void myQueuePush(MyQueue* obj, int x) {
//往pushST中插入数据
StackPush(&obj->pushST,x);
}
//检查popST是否为空
//1）不为空，直接出popST栈顶
//2）为空，pushST数据导入到popST中，再出popST栈顶
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);
obj=NULL;
}