温故而知新 -＞ 数据结构 -＞利用 栈 实现 队列 -＞ 程序实现1

温故而知新 -＞ 数据结构 -＞利用 栈 实现 队列 -＞ 程序实现1 温故而知新 -＞ 数据结构 -＞利用 栈 实现 队列 -> 程序实现1_利用结构体

本篇博客是基于 温故而知新 -＞ 数据结构 -＞ 线性表 -＞队列 && 栈 中利用 栈 实现 队列 的理论知识进行程序实现！

其中结合了 温故而知新-＞数据结构-＞栈-＞程序实现1_利用结构体 中的代码，实现了队列的 增（入队）删（出队）查（队头与队尾元素）改（没写(～￣▽￣)～），判空，打印等 *** 作！并附带了实例以及对应的运行结果！

注意：其中代码多多少少有点冗余，且未考虑性能最优，读者有兴趣可进一步精简！

具体内容如下
（1）newSQueue.h

#ifndef __NEWSQUEUE_H_
#define __NEWSQUEUE_H_

#include
#include
#include

typedef int STDataType;

//顺序结构实现：实现一个更简单的顺序表
typedef struct stack
{
	STDataType *_data;
	int _size;
	int _capacity;
}stack;

typedef struct
{
	struct stack st1;//入队栈
	struct stack st2;//出队栈
}MyQueue;

#endif

（2）main.c

#include"newSQueue.h"

void initStack(stack *st)
{
	//空栈
	if (st == NULL)
		return;
	st->_data = NULL;
	st->_size = st->_capacity = 0;
}

void checkCapacity(stack *st)
{
	if (st->_size == st->_capacity)
	{
		int newCap = st->_capacity == 0 ? 1 : 2 * st->_capacity;
		st->_data = (STDataType*)realloc(st->_data, sizeof(STDataType)*newCap);
		st->_capacity = newCap;
	}
}

void stackPush(stack *st, STDataType val)
{
	//尾插
	if (st == NULL)
		return;
	checkCapacity(st);
	st->_data[st->_size++] = val;
}

void stackPop(stack *st)
{
	//尾删
	if (st == NULL || st->_size == 0)
		return;
	--st->_size;
}

int stackSize(stack *st)
{
	if (st == NULL)
		return 0;
	return st->_size;
}

int stackEmpty(stack* st)
{
	if (st == NULL || st->_size == 0)
		return 1;//返回1为空
	else
		return 0;
	//return st->_size;
}

STDataType stackTop(stack *st)
{
	return st->_data[st->_size - 1];//栈顶元素
}

void stackPrint(stack *st)
{
	printf("栈内元素为：");
	int i = st->_size - 1;
	while (i >= 0)
	{
		printf("%d ", st->_data[i]);
		i--;
	}printf("n");
}

void stackDestory(stack *st)
{
	if (st)
	{
		if (st->_data)
		{
			free(st->_data);
			st->_data = NULL;
			st->_size = 0;
			st->_capacity = 0;
		}
	}

}

//栈实现队列：入队：入队栈的入栈
//			出队：出队栈：
//					非空：出栈
//					空：首先把入队栈元素存入出队栈，出队栈在进行出栈
MyQueue *myQueueCreate()
{
	MyQueue *q = (MyQueue *)malloc(sizeof(MyQueue));
	initStack(&q->st1);
	initStack(&q->st2);
	return q;
}

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

int myQueuePop(MyQueue *obj)
{
	int data;
	if (!stackEmpty(&obj->st1))
	{
		int n = stackSize(&obj->st1);
		while (n)//相当于 while (!stackEmpty(&obj->st1))
		{
			int data1 = stackTop(&obj->st1);
			stackPop(&obj->st1);
			stackPush(&obj->st2, data1);
			--n;
		}
		data = stackTop(&obj->st2);
		stackPop(&obj->st2);
	}
	else
	{
		data = stackTop(&obj->st2);
		stackPop(&obj->st2);
	}
	return data;
}

void myQueuePrint(MyQueue *obj)
{
	if (stackEmpty(&obj->st1) && stackEmpty(&obj->st2))
		return;
	if (!stackEmpty(&obj->st2))
	{
		stackPrint(&obj->st2);
	}
	if (!stackEmpty(&obj->st1))
	{
		stack tmp; 
		initStack(&tmp);
		while (!stackEmpty(&obj->st1))
		{
			stackPush(&tmp, stackTop(&obj->st1));
			stackPop(&obj->st1);
		}
		stackPrint(&tmp);
		while (!stackEmpty(&tmp))
		{
			stackPush(&obj->st1, stackTop(&tmp));
			stackPop(&tmp);
		}
		stackDestory(&tmp);
	}

}

STDataType myQueueFront(MyQueue *obj)
{
	if (stackEmpty(&obj->st1) && stackEmpty(&obj->st2))
		return NULL;
	if (stackEmpty(&obj->st2))//判断出队栈是否为空，空，则将入队栈的数据存入到出队栈
	{
		while (!stackEmpty(&obj->st1))
		{
			int data = stackTop(&obj->st1);
			stackPop(&obj->st1);
			stackPush(&obj->st2, data);
		}
	}
	return stackTop(&obj->st2);
}

STDataType myQueueRear(MyQueue *obj)
{
	if (stackEmpty(&obj->st1) && stackEmpty(&obj->st2))
		return NULL;
	if (!stackEmpty(&obj->st1))
		return stackTop(&obj->st1);
	stack tmp;
	initStack(&tmp);
	while (!stackEmpty(&obj->st2))
	{
		stackPush(&tmp, stackTop(&obj->st2));
		stackPop(&obj->st2);
	}
	STDataType t = stackTop(&tmp);
	while (!stackEmpty(&tmp))
	{
		stackPush(&obj->st2, stackTop(&tmp));
		stackPop(&tmp);
	}
	stackDestory(&tmp);
	return t;
}

bool myQueueEmpty(MyQueue *obj)
{
	return stackEmpty(&obj->st1) && stackEmpty(&obj->st2);
}

void myQueueDestory(MyQueue *obj)
{
	stackDestory(&obj->st1);
	stackDestory(&obj->st2);
	free(obj);
}

void test()
{
	MyQueue *mq = myQueueCreate();
	
	myQueuePush(mq, 1);
	myQueuePush(mq, 2);
	myQueuePush(mq, 3);
	myQueuePush(mq, 4);
	myQueuePrint(mq);// 1 2 3 4
	printf("n");

	
	myQueuePop(mq);
	myQueuePrint(mq);// 2 3 4
	myQueuePop(mq);
	myQueuePrint(mq);// 3 4
	//myQueuePop(mq);
	//myQueuePrint(mq);// 4
	//myQueuePop(mq);
	//myQueuePrint(mq);//不会打印，因为此时队列内无数据
	printf("n");

	
	printf("此时队头元素为：%d n", myQueueFront(mq));
	
	printf("此时队尾元素为：%d nn", myQueueRear(mq));

	
	printf("队列状态（0：非空，1：空）：%d n", myQueueEmpty(mq));
}

int main()
{
	test();

	system("pause");
	return 0;
}

（3）运行结果

以上为本篇博客内容，欢迎与笔者交流！
侵权删~