栈、队列的应用(栈实现队列，队列实现栈，球钟问题）

栈、队列的应用 C语言

文章目录

- - 栈、队列的应用 C语言
  - - 1.用两个栈来实现一个队列
    - 2.用两个队列来实现一个栈
    - 3.球钟问题

1.用两个栈来实现一个队列

1.两个栈，s1，s2
2.入队：找到空s1栈，入栈，若无空栈，则出栈s1中的所有元素，存到另一栈s2中，再入栈s1。
3.出队：非空栈出栈。

#include 
#include 
#include 

typedef int DataType;

//数据节点结构体
typedef struct node
{
	DataType data;		//数据
	struct node *next;	//指针
}LinkNode;

//管理结构体
typedef struct stack
{
	struct node *top;		//栈顶偏移 栈顶指针就是节点指针的类型
	unsigned int size;				//当前元素个数
}Stack;


//初始化链式栈
Stack * InitStack()
{
	Stack * s = malloc(sizeof(Stack));
	if(s!=NULL)
	{
		s->top=NULL;
		s->size=0;
		return s;
	}
}

// 压栈、出栈、栈空判断
bool IsStackEmpty(Stack *s)
{
	return (s->size == 0);
}

bool push(Stack *s,DataType data)
{
	LinkNode *newNode = malloc(sizeof(LinkNode));
	if(newNode!=NULL)
	{
		//新节点初始化
		newNode->data = data;
		//新节点next指向原来栈顶
		newNode->next = s->top;
		//将栈顶设置为新节点
		s->top=newNode;
		//元素个数加1
		s->size++;
		return true;
	}
	return false;
}


bool pop(Stack *s,DataType *data)
{
	if(IsStackEmpty(s)||s==NULL)
	{
		return false;
	}
	//先拿到栈顶的数据
	*data = s->top->data;
	//将栈顶往后（向下）偏移一个
	s->top = s->top->next;
	//长度减1
	s->size--;
	return true;

}

void DisplayStack(Stack *s)
{
	LinkNode *tmp=s->top;
	int data;
	while(tmp!=NULL)
	{
		data = tmp->data;
		printf("%d ",data);
		tmp=tmp->next;
	}
	printf("n");
}


void Stack_2_EnQueue(Stack *s1,Stack *s2,DataType data)
{	
	int tmp;
	while(!IsStackEmpty(s2))
	{
		pop(s2,&tmp);
		push(s1,tmp);
	}
	push(s1,data);
}
void Stack_2_DeQueue(Stack *s1,Stack *s2,DataType *data)
{
	int tmp;
	while(!IsStackEmpty(s1))
	{
		pop(s1,&tmp);
		push(s2,tmp);
	}
	pop(s2,data);
}
void QueueDisplay(Stack *s1,Stack *s2)
{
	if(IsStackEmpty(s1))
		DisplayStack(s2);
	else
		DisplayStack(s1);
}

int main(int argc, char const *argv[])
{
	Stack *s1=InitStack();
	Stack *s2=InitStack();

	int num;
	DataType data;
	int mem = 0;
	while(1)
	{
		scanf("%d", &num);
		if (num > 0)
		{
			mem++;
			Stack_2_EnQueue(s1,s2, num);
			QueueDisplay(s1,s2);
		}
		else
			if (num < 0)
			{
				mem--;
				Stack_2_DeQueue(s1,s2, &data);
				printf("出队：%dn", data);
				QueueDisplay(s1,s2);
			}
			else
			{
				for (int i = 0; i < mem; ++i)
				{
					Stack_2_DeQueue(s1,s2, &data);
					printf("%d ", data);
				}
				mem = 0;
				printf("n");			
			}
	}
	return 0;
}

2.用两个队列来实现一个栈

1.两个队列q1，q2
2.入栈：若找到空队列q1，入队，否则清空队列q1，将元素存到q2，再入队q1.
3.出栈：非空队列出队。

#include 
#include 
#include 

typedef int DataType;


//队列节点
typedef struct node
{
	DataType data;
	struct node *next;
}LinkNode;

//管理结构体
typedef struct
{
	struct node *front;		//队头指针
	struct node *rear;		//队尾指针
	unsigned int size;		//当前元素个数
}LinkQueue;


//初始化
LinkQueue *InitLinkQueue(void)
{
	LinkQueue *q=(LinkQueue *)malloc(sizeof(LinkQueue));
	if(q!=NULL)
	{
		q->front=NULL;
		q->rear=NULL;
		q->size=0;
		return q;
	}
	return q;
}

//判断队空
bool IsQueueEmpty(LinkQueue *q)
{
	return (q->size == 0);
}

LinkNode *CreatNode(DataType data)
{
	LinkNode * newNode = (LinkNode *)malloc(sizeof(LinkNode));
	if(newNode!=NULL)
	{
		newNode->data=data;
		newNode->next=NULL;
		return newNode;
	}
}

//入队
bool EnQueue(LinkQueue *q,LinkNode *newNode)
{
	if(newNode == NULL)
		return false;
	if(IsQueueEmpty(q))
	{
		//第一个数据进来，那么队头和队尾都指向这个节点
		q->front=newNode;
		q->rear=newNode;
	}
	else
	{
		//将新节点按照链表尾插的方式加入链表
		q->rear->next = newNode;
		//new就要作为队的新队尾节点
		q->rear = newNode;
	}
	q->size++;
	return true;
}


//出队
bool DeQueue(LinkQueue *q,LinkNode **nodeData)
{
	if(IsQueueEmpty(q))
		return false;

	//将队头的数据拿到
	*nodeData = q->front;
	//队头要重新变到下一个节点
	q->front=q->front->next;
	q->size--;
	return true;
}

bool DeQueue1(LinkQueue* q, DataType *data)
{
	//队列为空
	if (IsQueueEmpty(q))
	{
		return false;
	}

	if (q->size == 1)
	{
		q->rear = NULL;
	}

	//将队头的数据拿到
	*data = q->front->data;
	//队头要重新变到下一个节点
	q->front = q->front->next;
	q->size--;
	return true;
}


//遍历链表
void Display(LinkQueue *q)
{
	LinkNode *tmp=q->front;
	while(tmp != NULL)
	{
		printf("%d ",tmp->data);
		tmp=tmp->next;
	}
	printf("n");
}


void Queue_2_Push(LinkQueue *q1,LinkQueue *q2,DataType data)
{
	LinkNode *tmp=NULL;
	if(IsQueueEmpty(q1))
	{
		EnQueue(q1,CreatNode(data));
		while(!IsQueueEmpty(q2))
		{
			DeQueue(q2,&tmp);
			EnQueue(q1,CreatNode(tmp->data));
		}
	}
	else
	{
		EnQueue(q2,CreatNode(data));
		while(!IsQueueEmpty(q1))
		{
			DeQueue(q1,&tmp);
			EnQueue(q2,CreatNode(tmp->data));
		}
	}

}
void Queue_2_Pop(LinkQueue *q1,LinkQueue *q2,DataType *data)
{
	LinkNode *tmp=NULL;
	if(!IsQueueEmpty(q1))
	{
		DeQueue(q1,&tmp);
	}
	else
	{
		DeQueue(q2,&tmp);
	}
	*data=tmp->data;

}

void DisplayStack(LinkQueue *q1,LinkQueue *q2)
{
	if(IsQueueEmpty(q1))
		Display(q2);
	else
		Display(q1);
}



int main(int argc, char const *argv[])
{
	LinkQueue *q1 = InitLinkQueue();
	LinkQueue *q2 = InitLinkQueue();



	int num;
	DataType data;
	int mem = 0;
	while(1)
	{
		scanf("%d", &num);
		if (num > 0)
		{
			mem++;
			Queue_2_Push(q1,q2, num);
			DisplayStack(q1,q2);
		}
		else
			if (num < 0)
			{
				mem--;
				Queue_2_Pop(q1,q2, &data);
				printf("出栈：%dn", data);
				DisplayStack(q1,q2);
			}
			else
			{
				for (int i = 0; i < mem; ++i)
				{
					Queue_2_Pop(q1,q2, &data);
					printf("%d ", data);
				}
				mem = 0;
				printf("n");			
			}
	}

	return 0;
}

3.球钟问题

球钟问题描述:球钟是一个利用球的移动来记录时间的简单装置。它有三个可以容纳若干个球的指示器：分钟指示器，五分钟指示器，小时指示器。若分钟指示器中有2个球，5分钟指示器中有6个球，小时指示器中有5个球，则时间为5:32。

工作原理:每过一分钟，球钟就会从球队列的队首取出一个球放入分钟指示器，分钟指示器最多可容纳4个球。当放入第五个球时，在分钟指示器的4个球就会按照他们被放入时的相反顺序加入球队列的队尾。而第五个球就会进入分钟指示器。按此类推，五分钟指示器最多可放11个球，小时指示器最多可放11个球。当小时指示器放入第12个球时，原来的11个球按照他们被放入时的相反顺序加入球队列的队尾，然后第12个球也回到队尾。这时，三个指示器均为空，回到初始状态，从而形成一个循环。因此，该秋种表示的时间范围是从00:00到11:59

要想表示00:00到12：00需要多少个球?假设，指示器都为空，球队列需要多长时间能回到原来的状态?

1.定义1个队列q，3个栈s1，s5，s60
2.s1存4个元素判断栈满然后入栈s5，将s1所有元素出栈，入队q
3.s5存11个元素判断栈满然后入栈s60，将s5所有元素出栈，入队q
4.s60存11个元素判断栈满，将s60所有元素出栈，入队q
5.判断q中的元素顺序

#include 
#include 
#include 
#include 
#include 

typedef int DataType;

//数据节点结构体
typedef struct node
{
	DataType data;		//数据
	struct node *next;	//指针
}LinkNode;


//管理结构体
typedef struct queue
{
	struct node *front;		//队头指针
	struct node *rear;		//队尾指针
	unsigned int size;		//当前元素个数
}LinkQueue;


//管理结构体
typedef struct stack
{
	struct node *top;		//栈顶偏移 栈顶指针就是节点指针的类型
	int size;				//当前元素个数
}Stack;


//初始化
LinkQueue *InitLinkQueue(void)
{
	LinkQueue *q=(LinkQueue *)malloc(sizeof(LinkQueue));
	if(q!=NULL)
	{
		q->front=NULL;
		q->rear=NULL;
		q->size=0;
		return q;
	}
	return q;
}

//判断队空
bool IsQueueEmpty(LinkQueue *q)
{
	return (q->size == 0);
}

LinkNode *CreatNode(DataType data)
{
	LinkNode * newNode = (LinkNode *)malloc(sizeof(LinkNode));
	if(newNode!=NULL)
	{
		newNode->data=data;
		newNode->next=NULL;
		return newNode;
	}
}

//入队
bool EnQueue(LinkQueue *q,LinkNode *newNode)
{
	if(newNode == NULL)
		return false;
	if(IsQueueEmpty(q))
	{
		//第一个数据进来，那么队头和队尾都指向这个节点
		q->front=newNode;
		q->rear=newNode;
	}
	else
	{
		//将新节点按照链表尾插的方式加入链表
		q->rear->next = newNode;
		//new就要作为队的新队尾节点
		q->rear = newNode;
	}
	q->size++;
	return true;
}


//出队
bool DeQueue(LinkQueue *q,LinkNode **nodeData)
{
	if(IsQueueEmpty(q))
		return false;

	//将队头的数据拿到
	*nodeData = q->front;
	//队头要重新变到下一个节点
	q->front=q->front->next;
	q->size--;
	return true;
}

bool DeQueue1(LinkQueue* q, DataType *data)
{
	//队列为空
	if (IsQueueEmpty(q))
	{
		return false;
	}

	if (q->size == 1)
	{
		q->rear = NULL;
	}

	//将队头的数据拿到
	*data = q->front->data;
	//队头要重新变到下一个节点
	q->front = q->front->next;
	q->size--;
	return true;
}


//遍历链表
void DisplayQueue(LinkQueue *q)
{
	int flag=0;
	LinkNode *tmp=q->front;
	while(tmp != NULL)
	{
		printf("%s%d",flag == 0?"":"-",tmp->data);
		flag=1;
		tmp=tmp->next;
	}
	printf("n");
}


Stack * InitStack()
{
	Stack * s = malloc(sizeof(Stack));
	if(s!=NULL)
	{
		s->top=NULL;
		s->size=0;
		return s;
	}
}

bool IsStackEmpty(Stack *s)
{
	return (s->size == 0);
}

bool push(Stack *s,DataType data)
{
	LinkNode *newNode = malloc(sizeof(LinkNode));
	if(newNode!=NULL)
	{
		//新节点初始化
		newNode->data = data;
		//新节点next指向原来栈顶
		newNode->next = s->top;
		//将栈顶设置为新节点
		s->top=newNode;
		//元素个数加1
		s->size++;
		return true;
	}
	return false;
}


bool pop(Stack *s,DataType *data)
{
	if(IsStackEmpty(s)||s==NULL)
	{
		return false;
	}
	//取出数据
	*data = s->top->data;
	//栈顶偏移指向上一个节点
	s->top = s->top->next;
	s->size--;
	return true;

}

void DisplayStack(Stack *s)
{
	LinkNode *tmp=s->top;
	int data;
	while(tmp!=NULL)
	{
		data = tmp->data;
		printf("%d ",data);
		tmp=tmp->next;
	}
	printf("n");
}

void Stack_pop_Enque(Stack *s,LinkQueue *q)
{
	int data;
	while(!IsStackEmpty(s))
	{
		pop(s,&data);
		EnQueue(q,CreatNode(data));
	}
}
bool CheckQueue(LinkQueue *q)
{
	if(IsQueueEmpty(q))
		return false;
	LinkNode *p=q->front;
	while(p->next!=NULL)
	{
		if(p->data > p->next->data)
		{
			return false;
		}
		p = p->next;
	}
	return true;
}

void show(Stack *s1,Stack *s5,Stack *s60,LinkQueue *q)
{
	system("clear");
	printf("s1ts5ts60n");
	LinkNode *tmp1=s1->top;
	LinkNode *tmp5=s5->top;
	LinkNode *tmp60=s60->top;
	for(int i=1;i<12;i++)
	{
		if (tmp1!=NULL)
		{
			printf("%d", tmp1->data);
			tmp1=tmp1->next;
		}
		printf("t");
		if (tmp5!=NULL)
		{
			printf("%d", tmp5->data);
			tmp5=tmp5->next;
		}
		printf("t");
		if (tmp60!=NULL)
		{
			printf("%d", tmp60->data);
			tmp60=tmp60->next;
		}
		printf("n");
	}
	DisplayQueue(q);
}

int main(int argc, char const *argv[])
{
	int tmp;
	int balls=27,i;
	int minutes=0;
	LinkQueue *q;
	Stack *s1,*s5,*s60;

	q = InitLinkQueue();
	s1 = InitStack();
	s5  = InitStack();
	s60 = InitStack();

	for(i=1;i<=balls;i++)
		EnQueue(q,CreatNode(i));
	
	// printf("%d",q->size);

	while(1)
	{
		show(s1,s5,s60,q);
		DeQueue1(q,&tmp);//出队一个球
		minutes++;
		usleep(1000*200);

		if(s1->size != 4) //栈没满，往里面放球
		{
			push(s1,tmp);
		}
		else
		{
			Stack_pop_Enque(s1,q);//球出栈入队
			if(s5->size!= 11)//栈没满，往里面放球
			{
				push(s5,tmp);
			}
			else
			{
				Stack_pop_Enque(s5,q);//球出栈入队
				if(s60->size!=11)
				{
					push(s60,tmp);
				}
				else
				{
					Stack_pop_Enque(s60,q);//球出栈入队
					EnQueue(q,CreatNode(tmp));//球入队
					if(CheckQueue(q))//球的顺序又变为了从小到大的顺序之后
						break;
				}
			}
		}			
		
	}
		
	printf("%dn",minutes);
	


	return 0;
}

33120

栈、队列的应用(栈实现队列，队列实现栈，球钟问题）

C/C++/C#相关栏目本月热门文章