Java - sorted stack

TreeSet is a sorted set. Set means no duplicates though. add() adds an item, which is inserted in the correct sorted place. pollLast() removes and returns the last item, pollFirst() removes and returns the first item.

Java doesn't provide a PriorityStack, but you could easily write one by wrapping the PriorityQueue class and providing the push/pop methods to manage the underlying queue.

import java.util.Stack; public class Q6_SortStack { /** * @param args * Write a program to sort a stack in ascending order. * You should not make any assumptions about how the stack is implemented. * The following are the only functions that should be used to * write this program: push | pop | peek | isEmpty. */ public static void main(String[] args) { int[] array = {2,5,10,3,11,7,13,8,9,4,1,6}; Stack<Integer> s1 = new Stack<Integer>(); //int[] array = {2,4,1,6}; for(int i=0;i<array.length;i++){ s1.push(array[i]); } //displayStack(s1); displayStack(sortStack(s1)); } public static Stack<Integer> sortStack(Stack<Integer> s1){ Stack<Integer> s2 = new Stack<Integer>(); while(!s1.isEmpty()){ int temp = s1.pop(); while(!s2.isEmpty() && s2.peek()<temp){ s1.push(s2.pop()); } s2.push(temp); } return s2; } public static void displayStack(Stack<Integer> s){ while(!s.isEmpty()) System.out.print(s.pop()+"->"); System.out.println("end"); } } 

You can always use two data structures. A priority queue and a map. The first will let you get the smallest/largest item, and the second will let you search items fast. You just need to wrap them in the logic to keep them in sink (which shouldn't be too hard)

You could modify/overload the method you use to push data into your stack such that it inserts into the correct or "sorted" position. Otherwise, if you're implementing the stack using an array of some primitive datatype, you could use Arrays.sort(*Stack data array goes here*) from the java.util package every time you push data into the stack.