用栈实现队列 / 用队列实现栈

OJ题链接：

用栈实现队列

用队列实现栈

 

 

 用栈实现队列

1.基本思想

我们需要实现队列的四种操作：增删查和判空。对于栈，我们增加元素和删除元素都只能从栈顶实现，并且只能返回栈顶的元素，而对于队列，以栈的视角来看，我们增加元素从栈顶插入，而删除和查找只能从栈底实现，所以我们的重点应放在如何获取和改变栈底的元素上。

我们构建两个栈，如果想获得栈底的元素，我们可以把栈1的元素全部“倒入”栈2中，便实现了栈的反转。

此时我们对栈二进行出栈的操作，就相当于删除了栈1栈尾的元素（也就是队列的删除） 

而我们想插入，因为栈的插入和队列的插入是相同的，所以我们只需要把栈2的元素再倒回栈1，对栈1进行插入便可以了

 但是，如果我们需要连续删除，需不需要倒来倒去呢？

 我们发现，删除1之后，2成为了栈1栈底的元素。也就是说，无论我们进行多少次删除，栈2中栈顶的元素永远是栈1中栈底的元素，对栈2的出栈永远是队列的出队列

所以我们可以把栈1定义为入队列的栈，把栈2定义为出队列的栈，如果要入队列，只需要把栈2的元素全部倒入栈1，而如果要出队列，只需要把栈1的元素全部倒入栈2，然后进行入栈出栈的操作。

2.判空

如果入队列栈（栈1），出队列栈（栈2）都为空，队列自然也为空

3.增

如果出队列栈为空，则有两种情况：

1. 队列为空
2. 元素全在入队列栈

而无论哪种情况，都可以直接将元素插入入队列栈

如果出队列栈不为空，则需先将出队列栈元素全部倒入入队列栈，然后再将元素插入入队列栈 

4.删

如果入队列栈为空，则有两种情况

1. 队列为空
2. 元素全在出队列栈

对于第一种情况，队列没有元素进行队列的删除，会发生报错

而对于第二种情况，可以直接将栈顶元素删除

如果入队列栈不为空，则需先将入队列栈元素全部倒入出队列栈，然后再将出队列栈栈顶元素删除。

5.查找队列头元素 

和队列的删除一样，只不过我们不需要删除该元素，只需要返回出队列栈的栈顶元素便可

6.总代码实现 

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps)
{
	STDataType* tmp = (STDataType*)malloc(sizeof(STDataType) * 4);
	ps->a = tmp;
	ps->top = 0;
	ps->capacity = 4;
}
// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
		ps->a = tmp;
		ps->capacity *= 2;
	}
	(ps->a)[ps->top] = data;
	ps->top++;
}
// 出栈 
void StackPop(Stack* ps)
{
	assert(ps->top);
	ps->top--;
}
// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps->top);
	return (ps->a)[ps->top - 1];
}
// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	return ps->top;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	if (ps->top == 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
// 销毁栈 
void StackDestroy(Stack* ps)
{
	free(ps->a);
	ps->top = 0;
	ps->capacity = 0;
}

//队列的定义
typedef struct {
    Stack* Stack1;//入队列栈
    Stack* Stack2;//出队列栈
} MyQueue;

//队列的创建
MyQueue* myQueueCreate()
{
    Stack* pstack1=(Stack*)malloc(sizeof(Stack));
    Stack* pstack2=(Stack*)malloc(sizeof(Stack));
    StackInit(pstack1);
    StackInit(pstack2);
    MyQueue* queue=(MyQueue*)malloc(sizeof(MyQueue));
    queue->Stack1=pstack1;
    queue->Stack2=pstack2;
    return queue;
}

//队列的插入
void myQueuePush(MyQueue* obj, int x) {
    if(StackEmpty(obj->Stack1))
    {
        while(!StackEmpty(obj->Stack2))
        {
            int top=StackTop(obj->Stack2);
            StackPush(obj->Stack1,top);
            StackPop(obj->Stack2);
        }
    }
    StackPush(obj->Stack1,x);
}

//队列的删除
int myQueuePop(MyQueue* obj) {
    if(StackEmpty(obj->Stack2))
    {
        while(!StackEmpty(obj->Stack1))
        {
            int top=StackTop(obj->Stack1);
            StackPush(obj->Stack2,top);
            StackPop(obj->Stack1);
        }
    }
    int top=StackTop(obj->Stack2);
    StackPop(obj->Stack2);
    return top;
}

//返回队列头元素
int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(obj->Stack2))
    {
        while(!StackEmpty(obj->Stack1))
        {
            int top=StackTop(obj->Stack1);
            StackPush(obj->Stack2,top);
            StackPop(obj->Stack1);
        }
    }
    int top=StackTop(obj->Stack2);
    return top;
}

//队列的判空
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(obj->Stack1)&&StackEmpty(obj->Stack2);
}

//队列的销毁
void myQueueFree(MyQueue* obj) {
    StackDestroy(obj->Stack1);
    StackDestroy(obj->Stack2);
    free(obj);
}

 用队列实现栈

1.基本思想

