链接
描述
思路
上次我们的想法是创建两个普通的栈,在完成出栈与入栈后,为了保持顺序不变,我们采用的方法将元素从另一个栈中重新打回去,但是这样会导致时间大大加长,我们这次换一个思路
一个栈用来存放push的元素,另一个用来存放pop的元素
基本思路如下:
打入5个元素,push栈中存放1,2,3,4,5
假设pop两次
pop栈此时为空,我们将push栈中全部元素打入pop栈
此时pop栈为5,4,3,2,1,push栈为空
我们可以发现,接下来无论要pop几次,都要先将pop栈中的元素清空
pop两次后,pop栈中剩下5,4,3。
我们再打入5个元素,push栈中存放6,7,8,9,10
我们再pop八次,先将pop栈中剩下的三个元素弹出,之后pop栈为空,又将push栈中全部元素打入pop栈,继续pop即可实现队列的操作
代码如下
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
void StackInit(Stack* ps) {
ps->_a = NULL;
ps->_capacity = 0;
ps->_top = -1;
}
void StackPush(Stack* ps, STDataType data) {
if (ps->_capacity == ps->_top + 1) {
int newcapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
STDataType* tmp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));
if (tmp == NULL) {
perror("realloc error");
return;
}
ps->_a = tmp;
ps->_capacity = newcapacity;
}
ps->_top++;
ps->_a[ps->_top] = data;
}
void StackPop(Stack* ps) {
if (ps->_top == -1) {
printf("no value!\n");
return;
}
ps->_top--;
}
STDataType StackTop(Stack* ps) {
return ps->_a[ps->_top];
}
int StackSize(Stack* ps) {
return ps->_top + 1;
}
int StackEmpty(Stack* ps) {
if (ps->_top == -1)
return 1;
return 0;
}
void StackDestroy(Stack* ps) {
ps->_capacity = 0;
ps->_top = -1;
free(ps->_a);
ps->_a = NULL;
}
typedef struct {
Stack pushst;
Stack popst;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* mn = (MyQueue*)malloc(sizeof(MyQueue));
StackInit(&(mn->popst));
StackInit(&(mn->pushst));
return mn;
}
void myQueuePush(MyQueue* obj, int x) {
StackPush(&(obj->pushst), x);
}
int myQueuePop(MyQueue* obj) {
int a;
if (StackEmpty(&(obj->popst))) {
while (!StackEmpty(&(obj->pushst))) {
StackPush(&(obj->popst), StackTop(&(obj->pushst)));
StackPop(&(obj->pushst));
}
}
a = StackTop(&(obj->popst));
StackPop(&(obj->popst));
return a;
}
int myQueuePeek(MyQueue* obj) {
int a;
if (StackEmpty(&(obj->popst))) {
while (!StackEmpty(&(obj->pushst))) {
StackPush(&(obj->popst), StackTop(&(obj->pushst)));
StackPop(&(obj->pushst));
}
}
a = StackTop(&(obj->popst));
return a;
}
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&(obj->popst)) && StackEmpty(&(obj->pushst));
}
void myQueueFree(MyQueue* obj) {
free(obj->popst._a);
free(obj->pushst._a);
free(obj);
}