Question

c语言编程 数据结构题

设栈S和队列Q的初始状态是空，元素a b c d e f 是进栈顺序，一个元素出栈之后即刻进入队列Q，若出列顺序是b d f e c a。要求写出其实现的过程。拜托了！

Answer 1

栈先进后出，队列先进先出，队列的顺序等价于栈的出栈顺序。写了个简单的验证程序，初始的出栈顺序必须无误

#include <iostream>
using std::cout;

// iStack元素值有序，简化了编程，否则就要借助于下标的有序性
// 'g'作为一个额外的标记，取到此值时，表示所有元素都已入栈
char iStack[] = { 'a','b', 'c', 'd', 'e', 'f', 'g' };
char oStack[] = { 'b','d', 'f', 'e', 'c', 'a' };

int no = 1;

// sp用于指示iStack未入栈的元素
int sp = 0;

char Top()
{
	return iStack[sp];
}

// ch及之前元素入栈
void Push(char ch)
{
	char cc = Top();
	while (cc <= ch)
	{
		printf("(%2d) Push: \t%c\n", no++, cc);
		sp++;
		cc = Top();
	}
}

void Pop(char ch)
{
	if (ch >= Top())	// 当前要出栈的元素未入栈
		Push(ch);

	printf("(%2d) Pop: \t\t%c\n", no++, ch);
}

int main()
{
	int count = 0;
	int len = sizeof(oStack);

	//1
	printf("入栈顺序：\n");
	for (int i = 0; i < len; i++)
		printf("%c ", iStack[i]);
	printf("\n");

	//2
	printf("出栈顺序：\n");
	for (int i = 0; i < len; i++)
		printf("%c ", oStack[i]);
	printf("\n\n");

	//3
	printf("出入栈操作：\n");
	while (count < len)
	{
		Pop(oStack[count]);
		count++;
	}

	return 0;

}

追问

请问为什么无法编译？

Answer 2

可以用结构链表来实现栈和队列。
栈是后进先出。所以可以反向创建结构链表S，第一个创建的节点，作为尾节点，之后创建的节点作为新的首节点。(每次创建新节点，其next初始NULL，之前创建的结点next指针指向新结点)。这样就实现了入栈，出栈只要正常遍历链表，从首节点开始取(取一个，删一个)。
而队列先进先出，就更简单，直接创建正向链表Q，先创建的作为首节点，之后都是新的尾节点。出队列也是直接遍历链表，取一个删一个。
所以，这样出栈进队，只要遍历S取一个节点添加到Q中就可以了，反向也是一样。

Answer 3

?这是数据结构的题.解答：首先明确几个概念：栈是先进后出,队列是先进先出；题目中指定了进栈顺序,但没说要连续进栈.(下面箭头图中右代表栈底,左代表栈顶,队列同样)
假如栈的容量是1,则第一个出栈的肯定是a,不符合
假如栈的容量是2,则a、b进去,b出栈,c进栈,只能c先出栈,d不可能出队顺序在c前
假如栈的容量是3,分析过程如下
①S：b→a,b出栈,Q：b,S：a
②S：d→c→a,d、c依次出栈,Q：c→d→b,S：a
③S：f→e→a,f、e、a依次出栈,Q：a→e→f→c→d→b,S：null
④S：g,g出栈,Q：g→a→e→f→c→d→b,S：null
Q中元素依次出队,即b→d→c→f→e→a→g

Answer 4

S:空 Q:空
a 进栈 => S:a, Q:空
b 进栈 => S:ab, Q:空
b 出栈 进队列=> S:a, Q:b
c 进栈 => S:ac, Q:b
d 进栈 => S:acd, Q:b
d 出栈 进队列=> S:ac, Q:bd
f 进栈 => S:acf, Q:bd
f 出栈 进队列=> S:ac, Q:bdf
e 进栈 => S:ace, Q:bdf
e 出栈 进队列=> S:ac, Q:bdfe
c 出栈 进队列=> S:a, Q:bdfec
a 出栈 进队列=> S:空, Q:bdfeca
因此 Q队列为 ： bdfeca, 出队顺序是 bdfeca

Answer 5

假如栈的容量是2,则a、b进去,b出栈,c进栈,只能c先出栈,d不可能出队顺序在c前