利用栈和队列将队列中的元素逆置☆

  • Post author:
  • Post category:其他


题目:有一个队列和一个栈,设计一个算法是队列中的元素逆置。

分析:

我们可以一次取出队列中的元素放到栈中,然后在依次取出入队。

代码:

struct Stack
{
	int* arr;	//内存首地址
	int  len;	//栈的容量
	int top; 	//栈的下标
};
struct Squeue {//这里我才用的是循环队列,也可以不用循环队列
	int *arr;
	int front, rear;
};
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int main() {
	struct Squeue *sq;
	struct Stack *s;
	int n,data;
	Squeue *createQueue(int );
	bool enQueue(Squeue *,int,int);
	bool deQueue(Squeue *,int *,int);
	void printQ(Squeue *, int );
	Stack *createStack(int );
	bool push(Stack *,int );
	bool pop(Stack *);
	int *top(Stack *);

	printf("请输入队列及栈大小:");
	scanf("%d",&n);
	sq = createQueue(n+1);//因为是循环队列,需要留一个空间作为满空判定
	s = createStack(n);
	for (int i = 0; i < n;i++) {
		printf("请输入第%d个入队元素:",i+1);
		scanf("%d",&data);
		enQueue(sq,data, n + 1);//入队
	}
	printf("原队列中元素为:");
	printQ(sq,n+1);
	printf("\n");
	for (int i = 0; i < n;i++) {
		deQueue(sq,&data, n + 1);//出队
		push(s,data);//入栈
	}
	for (int i = 0; i < n; i++) {
		data = *top(s);
		pop(s);//出栈
		enQueue(sq,data, n + 1);//入队
	}
	printf("逆转后队列中元素为:");
	printQ(sq, n + 1);


}

队列相关代码如下:

#include <stdio.h>
#include <stdlib.h>
#define TYPE int 
struct Squeue {
	TYPE *arr;
	TYPE front, rear;
};

//创建队列
Squeue *createQueue(int n) {
	struct Squeue *sq = (struct Squeue *)malloc(sizeof(struct Squeue));
	sq->arr = (TYPE *)malloc(sizeof(TYPE)*n);//数组大小
	sq->front = 0;
	sq->rear = 0;
	return sq;
}
//判断队满(这里采用牺牲一个存储单元来实现,约定队头指针在队尾指针的下一个位置作为队满的标志)
bool isFull(Squeue *sq,int maxSize) {
	return (sq->rear + 1) % maxSize == sq->front;
}
//判断队空
bool isEmpty(Squeue *sq) {
	return sq->front == sq->rear;
}
//判断队列中元素个数
int count(Squeue *sq,int maxSize) {
	return (sq->rear - sq->front + maxSize) % maxSize;
}
//入队
bool enQueue(Squeue *sq,int data,int maxSize) {
	if (isFull(sq,maxSize)) return false;
	sq->arr[sq->rear] = data;
	sq->rear = (sq->rear + 1) % maxSize;
	return true;
}
//出队
bool deQueue(Squeue *sq, int *data,int maxSize) {//data我最开始用的&data会报错,
	if (isEmpty(sq)) return false;
	*data = sq->arr[sq->front];
	sq->front = (sq->front + 1) % maxSize;
	return true;
}
//打印队列中元素
void printQ(Squeue *sq,int maxSize) {
	if (isEmpty(sq)) return ;
	int np = sq->front;
	while (np!=sq->rear) {
		printf("%d ",sq->arr[np]);
		np = (np + 1) % maxSize;
	}
}

当我真心在追寻著我的梦想时,每一天都是缤纷的,因为我知道每一个小时,都是在实现梦想的一部分。



版权声明:本文为qq_36790381原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。