8 Replies - 6178 Views - Last Post: 09 February 2010 - 10:42 AM Rate Topic: -----

#1 Djhar  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 35
  • Joined: 24-January 10

Sorting Stacks

Posted 08 February 2010 - 06:38 PM

Hey guys, I'm having trouble with answering this question:

Put the elements on the stack S in ascending order using one additional stack and some additional non-array variables.

Here's my code thus far:

class Stack<T>
{
	private java.util.ArrayList<T> pool = new java.util.ArrayList<T>();

	public void push(T el)
	{
		pool.add(el);
	}

	public T pop()
	{
		if(!pool.isEmpty())
		return pool.remove(pool.size()-1);
		else return null;
	}

	public T topEl()
	{
		if(isEmpty())
		return pool.get(pool.size()-1);
		else return null;
	}

	public boolean isEmpty()
	{
		return pool.isEmpty();
	}

	public void clear()
	{
		pool.clear();
	}

	public String toString()
	{
		return pool.toString();
	}
}

class Test2
{
	public static void main(String[] arg)
	{
		Stack<Integer> s = new Stack<Integer>();

		s.push(2);
		s.push(0);
		s.push(9);
		s.push(5);
		s.push(7);
		s.push(3);
		s.push(1);
		s.push(10);
		s.push(6);
		s.push(4);
		s.push(8);

		System.out.println(s);

		Stack<Integer> newstack = new Stack<Integer>();

		for(int i=0;i<=10;i++)
		{
		int temp = s.pop();
		newstack.push(temp);

		if(newstack.pop() < s.pop())
		{
			int temp2 = newstack.pop();
			newstack.push(temp2);
		}
		else
		{
			int temp2 = s.pop();
			s.push(temp2);
		}

		System.out.println(newstack);
		}
	}
}



I'm sure my sort method isn't the right one but any help is highly appreciated

Is This A Good Question/Topic? 0
  • +

Replies To: Sorting Stacks

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10771
  • View blog
  • Posts: 40,107
  • Joined: 27-December 08

Re: Sorting Stacks

Posted 08 February 2010 - 06:50 PM

Edit: Whoops I completely didn't read that "Use an additional Stack" part. My mistake. You might consider using an Insertion Sort principle, meaning grab the popped element and place it in the correct sequence amongst the elements. This will require a lot of juggling between the two Stacks.

This post has been edited by macosxnerd101: 08 February 2010 - 06:57 PM

Was This Post Helpful? 1
  • +
  • -

#3 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8343
  • View blog
  • Posts: 31,890
  • Joined: 06-March 08

Re: Sorting Stacks

Posted 08 February 2010 - 06:54 PM

If your class T implements Comparable (like String does) then it is easy to can call Collections.sort()

		ArrayList<String> al = new ArrayList<String>();
		al.add("aaa");
		al.add("zzz");
		al.add("iii");
		Collections.sort(al);
		System.out.println(al);


will print
[aaa, iii, zzz]
Was This Post Helpful? 1
  • +
  • -

#4 Djhar  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 35
  • Joined: 24-January 10

Re: Sorting Stacks

Posted 08 February 2010 - 06:59 PM

Hey there Mac and Paul, thank you so much for the response. It's just a simple homework response, not a full program this time around. My professor specifically wants there to be another stack to sort the original stack. Sorry if I sound blunt =/ I understand efficiency is key in programming but during this time around, it's seems it's more about understand how to write out a simple concept.

If I use Collections.sort(), I understand it'll be much more efficient but I just want to stay safe and stick to sorting a stack using another stack.

This post has been edited by Djhar: 08 February 2010 - 07:03 PM

Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10771
  • View blog
  • Posts: 40,107
  • Joined: 27-December 08

Re: Sorting Stacks

Posted 08 February 2010 - 07:24 PM

View Postmacosxnerd101, on 08 February 2010 - 09:50 PM, said:

Edit: Whoops I completely didn't read that "Use an additional Stack" part. My mistake. You might consider using an Insertion Sort principle, meaning grab the popped element and place it in the correct sequence amongst the elements. This will require a lot of juggling between the two Stacks.


I caught that mistake probably right as you were posting, so you might have missed my edit. You might consider using the Insertion Sort algorithm for this task.
Was This Post Helpful? 0
  • +
  • -

#6 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5901
  • View blog
  • Posts: 12,805
  • Joined: 16-October 07

Re: Sorting Stacks

