数据结构——队列

1.队列元素逆置

【问题描述】

已知Q是一个非空队列，S是一个空栈。仅使用少量工作变量以及对队列和栈的基本操作，编写一个算法，将队列Q中的所有元素逆置。

【输入形式】

输入的第一行为队列元素个数，第二行为队列从首至尾的元素

【输出形式】

输出队列的逆置

【样例输入】

3
1 2 3

【样例输出】

3 2 1

【评分标准】

需采用队列与栈的知识，否则不能得分

C语言

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 3000typedef struct {int data[MAX_SIZE];int front;int rear;
} Queue;void initQueue(Queue *q) {q->front = 0;q->rear = -1;
}int isEmpty(Queue *q) {return q->front > q->rear;
}void enqueue(Queue *q, int item) {if (q->rear == MAX_SIZE - 1) {printf("Error: Queue is full\n");exit(1);}q->rear++;q->data[q->rear] = item;
}int dequeue(Queue *q) {if (isEmpty(q)) {printf("Error: Queue is empty\n");exit(1);}int item = q->data[q->front];q->front++;return item;
}typedef struct {int data[MAX_SIZE];int top;
} Stack;void initStack(Stack *s) {s->top = -1;
}int isStackEmpty(Stack *s) {return s->top == -1;
}void push(Stack *s, int item) {if (s->top == MAX_SIZE - 1) {printf("Error: Stack is full\n");exit(1);}s->top++;s->data[s->top] = item;
}int pop(Stack *s) {if (isStackEmpty(s)) {printf("Error: Stack is empty\n");exit(1);}int item = s->data[s->top];s->top--;return item;
}void reverseQueue(Queue *q) {if (isEmpty(q)) {return;}Stack s;initStack(&s);while (!isEmpty(q)) {push(&s, dequeue(q));}while (!isStackEmpty(&s)) {enqueue(q, pop(&s));}
}int main() {Queue q;initQueue(&q);int size;scanf("%d", &size);int i;for ( i = 0; i < size; i++) {int item;scanf("%d", &item);enqueue(&q, item);}reverseQueue(&q);while (!isEmpty(&q)) {printf("%d ", dequeue(&q));}printf("\n");return 0;
}

C++

#include<stdio.h>
int main()
{int QUEUE[1000],STACK[1000],i,n,temp,top,front,rear;front=rear=top=-1;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&temp);rear++;QUEUE[rear]=temp;}for(i=0;i<n;i++){temp=QUEUE[++front];STACK[++top]=temp;}while(top!=-1){printf("%d ",STACK[top]);top--;}return 0;
}