如何实现队列和栈的转化（c语言）

文章目录

一.什么是栈
二.什么是队列
三.怎么把栈变成队列（力扣）
四.怎么把队列变成栈（力扣）
总结

一.什么是栈

栈（stack）又名堆栈，它是一种运算受限的线性表。限定权在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

其实只要注意栈的一个特点就是后进先出

二.什么是队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

其实也是只有注意一点就是队列的特点就是先进先出

接下来我们只要是要解决队列是栈之间的转化，怎么把队列变成栈，怎么把栈变成队列

三.怎么把栈变成队列（力扣）

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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（双端队列）来模拟一个栈，只要是标准的栈操作即可。

思路：设置两个站一个入数据，一个出数据，设置两个站一个入数据，一个出数据

3.1初始化

typedef struct {
	stack PushST;
	stack PopST;

} MyQueue;

3.2创建

开辟两个栈的空间

MyQueue* myQueueCreate() {
	MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
	stackInit(&q->PushST);
	stackInit(&q->PopST);
	return p;
}

3.3插入 `void push(int x)` 将元素 x 推到队列的末尾

如果要插元素，就放入push这个栈里

void myQueuePush(MyQueue* obj, int x) {
	assert(obj);
	stack Push(&obj->PushST, x);
}

3.4删除从队列的开头移除并返回元素

因为是队列，要满足先入先出，所以先判断Pop栈里还有没有数据，如果没有，就把push里的数据放过来，放一个就把Push栈里的数据删一个，然后在删Pop里的就可以了

int myQueuePop(MyQueue* obj) {
	if (stackEmpty(&obj->PopST))
	{
		while (!stackEmpty(&obj->PushST))
		{
			stackPush(&obj->PopST, stackTop(&obj->PushST));
			stackPop((&obj->PushST);
		}
		
	}
	int front = stackTop(&obj->PopST);
	stackPop(&obj->PopST);
	return front;
}

3.5去数据返回队列开头的元素

和删除数据前面是一样的，但是这个不用删，所以结尾返回就可以了

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);

}

3.6检查数据和释放数据

bool myQueueEmpty(MyQueue* obj) {
	return stackEmpty(&obj->PushST) && stackEmpty(&obj->PopST);
}


void myQueueFree(MyQueue* obj) {
	stackDestroy(&obj->PushST);
	stackDestroy(&obj->PopST);
	free(obj);
}

四.怎么把队列变成栈（力扣）

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

核心思路：入数据时，往部位空的队列入保持另一个队列为空，出数据的时候，一次从对头的数据转移到另一个队列保存，只剩最后一个的时候pop掉

3.1初始化

typedef struct {
	Queue q1;
	Queue q2;

} MyStack;

3.2创建

开辟两个队列，用来实现栈结构

MyStack* myStackCreate() {
	MyStack* st = (MyStack*)malloc(sizeof(MyStack));
	QueueInit(st->q1);
	QueueInit(st->q2);
	return st;
}

3.3插入 `void push(int x)` 将元素 x 压入栈顶

入数据时，往部位空的队列入保持另一个队列为空，谁空就入谁

void myStackPush(MyStack* obj, int x) {
	if (!QueueEmpty(&obj->q1))
	{
		Queuepush(&obj->q1,x);
	}
	else
	{
		Queuepush(&obj->q2, x);
	}
}

3.4删除移除并返回栈顶元素。

先判断那个队列是空的，然后把数据放到空的里，还剩一个的时候删除

int myStackPop(MyStack* obj) {
	//判断那个为空
	Queue* emptyQ = &obj->q1;
	Queue* noemptyQ = &obj->q2;
	if (!QueueEmpty(&obj->q1))
	{
		emptyQ = &obj->q2;
		noemptyQ = &obj->q1;
	}
	while (Queuesize(noemptyQ > 1))
	{
		Queuepush(emptyQ, QueueFront(noemptyQ));
		Queuepop(noemptyQ);
	}
	//还剩最后一个
	Queuepop(noemptyQ);
	int top = QueueFront(noemptyQ);
	return top;
}

3.5取头顶数据返回栈顶元素。

先判断那个是空，top就是非空的尾数据

int myStackTop(MyStack* obj) {
	if (!QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q1);
	}
	else
	{
		return QueueBack(&obj->q2);
	}
}

3.6检查数据和释放数据

bool myStackEmpty(MyStack* obj) {
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
	QueueDestroy(&obj->q1);
	QueueDestroy(&obj->q2);
	free(obj);
}