CS1020 StackSort Lab4 Ex3

Link to the question – StackSort Lab 4 Ex 3

import java.util.*;

class StackSort
{
	static Scanner sc = new Scanner(System.in);
	public static void main(String [] args)
	{
		int T = sc.nextInt();
		for(int i = 0; i < T; i++)
		{
			int N = sc.nextInt();
			ArrayList<Integer> A = new ArrayList<Integer>();
			System.out.println(solve(N));
		}
	}
	
	public static String solve(int N)
	{
		ArrayList<Integer> B = new ArrayList<Integer>();
		Stack J = new Stack();
		
		for(int i = 0; i < N; i++)
		{
			int input = sc.nextInt();
			if(J.empty())
			{
				J.push(input);
			}
			else
			{
				int top = (int)J.peek();
				//Check if first guy from A is smaller than top of Junction, add to top of Junction
				if(input <= top)
				{
					J.push(input);
				}
				else
				{
					//first guy is larger than top.
					//Add top of Junction to B
					//Check again if first guy is larger than top and repeat
					while(!J.empty() && (int)J.peek() < input)
					{
						if(B.size() != 0)
						{
							//the data are not sorted if last element is B is greater than the top of the stack
							if(B.get(B.size()-1) > (int)J.peek())
							{
								sc.nextLine();
								return "NO";
							}
						}
						B.add((int)J.pop());
					}
					J.push(input);
				}
			}
		}
		
		return "YES";
	}
}
Advertisements
This entry was posted in NUS, SoC and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s