用栈实现队列（OJ中报错的处理）

用栈实现队列

=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容器的话可以及其方便。