【数据结构】用栈实现队列-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】用栈实现队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言：本节博客分享了用栈实现队列效果的思路以及代码，有需要借鉴即可。

1.题目及链接

LINK 【数据结构】用栈实现队列,数据结构,c语言,栈,队列

2.思路分析

如果要用栈实现队列，我们直到栈是先入后出的一个效果，所以我们可以用两个栈，这样逆转两次数不就是入栈之前数组的顺序嘛。下面是一些图辅助理解：

【数据结构】用栈实现队列,数据结构,c语言,栈,队列

3.代码示例


#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

//用数组的方式实现栈结构
typedef int STDateType;
typedef struct Stack
{
	STDateType* arr;
	int top;
	int capacity;
}ST;

//初始化与销毁
void StackInit(ST* ps);
void StackDestroy(ST* ps);

//入栈出栈
void StackPush(ST* ps,STDateType x);
STDateType StackTop(ST* ps);
void StackPop(ST* ps);

//统计与判断
bool StackEmpty(ST* ps);
int StackSize(ST* ps);

void StackInit(ST* ps)
{
	assert(ps);

	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

void StackDestroy(ST* ps)
{
	assert(ps);

	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
	ps = NULL;
}

void StackPush(ST* ps, STDateType x)
{
	assert(ps);
	
	if (ps->capacity == ps->top)
	{
		//初始值的情况
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDateType* temp = (STDateType*)realloc(ps->arr, newcapacity * sizeof(STDateType));
		if (temp == NULL)
		{
			perror("malloc fail!");
			exit(-1);
		}
		ps->arr = temp;
		ps->capacity = newcapacity;
	}

	ps->arr[ps->top++] = x;
}

void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);

	ps->top--;
}


STDateType StackTop(ST* ps)
{
	assert(ps);

	return ps->arr[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 pushtack;
    ST poptack;
} MyQueue;


MyQueue* myQueueCreate() {
    //首先要创建一个队列结构体
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    
    //对队列结构体中的栈做初始化调整
    StackInit(&obj->pushtack);
    StackInit(&obj->poptack);

    //返回
    return obj;
}

//将元素 x 推到队列的末尾
void myQueuePush(MyQueue* obj, int x) {
    //插入数据
    StackPush(&obj->pushtack,x);
}

//返回队列开头的元素
int myQueuePeek(MyQueue* obj) {
    //分两种情况:1.poptack为空2.poptack不为空
    if(StackEmpty(&obj->poptack))//为空需要导数据
    {
        while(!StackEmpty(&obj->pushtack))
        {
            int top = StackTop(&obj->pushtack);//取出push数据
            StackPop(&obj->pushtack);//删除pop数据
            StackPush(&obj->poptack,top);//放入push
        }
    }
    //poptack不为空
    return StackTop(&obj->poptack);
}

//从队列的开头移除并返回元素
int myQueuePop(MyQueue* obj) {
    int front = myQueuePeek(obj);//取出
    StackPop(&obj->poptack);//删除
    return front;//返回
}



//如果队列为空，返回 true ；否则，返回 false
bool myQueueEmpty(MyQueue* obj) {//两个都为空
    return StackEmpty(&obj->pushtack)&&StackEmpty(&obj->poptack);
}

//释放
void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->pushtack);
    StackDestroy(&obj->poptack);
    free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/