Posted 08 February 2010 - 07:28 PM

It late, but I loved this one. The other kids aren't understanding the game. It's like Towers of Hanoi, only simple.

Basically, you pop your stack into another stack until you hit a number that isn't in order. Then pop the offending value and push back into the stack, placing the value back in the order. You repeat this process until you can pop the entire stack and it's in order.

I wrote a solution, because it was fun. Please take a stab at your own. Hope this helps.

import java.util.*;

class Stack<T extends Comparable<T>> {
	private java.util.ArrayList<T> pool = new java.util.ArrayList<T>();

	public void push(T el) { pool.add(el); }

	public T pop() {
		if(isEmpty()) { return null; }
		return pool.remove(pool.size()-1);
	}

	public T topEl() {
		if(isEmpty()) { return null; }
		return pool.get(pool.size()-1);
	}

	public boolean isEmpty() { return pool.isEmpty(); }

	public void clear() { pool.clear(); }

	public String toString() {
		return pool.toString();
	}
	
	public void Sort() {
		if(isEmpty()) { return; }
		boolean flag = true;
		while(flag) {
			flag = false;
			Stack<T> other = new Stack<T>();
			other.push(this.pop());
			while(!isEmpty() && this.topEl().compareTo(other.topEl())>0) {
				other.push(this.pop());
			}
			if (!isEmpty()) {
				flag = true;
				T misfit = this.pop();
				while(!other.isEmpty() && misfit.compareTo(other.topEl())<0) {
					push(other.pop());
				}
				push(misfit);
			}
			while(!other.isEmpty()) { push(other.pop()); }
		}
	}
}

class Test2 {
	public static void main(String[] arg) {
		Stack<Integer> s = new Stack<Integer>();

		s.push(2);
		s.push(0);
		s.push(9);
		s.push(5);
		s.push(7);
		s.push(3);
		s.push(1);
		s.push(10);
		s.push(6);
		s.push(4);
		s.push(8);

		System.out.println(s);
		s.Sort();
		System.out.println("---------");
		System.out.println(s);
	}
}



Oh, yeah, your "topEl" was off. Also, note the Comparable requirement.
Was This Post Helpful? 1
  • +
  • -

#7 Djhar  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 35
  • Joined: 24-January 10

Re: Sorting Stacks

Posted 08 February 2010 - 07:35 PM

Wowzers, I can't thank you all enough for the help. The clouds in my mind have been cleared up! :bananaman: Thank you so much once again and have a good one :bigsmile:
Was This Post Helpful? 0
  • +
  • -

#8 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5901
  • View blog
  • Posts: 12,805
  • Joined: 16-October 07

Re: Sorting Stacks

Posted 09 February 2010 - 04:54 AM

Glad it helped, and made sense.

Upon further consideration, and some sleep, I'm not fond of the sort I offered. I believe a pure bubble sort makes more sense than the odd hybrid I came up with the night before.

Here's a simple bubble sort:
public void Sort() {
	if(isEmpty()) { return; }
	
	boolean flag = true;
	while(flag) {
		flag = false;
		Stack<T> other = new Stack<T>();
		other.push(this.pop());
		while(!isEmpty()) {
			if (this.topEl().compareTo(other.topEl())<0) {
				other.push(this.pop());
			} else {
				T temp = other.pop();
				other.push(this.pop());
				other.push(temp);
				flag = true;
			}
		}
		while(!other.isEmpty()) { push(other.pop()); }
	}
}


Was This Post Helpful? 1
  • +
  • -

#9 Djhar  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 35
  • Joined: 24-January 10

Re: Sorting Stacks

Posted 09 February 2010 - 10:42 AM

After the post last night, I spent from 1:30 AM till around 3:00 AM trying to decipher your code and making it simpler for me to understand and ended up back making it into a code very similar to the one you just posted. I felt your first code wasn't going to get me very far in understanding the method because when I got to the "compareTo" parts, I just collapsed XD My mind was literally fried from over-thinking the program.

When I first saw "ascending order" in the question, I immediately thought of an if else statement and while writing it out, it reminded me of when I used bubble sort in an extremely similar case during my C++ course. I'm very thankful that you posted again baavgai because now I know that the track I was approaching was the right one! Thank you once again and to everyone who helped! Glad to see there are very helpful people in this community. :bigsmile:

This post has been edited by Djhar: 09 February 2010 - 11:03 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1