【C语言】栈和队列的相互实现_用栈实现队列c语言

目录

用队列实现栈

代码实现

完整代码

用栈实现队列

 代码实现

完整代码

---

用队列实现栈

力扣链接：用队列实现栈

这个题目，使用队列模拟实现栈，我们是使用C语言来实现，由于C语言没有相应的库所以我们要先手写一个队列出来，在此之前我们还要对队列和栈的性质有所了解 ，可以参考我之前写的文章——（队列的模拟实现）和（栈的模拟实现）

方法：两个队列

为了满足栈的特性，即最后入栈的元素最先出栈，在使用队列实现栈时，应满足队列前端的元素是最后入栈的元素。所以我们可以使用两个队列实现栈的操作，其中一个队列用来存储栈内的元素，另一个队列用来倒数据。

入栈操作：把数据入队到其中一个队列中，另一个队列保持为空队列。

出栈操作：将存储了栈内元素的队列倒到另一个空的队列中，当倒了只剩下一个数据时停止，将这个数据出队就达到了出栈的效果。

  

代码实现

 创建两个队列

typedef struct
 {
    Queue q1;
    Queue q2;
} MyStack;

初始化 

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

 首先看一下这样写行不行？

这样写当然是不行的，因为它是带返回值的，所以我们要返回我们创建的地址，但是st是局部变量，出了这个函数就销毁了，那你接受到的只能是野指针。

所以这里只能用静态的或者malloc动态的，出了这个函数也不会被销毁，但是malloc更好，那我们就用malloc的，然后初始化这两个队列 就行了。

入栈

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

 入栈就很简单了，我们就向队列不为空的入数据，如果两个队列都为空，向哪个队列入数据都行。

出栈

int myStackPop(MyStack* obj) {
    Queue* emptyQ=&obj->q1;
    Queue* nonEmptyQ=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        emptyQ=&obj->q2;
        nonEmptyQ=&obj->q1;
    }
    while(QueueSize(nonEmptyQ)>1)
    {
        QueuePush(emptyQ,QueueFront(nonEmptyQ));
        QueuePop(nonEmptyQ);
    }
    int top=QueueFront(nonEmptyQ);
    QueuePop(nonEmptyQ);
    return top;
}

 这里就需要倒数据了，但是我们不知道哪个为空，哪个不为空，我们可以用假设法。先假设一个为空 ，一个不为空，再来一个if语句判断一下，确定哪个为空，哪个不为空。然后将非空队列的数据倒入空的队列中去，当非空对列倒的只剩下一个数据时就停止，最后pop掉这个数据。

 获取栈顶元素

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

因为我们是用队列来模拟实现栈的，那我们既可以取到对头的数据，也可以取到队尾的数据，这里我们只用取队尾的数据就行了，只需判断哪个不为空，取那个就行。 

判空 

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

注意这里是&&而不是|| ，我们是用两个队列来模拟栈，只有当两个队列都为空时，栈才是空。

销毁栈

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

 我们不仅要销毁这两个队列，还要free掉队列中指针指向的链表。

完整代码

 
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;
 
typedef struct Queue
{
	int size;
	QNode* head;
	QNode* tail;
}Queue;
 
//初始化队列
void QueueInit(Queue* pq);
 
//销毁队列
void QueueDestroy(Queue* pq);
 
//对尾入队列
void QueuePush(Queue* pq, QDataType x);
 
//对头出队列
void QueuePop(Queue* pq);
 
//获取对列头部元素
QDataType QueueFront(Queue* pq);
 
//获取队列队尾元素
QDataType QueueBack(Queue* pq);
 
//判空
bool QueueEmpty(Queue* pq);
 
//获取队列中有效元素的个数
int QueueSize(Queue* pq);
 
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->size = 0;
	pq->head = pq->tail = NULL;
}
 
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}
 
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
 
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}
 
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
 
	//1.一个节点
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;//避免野指针问题
	}
	//2.多个节点
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}
 
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}
 
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}
 
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}
 
int QueueSize(Queue* pq)
{
	assert(pq);
	/*int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}*/
	return pq->size;
}
 
typedef struct
 {
    Queue q1;
    Queue q2;
} MyStack;
 
 
MyStack* myStackCreate() {
    MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}
 
void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}
 
