【队列】4、利用栈逆置队列中的元素 - 《考研数据结构代码》

//createStack.cpp
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#define TYPE int
//#define TYPE biTree*
//#define TYPE char
//#define TYPE Recursion
struct biTree {
    char data;
    struct biTree *lchild;
    struct biTree *rchild;
};
struct Recursion {
    int no;
    int val;
};
struct Stack
{
    TYPE* arr;    //内存首地址
    int  len;    //栈的容量
    int top;     //栈的下标
};
/* --------------以下为实现函数--------------------*/
//创建一个栈
Stack *createStack(int size) {
    struct Stack *stack = (struct Stack*)malloc(sizeof(struct Stack));//给栈分配空间
    stack->arr = (TYPE *)malloc(sizeof(TYPE)*size);//给内存首地址分配空间，大小用户指定
    stack->len = size;//栈容量
    stack->top = -1;//栈顶下标，当前无元素，故为-1
    return stack;
}
//判断栈满
bool full(Stack *stack) {
    return stack->top + 1 >= stack->len;
}
//判断栈空
bool empty(Stack *stack) {
    return stack->top == -1;
}
//入栈
bool push(Stack *stack, TYPE p) {
    if (full(stack)) return false;
    *(stack->arr + ++stack->top) = p;
    return true;
}
//出栈
bool pop(Stack *stack) {
    if (empty(stack)) return false;
    stack->top--;
    return true;
}
//查看栈顶元素
TYPE top(Stack *stack) {
    if (empty(stack)) return NULL;
    return *(stack->arr + stack->top);
}
//销毁
void destory(Stack *stack) {
    free(stack->arr);
    free(stack);
}
//判断是否含有某个元素
bool contain(Stack *stack, TYPE r) {
    if (empty(stack)) return false;
    for (int i = stack->top; i >= 0; i--) {
        if (r == *(stack->arr + i) ){//疯了，我居然把==写成了=
            return true;
        }
    }
    return false;
}

//createSequentialQueue.cpp
/*
    此文件用于创建一个顺序队列，出队，入队,判断队空，判断队满等操作
*/
#include <stdio.h>
#include <stdlib.h>
//#define TYPE biTree* 
//#define TYPE char
#define TYPE int
struct biTree {
    char data;
    struct biTree *lchild;
    struct biTree *rchild;
};
struct Squeue {
    TYPE *arr;
    int 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, TYPE 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, TYPE *data,int maxSize) {
    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;
//    }
//}

/*
    有一个队列和一个栈，设计一个算法是队列中的元素逆置。
    分析：
        我们可以一次取出队列中的元素放到栈中，然后在依次取出入队。
*/
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);
}