[Leetcode]用栈实现队列

用栈实现队列：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

1.题解：

通过两个栈的配合实现队列的基本功能，下面先实现栈的基本功能

栈： （前面文章介绍过栈的实现，这里就不过多阐述）

typedef int StackDataType;
typedef struct Stack {
	StackDataType* head;
	int capacity;
	int size;
}Stack;
//创建栈
Stack* StackCreate() {
	Stack* tmp = (Stack*)malloc(sizeof(Stack));
	tmp->head = NULL;
	tmp->capacity = tmp->size = 0;
	return tmp;
}
//入栈
void StackPush(Stack*tmp,StackDataType x) {
	if (tmp->capacity == tmp->size) {
		int newcapacity = tmp->capacity == 0 ? 4 : 2 * tmp->capacity;
		StackDataType* cur = (StackDataType*)realloc(tmp->head, newcapacity * sizeof(StackDataType));
		if (cur == NULL) {
			perror("StackPush:malloc");
			exit;
		}
		tmp->head = cur;
		tmp->capacity = newcapacity;
	}
	tmp->head[tmp->size] = x;
	tmp->size++;
}
//出栈
StackDataType StackPop(Stack*tmp) {
	if (tmp->size == 0) {
		perror("StackPop:NULL");
		exit;
	}
	StackDataType s = tmp->head[tmp->size - 1];
	tmp->size--;
	return s;
}
//栈的销毁
void StackDestroy(Stack*tmp) {
	free(tmp->head);
	tmp->head = NULL;
	tmp->capacity = tmp->size = 0;
	free(tmp);
	tmp = NULL;
}

2.基于栈实现队列基本功能：

入队列：

根据上图思路，一个栈（stack1）存储数据，一个栈（stack2）出数据。

void myQueuePush(MyQueue* obj, int x) {
	assert(obj);
	StackPush(obj->stack1, x);
}

出队列：

出队列就涉及到判断出数据的那个栈（stack2）是否有数据（栈判空（StackEmpty））

int myQueuePop(MyQueue* obj) {
	assert(obj);
	if (obj->stack2->size == 0) {
		while (obj->stack1->size != 0) {
			StackPush(obj->stack2, StackPop(obj->stack1));
		}
	}
	return StackPop(obj->stack2);
}

返回队列顶部元素：

同样涉及判空问题，因为该功能仅和出队列少了最后删除元素

int myQueuePeek(MyQueue* obj) {
	assert(obj);
	if (obj->stack2->size == 0) {
		if (obj->stack1->size == 0) {
			perror("Peek:NULL");
			exit;
		}
		return obj->stack1->head[0];
	}
	return obj->stack2->head[obj->stack2->size - 1];
}

 判空：

stack1与stack2均为空

bool myQueueEmpty(MyQueue* obj) {
	assert(obj);
	return obj->stack1->size == 0 && obj->stack2->size == 0;
}

 3.完整代码：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int StackDataType;
typedef struct Stack {
	StackDataType* head;
	int capacity;
	int size;
}Stack;
Stack* StackCreate() {
	Stack* tmp = (Stack*)malloc(sizeof(Stack));
	tmp->head = NULL;
	tmp->capacity = tmp->size = 0;
	return tmp;
}
void StackPush(Stack*tmp,StackDataType x) {
	if (tmp->capacity == tmp->size) {
		int newcapacity = tmp->capacity == 0 ? 4 : 2 * tmp->capacity;
		StackDataType* cur = (StackDataType*)realloc(tmp->head, newcapacity * sizeof(StackDataType));
		if (cur == NULL) {
			perror("StackPush:malloc");
			exit;
		}
		tmp->head = cur;
		tmp->capacity = newcapacity;
	}
	tmp->head[tmp->size] = x;
	tmp->size++;
}
StackDataType StackPop(Stack*tmp) {
	if (tmp->size == 0) {
		perror("StackPop:NULL");
		exit;
	}
	StackDataType s = tmp->head[tmp->size - 1];
	tmp->size--;
	return s;
}
void StackDestroy(Stack*tmp) {
	free(tmp->head);
	tmp->head = NULL;
	tmp->capacity = tmp->size = 0;
	free(tmp);
	tmp = NULL;
}
typedef struct Queue{
	Stack* stack1;
	Stack* stack2;
}MyQueue;

MyQueue* myQueueCreate() {
	MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));
	queue->stack1 = StackCreate();
	queue->stack2 = StackCreate();
	return queue;
}

void myQueuePush(MyQueue* obj, int x) {
	assert(obj);
	StackPush(obj->stack1, x);
}

int myQueuePop(MyQueue* obj) {
	assert(obj);
	if (obj->stack2->size == 0) {
		while (obj->stack1->size != 0) {
			StackPush(obj->stack2, StackPop(obj->stack1));
		}
	}
	return StackPop(obj->stack2);
}

int myQueuePeek(MyQueue* obj) {
	assert(obj);
	if (obj->stack2->size == 0) {
		if (obj->stack1->size == 0) {
			perror("Peek:NULL");
			exit;
		}
		return obj->stack1->head[0];
	}
	return obj->stack2->head[obj->stack2->size - 1];
}

bool myQueueEmpty(MyQueue* obj) {
	assert(obj);
	return obj->stack1->size == 0 && obj->stack2->size == 0;
}