int myStackPop(MyStack* obj) {
    Queue* emptyQ=&obj->q1;
    Queue* nonEmptyQ=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        emptyQ=&obj->q2;
        nonEmptyQ=&obj->q1;
    }
    while(QueueSize(nonEmptyQ)>1)
    {
        QueuePush(emptyQ,QueueFront(nonEmptyQ));
        QueuePop(nonEmptyQ);
    }
    int top=QueueFront(nonEmptyQ);
    QueuePop(nonEmptyQ);
    return top;
}
 
int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
       return QueueBack(&obj->q1);
    }
    else
    {
       return QueueBack(&obj->q2);
    }
}
 
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
 
void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
 
    free(obj);
}

用栈实现队列

力扣链接：用栈实现队列

这个题目是用栈实现队列，我们依然使用C语言来写，C语言没有相应的库，所以我们还是要先手写一个栈才能实现题目中要求的函数接口。

方法：两个栈

一个队列是先进先出，一个栈是先进后出，新进的数据肯定是在栈底。我们可以这样做，指定一个栈专门进数据，指定另外一个栈专门出数据。

入队操作：向push栈中入数据。

 出对操作：将push栈中的数据全部倒入pop栈中，pop栈中数据的顺序刚好与push栈中的数据顺序相反，正好满足队列的性质，最后在push栈的栈顶出数据就行了。

 

 代码实现

创建两个栈

typedef struct {
    ST pushst;
    ST popst;
} MyQueue;

 指定一个栈专门进数据，指定另外一个栈专门出数据。

初始化

MyQueue* myQueueCreate() {
    MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&obj->pushst);
    StackInit(&obj->popst);
    return obj;
}

销毁队列

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->popst);
    StackDestroy(&obj->pushst);
    free(obj);
}

初始化和销毁队列的方法和上面题目的方法一致，就不多讲了。

入队

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

 入对只需要push进栈就行啦。

出队

int myQueuePop(MyQueue* obj) {
    if(StackEmpty(&obj->popst))
    {
        //如果pop栈为空，则把push栈的数据倒过来
        while(!StackEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,StackTop(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    int front=StackTop(&obj->popst);
    StackPop(&obj->popst);
    return front;
}

 首先要判断一下popst栈为不为空，如果为空，则把push栈的数据倒过来，不为空就直接在pop栈出数据。

取对头元素

int myQueuePeek(MyQueue* obj) {
     if(StackEmpty(&obj->popst))
    {
        //如果pop栈为空，则把push栈的数据倒过来
        while(!StackEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,StackTop(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    return StackTop(&obj->popst);
}

 这个就简单了，只需要取pop栈的栈顶的数据返回就可以了。

判空

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->popst)&&StackEmpty(&obj->pushst);
}

两个栈等于一个队列，所以两个栈都需要判空。 和上面的题目一样。

完整代码

 
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;
 
//初始化栈
void StackInit(ST* ps);
 
//销毁栈
void StackDestroy(ST* ps);
 
//进栈
void StackPush(ST* ps, STDataType x);
 
//出栈
void StackPop(ST* ps);
 
//获取栈顶元素
STDataType StackTop(ST* ps);
 
//判空
bool StackEmpty(ST* ps);
 
//栈的元素个数
int StackSize(ST* ps);
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
 
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
 
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType)* newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
 
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}
 
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}
 
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
 
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
 
typedef struct {
    ST pushst;
    ST popst;
} MyQueue;
 
 
MyQueue* myQueueCreate() {
    MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&obj->pushst);
    StackInit(&obj->popst);
    return obj;
}
 
void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushst,x);
}
 
int myQueuePop(MyQueue* obj) {
    if(StackEmpty(&obj->popst))
    {
        //如果pop栈为空，则把push栈的数据倒过来
        while(!StackEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,StackTop(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    int front=StackTop(&obj->popst);
    StackPop(&obj->popst);
    return front;
}
 
int myQueuePeek(MyQueue* obj) {
     if(StackEmpty(&obj->popst))
    {
        //如果pop栈为空，则把push栈的数据倒过来
        while(!StackEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,StackTop(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    return StackTop(&obj->popst);
}
 
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->popst)&&StackEmpty(&obj->pushst);
}
 
void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->popst);
    StackDestroy(&obj->pushst);
    free(obj);
}

总结：这两个题目是很相似的，你会写其中一个，那么另一个也不是什么难事。