`
xglv2013
  • 浏览: 38005 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Java实现判断入栈序列是否可以以某个序列出栈

阅读更多
输入第一个序列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
1
2
分享到:
评论

相关推荐

    Java写的一个进栈出栈的演示程序

    本程序的"汪秋云 MyStack.java"很可能是一个自定义的栈实现,可能包含了`push`和`pop`等基本操作,以及一些额外的功能,例如检查栈是否为空、获取栈的大小等。代码中可能会使用数组或者链表作为底层数据结构,并通过...

    java实现顺序栈

    Java实现顺序栈是一种常见的数据结构操作,主要用于存储和管理元素序列。栈是一种后进先出(LIFO,Last In First Out)的数据结构,通常用于执行回溯、递归等算法。在Java中,我们可以使用数组或ArrayList来实现顺序...

    使用进栈出栈的计算器程序

    在实际编程时,可以使用C++、Java、Python等语言来实现,利用这些语言提供的数据结构和控制流机制,编写出高效且易于理解的代码。在调试和优化过程中,可以利用单元测试和性能分析工具确保程序的正确性和效率。

    经典算法Java实现

    2. 队列和栈:基本操作如入队、出队、入栈、出栈,以及它们在算法中的应用。 3. 链表:单链表、双链表、循环链表及其操作。 4. 哈希表:快速查找和存储,解决查找、插入和删除操作的效率问题。 这些经典算法Java...

    java-leetcode面试题解Stack之第946题验证栈序列-题解.zip

    给定一个由整数组成的序列pushSeq,和另一个整数序列popSeq,如果可以通过对pushSeq进行入栈操作和popSeq进行出栈操作得到popSeq,那么返回true;否则返回false。每次入栈操作将一个元素添加到栈顶,每次出栈操作则...

    java五子棋

    这可以通过维护一个棋步栈来实现,每当玩家下棋,棋步就入栈;当悔棋时,将栈顶的棋步出栈并反向操作,还原棋盘状态。 存档和读档功能则是通过序列化和反序列化技术来实现的。Java提供了内置的序列化接口`...

    Java实现栈和队列面试题

    给定一个push序列和一个pop序列,判断是否能通过合法的push和pop操作得到。这通常涉及模拟栈操作的过程,检查pop序列是否是push序列的逆序。 以上就是Java实现栈和队列面试题的主要内容。理解和熟练掌握这些知识点...

    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...

    JAVA实验报告四(实现String类).doc

    - **使用ArrayList实现栈结构**:利用`ArrayList`的灵活性和高效性来构建栈,可以方便地实现入栈、出栈等操作。 - **实现深度复制**:为了确保复制后的栈与原栈完全独立,需要实现深度复制的功能,这样即使原栈发生...

    二叉树的遍历-java

    非递归实现通常使用栈来辅助,首先将根节点压入栈,然后不断出栈并访问节点,同时将其子节点(右子节点先入栈)压入栈,直到栈为空。 2. **中序遍历**: 中序遍历的顺序是:左子树 -> 根节点 -> 右子树。在二叉...

    全国计算机等级考试二级Java模拟试题9.pdf

    4. 快速排序中,第一趟划分以序列的第一个元素为基础,元素移动次数最多的序列通常是元素分布较为均匀的情况,因此答案C可能是最均匀的分布。 5. 面向对象编程中,对象间通信通过发送消息实现,因此选项D正确。 6....

    java数据结构和算法

    栈的主要操作有push(入栈)、pop(出栈)、peek(查看栈顶元素)等。 **队列(Queue)**: 队列是一种只允许在表的一端进行插入操作,在另一端进行删除操作的线性表,遵循先进先出(First In First Out,FIFO)的原则...

    数据结构(java版)习题解答

    **习9.1:判断一个数据序列是否为最小堆序列** - **题目**:判断一个序列是否构成最小堆。 - **解答**:遍历序列,确保每个父节点都不大于其子节点。 **习9.2:归并两条排序的单链表** - **题目**:合并两个已排序...

    java二级试卷密卷

    Java支持单一继承,即一个类只能继承一个父类,但可以实现多个接口。因此,选项**D**“java的单一继承使代码更可靠”是正确的。 **18. 访问修饰符** 为了使成员变量只能被同一包中的类访问,可以使用默认访问修饰...

    JAVA二级考试习题.doc

    17. 关于继承:Java不支持多重继承,但可以实现多个接口,D)java的单一继承使代码更可靠是正确的。 18. 访问修饰符:在同一包内的类可以访问没有修饰符的成员变量,答案B)无修饰符。 19. 访问成员变量:要使成员...

    线性表的6种结构JAVA源码.rar

    - **操作**:主要包含push(入栈)和pop(出栈)操作,时间复杂度为O(1)。 - **示例**:`AStack.java`可能是基于数组的栈实现,包括push、pop、peek等方法。 3. **队列**: - **概念**:队列是一种先进先出...

    JAVA版数据结构与算法(JAVA语言版解密)

    书中将讨论Java中的Stack类和Queue接口,以及如何实现它们的各种操作,如入栈、出栈、入队、出队等。 4. **树**:树是一种非线性的数据结构,包括二叉树、平衡树(如AVL树、红黑树)等。书中会详细讲解树的遍历...

    数据结构与算法java进阶(百度T5推荐)

    - 括号匹配检测:通过栈可以判断括号是否正确配对。 - 迷宫求解:使用栈可以辅助实现迷宫的深度优先搜索算法。 #### 第五章:递归 - **5.1 递归与堆栈** - 递归是一种调用自身的过程,可以简化问题的解决步骤。...

Global site tag (gtag.js) - Google Analytics