用栈实现队列
=ERROR: AddressSanitizer:
myQueueFree函数中栈的释放处现了问题,没有调用StackDestory而是直接free了。
这个是栈初始化时,capacity与malloc申请的空间大小没有匹配。
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(
push
、
pop
、
peek
、
empty
):
实现
MyQueue
类:
-
void push(int x)
将元素 x 推到队列的末尾
-
int pop()
从队列的开头移除并返回元素
-
int peek()
返回队列开头的元素
-
boolean empty()
如果队列为空,返回
true
;否则,返回
false
说明:
-
你
只能
使用标准的栈操作 —— 也就是只有
push to top
,
peek/pop from top
,
size
, 和
is empty
操作是合法的。
-
你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
在开始这个题之前应熟悉掌握栈和队列的基础操作。
进栈,出栈,栈顶元素,栈是否为空,以及栈是先进后出的。
代码:
typedef int SLDataType;
typedef struct Stack {
SLDataType* a;
int top;
int capacity;
}Stack;
void StackInit(Stack* pst);
void StackDestroy(Stack* pst);
void StackPush(Stack* pst, SLDataType x);
void StackPop(Stack* pst);
SLDataType StackTop(Stack* pst);
bool StackEmpty(Stack* pst);
int StackSize(Stack* pst);
void StackInit(Stack* pst) {
assert(pst);
pst->a = (SLDataType*)malloc(sizeof(SLDataType)*4);
pst->top = 0;
pst->capacity = 4;
}
void StackDestroy(Stack* pst) {
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}
void StackPush(Stack* pst, SLDataType x) {
assert(pst);
if (pst->top == pst->capacity) {
SLDataType* tmp = (SLDataType*)realloc(pst->a,sizeof(SLDataType)*pst->capacity*2);
if (tmp == NULL) {
printf("realloc fail\n");
exit(-1);
}
pst->a = tmp;
pst->capacity *= 2;
}
pst->a[pst->top] = x;
pst->top++;
}
void StackPop(Stack* pst) {
assert(pst);
assert(!StackEmpty(pst));
pst->top--;
}
SLDataType StackTop(Stack* pst) {
assert(pst);
assert(!StackEmpty(pst));
return pst->a[pst->top-1];
}
bool StackEmpty(Stack* pst) {
assert(pst);
return pst->top == 0;
}
int StackSize(Stack* pst) {
assert(pst);
return pst->top;
}
typedef struct {
Stack pushST;
Stack popST;
}MyQueue;
MyQueue* myQueueCreate() {
MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
StackInit(&q->pushST);
StackInit(&q->popST);
return q;
}
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->pushST, x);
}
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);
}
int myQueuePop(MyQueue* obj) {
int pop = myQueuePeek(obj);
StackPop(&obj->popST);
return pop;
}
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->pushST);
StackDestroy(&obj->popST);
free(obj);
}
使用c++的stack容器的话可以及其方便。