如何用顺序队列实现栈的逆置

Question

用顺序队列实现栈的逆置 按照图片上的要求实现 头文件已经有了 想看看主函数怎么实现

Answer 1

#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
 
 
 
//栈接口函数
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;
}

https://blog.csdn.net/RXY24601/article/details/127209676