写一c语言算法,(不妨取名为 stackToQueue)从一个栈创建一队列,使栈顶为队列的头,栈尾为队列的尾,算法最后要求使栈成为空栈
时间: 2024-12-06 08:23:47 浏览: 12
在C语言中,可以使用两个栈来实现这个转换过程,其中一个栈用于存储数据,另一个栈则作为临时辅助。栈顶到队列头的操作可以通过模拟出入队的过程来完成。以下是详细的步骤:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义栈结构体
typedef struct StackNode {
int data;
struct StackNode* next;
} StackNode;
// 创建新节点
StackNode* createStackNode(int data) {
StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 初始化栈
StackNode* initStack() {
StackNode* top = NULL;
return top;
}
// 入栈
void push(StackNode** top, int data) {
StackNode* newNode = createStackNode(data);
if (*top == NULL) {
*top = newNode;
} else {
newNode->next = *top;
*top = newNode;
}
}
// 出栈并返回顶部元素
int pop(StackNode** top) {
if (*top == NULL) {
printf("Stack is empty.\n");
exit(EXIT_FAILURE);
}
int data = (*top)->data;
StackNode* temp = *top;
*top = (*top)->next;
free(temp);
return data;
}
// 将栈转换为队列
QueueNode* stackToQueue(StackNode* sTop, QueueNode* qHead) {
// 使用辅助栈tempStack存放当前处理的栈元素
StackNode* tempStack = initStack();
while (sTop != NULL) {
push(&tempStack, sTop->data);
sTop = sTop->next;
}
// 现在tempStack栈顶就是我们想要移动到队列头部的数据
while (!isEmpty(tempStack)) {
qHead->data = pop(&tempStack);
qHead->next = initQueueNode(); // 假设队列节点初始化函数为initQueueNode()
qHead = qHead->next;
}
return qHead;
}
// 验证栈是否为空
int isEmpty(StackNode* top) {
return top == NULL;
}
int main() {
StackNode* stack = initStack();
// 填充栈...
QueueNode* queue = stackToQueue(stack, NULL); // 初始化空队列
// 队列已转换好,现在栈为空
return 0;
}
```
阅读全文