/*3)假设栈的输入序列为1、2、3、...、n，设计算法求出所有可能的出栈序列。
比如输入1、2、3、4、5，可能出栈的序列为12345、13452等42个。
*/
#include"Queue.h"
typedef struct sStack {
element data[max];
int top;
}seqStack;
void initialStack(seqStack& S) {
S.top = -1;
}
bool stackEmpty(seqStack& S) {
if (S.top == -1)
return true;
else
return false;
}
bool stackFull(seqStack& S) {
if (S.top == max - 1)
return true;
else
return false;
}
bool pushStack(seqStack& S, element x) {//入栈
if (stackFull(S))
return false;
else
{
S.top++;
S.data[S.top] = x;
return true;
}
}
bool popStack(seqStack& S, element& x) {//出栈
if (stackEmpty(S))
return true;
else {
x = S.data[S.top];
S.top--;
return true;
}
}
bool stackTop(seqStack& S, element& x) {//取栈顶元素
if (stackEmpty(S))
return false;
else {
x = S.data[S.top];
return true;
}
}
int fun(seQueue inQ, int n, seqStack& S, seQueue outQ) {
if (n <= 0 || queueEmpty(inQ) && queueEmpty(outQ) && stackEmpty(S)) {
return 0;
}
if (sizeQueue(inQ) == n) {
element x=0;//存放出队队列队头元素
while (!queueEmpty(outQ)) {
queueFront(outQ, x);
cout << x << " ";
outQueue(outQ);
}
cout << endl;
return 0;
}
//seqStack SCopy = S;
//seQueue QCopy = outQ;
element y;//存放栈顶元素
if (!stackFull(S)) {
stackTop(S, y);
enQueue(outQ, y);
popStack(S, y);
fun(inQ, n, S, outQ);
}
element z=0;//存放入队队列队头元素
if (!queueEmpty(inQ)) {
queueFront(inQ, z);
pushStack(S, z);
outQueue(inQ);
fun(inQ, n, S, outQ);
}
return 0;
}
int main() {
seQueue inQ, outQ;
seqStack S;
initialStack(S);
initQueue(inQ);
initQueue(outQ);
int n,a[100];
cout << "输入元素个数：";
cin >> n;
cout << "输入元素：" << endl;
for (int i = 0; i < n; i++) {
cin >> a[i];
enQueue(inQ, a[i]);
}
fun(inQ, n, S, outQ);
return 0;
}
头文件队列的相关运算如下
#include
#include
using namespace std;
#define max 100
typedef int element;
typedef struct sQueue {
element data[max];
int front;
int rear;
}seQueue;
void initQueue(seQueue& Q) {
Q.front = 0;
Q.rear = 0;
}
bool queueEmpty(seQueue& Q) {
if (Q.front == Q.rear)
return true;
else
return false;
}
void queueFront(seQueue& Q, element x) {//取队头元素
if (queueEmpty(Q))
cout << "队空，不可取队头元素！";
else
x=Q.data[(Q.front + 1) % max] ;
}
void enQueue(seQueue& Q, element x) {//入队
Q.rear = ((Q.rear) + 1) % max;
Q.data[Q.rear] = x;
}
void outQueue(seQueue& Q) {//出队
Q.front = (Q.front + 1) % max;
}
int sizeQueue(seQueue& Q) {//求队列中元素个数
return (Q.rear - Q.front+max) % max;
}
编译没有问题，运行时输完数后，按回车什么都输不出来，这个我感觉有点难对我来说，这种写法也只是看到一个人的博客尝试一下，但我真的希望能搞出来，麻烦帮我看看哪里不合适，哪怕只是很小的一个地方，我也会认真改正
这样写，死算：
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // 栈的最大长度
int stack[MAX_SIZE]; // 栈
int top = -1; // 栈顶指针
void push(int value) { // 入栈
stack[++top] = value;
}
int pop() { // 出栈
if (top < 0) {
printf("Stack underflow!\n");
exit(1);
}
return stack[top--];
}
int is_empty() { // 判断栈是否为空
return top < 0;
}
void print_stack(int* output, int len) { // 输出栈
for (int i = 0; i < len; ++i) {
printf("%d ", output[i]);
}
printf("\n");
}
void backtrack(int* input, int n, int* output, int len, int* count) { // 回溯法
if (len == n) { // 找到一组出栈序列
print_stack(output, len);
(*count)++;
return;
}
for (int i = 0; i < n; ++i) {
int value = input[i];
if (top < 0 || value > stack[top]) { // 如果当前元素比栈顶元素大，就入栈
push(value);
backtrack(input, n, output, len, count);
pop(); // 回溯，弹出栈顶元素
}
}
}
int main() {
int n;
printf("Enter n: ");
scanf("%d", &n);
int* input = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; ++i) {
input[i] = i + 1;
}
int* output = (int*)malloc(n * sizeof(int));
int count = 0;
backtrack(input, n, output, 0, &count);
printf("Total: %d\n", count);
free(input);
free(output);
return 0;
}