输入第一个序列inSequence,是车厢入栈顺序
输入第二个序列outSequence,是车厢出栈顺序
算法判断以inSequence入栈的车厢可否以outSequence的顺序出栈
若可以,则返回出入栈动作的顺序并打印YES
若不可以,则返回出入栈动作的顺序直到失败的车厢并打印NO
算法的图示:
带括号的数字代表步数,红叉代表出栈,入栈序列的指针需要左右移动故采用双向链表,出栈序列的指针只向右移动故采用单向链表
package train;
public interface AddDelete
{
void addNode(int addNumber);
void deleteTop();
}
package train;
public class BidirectionalLinkedList implements AddDelete
{
BidirectionalNode top;//stack top
BidirectionalNode headNode;
BidirectionalNode tail;
int nodeNumber;
public BidirectionalLinkedList()
{
headNode = new BidirectionalNode(0);
tail = headNode;
nodeNumber = 0;
}
public void addNode(int newNumber)
{
BidirectionalNode bn = new BidirectionalNode(newNumber);
if(nodeNumber == 0)
{
top = bn;
}
tail.next = bn;
bn.last = tail;
tail = bn;
nodeNumber++;
}
public void deleteTop()
{
if(top.last.equals(headNode))
{
top = top.next;
headNode.next = top;
if(top != null)
{
System.out.println("in");
top.last = headNode;
}
}
else
{
top.last.next = top.next;
if(top.next != null)
{
top.next.last = top.last;
}
top = top.last;
}
}
public int getNodeNumber()
{
return nodeNumber;
}
}
package train;
public class BidirectionalNode
{
int number;
BidirectionalNode next;
BidirectionalNode last;
public BidirectionalNode(int number)
{
this.number = number;
this.next = null;
this.last = null;
}
}
package train;
public class LinkedList implements AddDelete
{
Node top;//stack top
Node headNode;
Node tail;
int nodeNumber;
public LinkedList()
{
headNode = new Node(0);
tail = headNode;
nodeNumber = 0;
}
public void addNode(int newNumber)
{
Node bn = new Node(newNumber);
if(nodeNumber == 0)
{
top = bn;
}
tail.next = bn;
tail = bn;
nodeNumber++;
}
public void deleteTop()
{
headNode.next = top.next;
top = headNode.next;
nodeNumber--;
}
boolean isEmpty()
{
return nodeNumber == 0;
}
}
package train;
public class Node
{
int number;
Node next;
public Node(int number)
{
this.number = number;
this.next = null;
}
}
package train;
import java.io.IOException;
import java.io.InputStreamReader;
public class Demo
{
public static void readInSequence(AddDelete a, InputStreamReader in) throws NumberFormatException, IOException
{
int c;
StringBuffer sb = new StringBuffer();
while((c = in.read()) != -1)
{
char ch = (char)c;
if(ch == ' ')
{
if(sb.toString().trim().equals(""))
continue;
a.addNode(Integer.parseInt(sb.toString().trim()));
sb.delete(0, sb.length());
}
else if(ch == '\r')
{
if(!sb.toString().trim().equals(""))
a.addNode(Integer.parseInt(sb.toString().trim()));
break;
}
else
{
sb.append(ch);
}
}
}
public static void main(String[] args)
{
BidirectionalLinkedList inSequence = new BidirectionalLinkedList();
LinkedList outSequence = new LinkedList();
InputStreamReader inIn = new InputStreamReader(System.in);
InputStreamReader inOut = new InputStreamReader(System.in);
try
{
System.out.println("pls input inSequence:");
readInSequence(inSequence, inIn);
System.out.println("pls input outSequence:");
readInSequence(outSequence, inOut);
}
catch (NumberFormatException e)
{
e.printStackTrace();
}
catch (IOException e)
{
e.printStackTrace();
}
finally
{
try
{
if(inIn != null)
inIn.close();
if(inOut != null)
inOut.close();
}
catch (IOException e)
{
e.printStackTrace();
}
}
System.out.println("in");
while(inSequence.top != null)
{
if(inSequence.top.number != outSequence.top.number)
{
inSequence.top = inSequence.top.next;
System.out.println("in");
}
else
{
System.out.println("out");
inSequence.deleteTop();
outSequence.deleteTop();
}
}
if(outSequence.isEmpty())
{
System.out.println("YES");
}
else
{
System.out.println("NO");
}
}
}
程序的运行结果:
返回NO的例子:
返回YES的例子:
- 大小: 14.3 KB
- 大小: 7.8 KB
- 大小: 8.3 KB
分享到:
相关推荐
本程序的"汪秋云 MyStack.java"很可能是一个自定义的栈实现,可能包含了`push`和`pop`等基本操作,以及一些额外的功能,例如检查栈是否为空、获取栈的大小等。代码中可能会使用数组或者链表作为底层数据结构,并通过...
Java实现顺序栈是一种常见的数据结构操作,主要用于存储和管理元素序列。栈是一种后进先出(LIFO,Last In First Out)的数据结构,通常用于执行回溯、递归等算法。在Java中,我们可以使用数组或ArrayList来实现顺序...
在实际编程时,可以使用C++、Java、Python等语言来实现,利用这些语言提供的数据结构和控制流机制,编写出高效且易于理解的代码。在调试和优化过程中,可以利用单元测试和性能分析工具确保程序的正确性和效率。
2. 队列和栈:基本操作如入队、出队、入栈、出栈,以及它们在算法中的应用。 3. 链表:单链表、双链表、循环链表及其操作。 4. 哈希表:快速查找和存储,解决查找、插入和删除操作的效率问题。 这些经典算法Java...
给定一个由整数组成的序列pushSeq,和另一个整数序列popSeq,如果可以通过对pushSeq进行入栈操作和popSeq进行出栈操作得到popSeq,那么返回true;否则返回false。每次入栈操作将一个元素添加到栈顶,每次出栈操作则...
这可以通过维护一个棋步栈来实现,每当玩家下棋,棋步就入栈;当悔棋时,将栈顶的棋步出栈并反向操作,还原棋盘状态。 存档和读档功能则是通过序列化和反序列化技术来实现的。Java提供了内置的序列化接口`...
给定一个push序列和一个pop序列,判断是否能通过合法的push和pop操作得到。这通常涉及模拟栈操作的过程,检查pop序列是否是push序列的逆序。 以上就是Java实现栈和队列面试题的主要内容。理解和熟练掌握这些知识点...
设在栈中,由顶向下已存放元素c、b、a,在第4个元素d入栈之前,栈中元素可以出栈, 试问d入栈前后,不可能的出栈序列是____。 A、d c b a B、c b d a C、c a d b D、c d b a A 3.某二叉树结点的前序序列为E、A、C...
- **使用ArrayList实现栈结构**:利用`ArrayList`的灵活性和高效性来构建栈,可以方便地实现入栈、出栈等操作。 - **实现深度复制**:为了确保复制后的栈与原栈完全独立,需要实现深度复制的功能,这样即使原栈发生...
非递归实现通常使用栈来辅助,首先将根节点压入栈,然后不断出栈并访问节点,同时将其子节点(右子节点先入栈)压入栈,直到栈为空。 2. **中序遍历**: 中序遍历的顺序是:左子树 -> 根节点 -> 右子树。在二叉...
4. 快速排序中,第一趟划分以序列的第一个元素为基础,元素移动次数最多的序列通常是元素分布较为均匀的情况,因此答案C可能是最均匀的分布。 5. 面向对象编程中,对象间通信通过发送消息实现,因此选项D正确。 6....
栈的主要操作有push(入栈)、pop(出栈)、peek(查看栈顶元素)等。 **队列(Queue)**: 队列是一种只允许在表的一端进行插入操作,在另一端进行删除操作的线性表,遵循先进先出(First In First Out,FIFO)的原则...
**习9.1:判断一个数据序列是否为最小堆序列** - **题目**:判断一个序列是否构成最小堆。 - **解答**:遍历序列,确保每个父节点都不大于其子节点。 **习9.2:归并两条排序的单链表** - **题目**:合并两个已排序...
Java支持单一继承,即一个类只能继承一个父类,但可以实现多个接口。因此,选项**D**“java的单一继承使代码更可靠”是正确的。 **18. 访问修饰符** 为了使成员变量只能被同一包中的类访问,可以使用默认访问修饰...
17. 关于继承:Java不支持多重继承,但可以实现多个接口,D)java的单一继承使代码更可靠是正确的。 18. 访问修饰符:在同一包内的类可以访问没有修饰符的成员变量,答案B)无修饰符。 19. 访问成员变量:要使成员...
- **操作**:主要包含push(入栈)和pop(出栈)操作,时间复杂度为O(1)。 - **示例**:`AStack.java`可能是基于数组的栈实现,包括push、pop、peek等方法。 3. **队列**: - **概念**:队列是一种先进先出...
书中将讨论Java中的Stack类和Queue接口,以及如何实现它们的各种操作,如入栈、出栈、入队、出队等。 4. **树**:树是一种非线性的数据结构,包括二叉树、平衡树(如AVL树、红黑树)等。书中会详细讲解树的遍历...
- 括号匹配检测:通过栈可以判断括号是否正确配对。 - 迷宫求解:使用栈可以辅助实现迷宫的深度优先搜索算法。 #### 第五章:递归 - **5.1 递归与堆栈** - 递归是一种调用自身的过程,可以简化问题的解决步骤。...