|
题目要求：
通过队列先进先出的特性，实现将栈中的元素逆置
思路：
由于栈先进后出的特性与队列先进先出的特性，所以只需要将栈中元素储存在队列中后，在把队列中的元素储存会栈中。
代码实现：
#include
#include
#include
#include
//栈接口函数
typedef int STDataType;
typedef struct stack
{
size_t top;
size_t capacity;
STDataType* a;
}ST;
void StackInit(ST* ps)
{
assert(ps);
ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
if (ps->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
ps->capacity = 4;
ps->top = 0;
//初始top=0，意味着top指向栈顶元素的下一个
//初始top=-1，意味着top指向栈顶元素
}
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);//终止程序
}
else
{
ps->a = tmp;
ps->capacity *= 2;
}
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);//空栈时调用top直接终止程序报错
ps->top--;//直接将栈顶数据删除，下一次有数据入栈会覆盖top位置
}
STDataType StackTop(ST* ps)//取栈顶元素
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;//如果top为零，说明栈中没有元素，为空
//返回布尔值为1
}
//队列接口函数
typedef int QDataType;
typedef struct QueueNode//创建一个链表
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue//创建一个队列
{
QNode* head;//指向队头
QNode* tail;//指向队尾
}Queue;
void QueueInit(Queue* Q1);
void QueueDestory(Queue* Q1);
void QueuePush(Queue* Q1, QDataType x);//队尾入
void QueuePop(Queue* Q1);//队头出
QDataType QueueFront(Queue* Q1);
QDataType QueueBack(Queue* Q1);
int QueueSize(Queue* Q1);
bool QueueEmpty(Queue* Q1);
void QueueInit(Queue* Q1)
{
assert(Q1);
Q1->head = Q1->tail = NULL;
}
void QueueDestory(Queue* Q1)
{
assert(Q1);
QNode* cur = Q1->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
}
void QueuePush(Queue* Q1, QDataType x)
{
assert(Q1);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (Q1->tail == NULL)
{
Q1->head = Q1->tail = newnode;
}
else
{
(Q1->tail)->next = newnode;//在tail后插入新结点
Q1->tail = newnode;//将新结点变为为结点
}
}
void QueuePop(Queue* Q1)
{
assert(Q1);
assert(Q1->head);//保证队列存在，并且队列不为空
if (Q1->head->next == NULL)
{
free(Q1->head);
Q1->head = Q1->tail = NULL;//将队头队尾指针置空，避免野指针问题
}
else
{
QNode* next = Q1->head->next;
free(Q1->head);
Q1->head = next;
}
}
QDataType QueueFront(Queue* Q1)
{
assert(Q1);
assert(Q1->head);
return Q1->head->data;
}
QDataType QueueBack(Queue* Q1)
{
assert(Q1);
assert(Q1->tail);
return Q1->tail->data;
}
int QueueSize(Queue* Q1)
{
assert(Q1);
int size = 0;
QNode* cur = Q1->head;
while (cur)
{
++size;
cur = cur->next;
}
return size;
}
bool QueueEmpty(Queue* Q1)
{
assert(Q1);
return Q1->head == NULL;
}
//用队列将栈中元素逆置
void myreverse(ST* L1,Queue *Q1)
{
while (!StackEmpty(L1))
{
QueuePush(Q1,L1->top);//将栈中元素逐个插入队列中，用队列保存栈中数据
StackPop(L1);
}
while (!QueueEmpty(Q1))
{
StackPush(L1, Q1->head->data);
QueuePop(Q1);
}
}
int main()
{
ST L1;
StackInit(&L1);
StackPush(&L1, 1);
StackPush(&L1, 2);
StackPush(&L1, 3);
StackPush(&L1, 4);
StackPush(&L1, 5);
StackPush(&L1, 6);
while (!StackEmpty(&L1))//如果栈不为空则执行循环
{
printf("%d", StackTop(&L1));//每次输出栈顶元素
StackPop(&L1);//必须要先删除才能拿到下层数据，栈后进先出
}
StackPush(&L1, 1);
StackPush(&L1, 2);
StackPush(&L1, 3);
StackPush(&L1, 4);
StackPush(&L1, 5);
StackPush(&L1, 6);
printf("\n");
Queue Q1;
QueueInit(&Q1);
myreverse(&L1, &Q1);
while (!StackEmpty(&L1))//如果栈不为空则执行循环
{
printf("%d", StackTop(&L1));//每次输出栈顶元素
StackPop(&L1);//必须要先删除才能拿到下层数据，栈后进先出
}
StackDestory(&L1);
QueueDestory(&Q1);
return 0;
}
|