我们不妨类比用栈实现队列的思想

 我们想将元素倒来倒去后，我们会发现，无论如何倒元素，元素的顺序都不会发生改变，队列的结构也不会发生变化，我们想获取栈顶的元素（即队列1队尾的元素），只能在倒的过程种，让队列只剩下1个元素，该元素即为队列尾（栈顶）的元素

而对第二次获取元素，我们还需要重复该操作，将元素再倒一遍，直到剩下一个元素，即为队列尾（栈顶）的元素。

也就是说，用队列实现栈的每一次删除我们都需要倒一遍队列，也就无法实现入栈队列或者出栈队列的称呼了。

但是对于栈的插入，我们只需要在有元素的队列直接插入便可以，不需要倒元素。

2.判空

如果两队列均为空，自然栈为空

3.增

首先判断哪一个队列不为空，然后将元素插入到不为空的队列即可

4.删

如果栈为空，则报错

如果栈不为空，我们找到不为空的队列，将其元素不断插入到另一个队列中直到剩下一个元素，然后删除这最后一个元素。

5.查找栈顶元素

和栈的删除一样，我们找到不为空的队列，将其元素不断插入到另一个队列中直到剩下一个元素，然后获得这一元素的值。

接着，我们不需要删除这一元素，只需要将这最后一个元素插入到另一个队列即可。

6.总代码实现

typedef int QDataType;
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;
	QNode* rear;
}Queue;
// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
	q->front = NULL;
	q->rear = NULL;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	if (q->front == NULL)
	{
		QNode* newnode = (QNode*)malloc(sizeof(QNode));
		newnode->next = NULL;
		newnode->data = data;
		q->front = newnode;
		q->rear = newnode;
	}
	else
	{
		QNode* newnode = (QNode*)malloc(sizeof(QNode));
		newnode->next = NULL;
		newnode->data = data;
		q->rear->next = newnode;
		q->rear = q->rear->next;
	}
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->front);
	QNode* erase = q->front;
	q->front = q->front->next;
	if (q->rear == erase)
	{
		q->rear = NULL;
	}
	free(erase);
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->front);
	return q->front->data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->front);
	return q->rear->data;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	if (q->front == NULL)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
	while (q->front)
	{
		QNode* erase = q->front;
		q->front = q->front->next;
		free(erase);
	}
	q->rear = NULL;
}

//栈的结构定义
typedef struct {
    Queue* queue1;
    Queue* queue2;
} MyStack;

//栈的创建
MyStack* myStackCreate() {
    MyStack* tmp=(MyStack*)malloc(sizeof(MyStack));
    tmp->queue1=(Queue*)malloc(sizeof(Queue));
    tmp->queue2=(Queue*)malloc(sizeof(Queue));
    QueueInit(tmp->queue1);
    QueueInit(tmp->queue2);
    return tmp;
}

//栈的插入
void myStackPush(MyStack* obj, int x) {
    if(QueueEmpty(obj->queue2))
    QueuePush(obj->queue1,x);
    else
    QueuePush(obj->queue2,x);
}

//栈的删除
int myStackPop(MyStack* obj) {
    assert(!QueueEmpty(obj->queue1)||!QueueEmpty(obj->queue2));
    if(QueueEmpty(obj->queue1))
    {
        while(obj->queue2->front!=obj->queue2->rear)
        {
            QDataType tmp=QueueFront(obj->queue2);
            QueuePop(obj->queue2);
            QueuePush(obj->queue1,tmp);
        }
        QDataType ret=QueueFront(obj->queue2);
        QueuePop(obj->queue2);
        return ret;
    }
    else
    {
        while(obj->queue1->front!=obj->queue1->rear)
        {
            QDataType tmp=QueueFront(obj->queue1);
            QueuePop(obj->queue1);
            QueuePush(obj->queue2,tmp);
        }
        QDataType ret=QueueFront(obj->queue1);
        QueuePop(obj->queue1);
        return ret;
    }
}

//获取栈顶元素
int myStackTop(MyStack* obj) {
    assert(!QueueEmpty(obj->queue1)||!QueueEmpty(obj->queue2));
    if(QueueEmpty(obj->queue1))
    {
        while(obj->queue2->front!=obj->queue2->rear)
        {
            QDataType tmp=QueueFront(obj->queue2);
            QueuePop(obj->queue2);
            QueuePush(obj->queue1,tmp);
        }
        QDataType ret=QueueFront(obj->queue2);
        QueuePop(obj->queue2);
        QueuePush(obj->queue1,ret);
        return ret;
    }
    else
    {
        while(obj->queue1->front!=obj->queue1->rear)
        {
            QDataType tmp=QueueFront(obj->queue1);
            QueuePop(obj->queue1);
            QueuePush(obj->queue2,tmp);
        }
        QDataType ret=QueueFront(obj->queue1);
        QueuePop(obj->queue1);
        QueuePush(obj->queue2,ret);
        return ret;
    }
}

//栈的判空
bool myStackEmpty(MyStack* obj) {
    if(QueueEmpty(obj->queue1)&&QueueEmpty(obj->queue2))
    return true;
    return false;
}

//栈的销毁
void myStackFree(MyStack* obj) {
    QueueDestroy(obj->queue1);
    QueueDestroy(obj->queue2);
    free(obj);
}