Data Structures - Stack

Sort a Stack

	public class Solution {
	public static void main(String args[]) {
	Stack<Integer> stack = new Stack<>();
	stack.push(1);
	stack.push(2);
	stack.push(5);
	stack.push(3);
	System.out.println(" Stack elements "+stack);
	sortStack(stack);
	System.out.println(" Stack elements after Sorting "+stack);
	}
	}
	private static void sortStack(Stack<Integer> stack) {
	if(stack==null||stack.isEmpty()) {
	return;
	}
	Integer element = stack.pop();
	sortStack(stack);
	insertAtBottom(stack,element);
	}
	private static void insertAtBottom(Stack<Integer> stack, Integer element) {
	if(stack.isEmpty() || stack.peek()<element) {
	stack.push(element);
	return;
	}
	Integer poppedElement = stack.pop();
	insertAtBottom(stack,element);
	stack.push(poppedElement);
	}

view raw Sort a Stack hosted with ❤ by GitHub

Reverse a Stack

	public class Solution {
	public static void main(String[] args) {
	Stack<Integer> stack = new Stack<>();
	stack.push(1);
	stack.push(2);
	stack.push(5);
	stack.push(3);
	System.out.println(" Stack elements "+stack);
	reverseStack(stack);
	System.out.println(" Stack elements after Reversing "+stack);
	}
	private static void reverseStack(Stack<Integer> stack) {
	if(stack==null || stack.isEmpty()) {
	return;
	}
	Integer element = stack.pop();
	reverseStackNew(stack);
	insertElementAtBottom(stack,element);
	}
	private static void insertElementAtBottom(Stack<Integer> stack, Integer element) {
	if(stack.isEmpty()) {
	stack.push(element);
	} else {
	Integer poppedElement = stack.pop();
	insertElementAtBottom(stack, element);
	stack.push(poppedElement);
	}
	}
	}

view raw Reverse a Stack hosted with ❤ by GitHub

Implement a Stack using Queue

	public class StackUsingSingleQueue {
	public static void main(String[] args) {
	StackUsingQueue stackUsingQueue = new StackUsingQueue();
	stackUsingQueue.push(1);
	stackUsingQueue.push(2);
	stackUsingQueue.push(3);
	System.out.println("Popped Element First "+ stackUsingQueue.pop());
	System.out.println("Popped Element Second "+ stackUsingQueue.pop());
	System.out.println("Popped Element Third "+ stackUsingQueue.pop());
	}
	}
	class StackUsingQueue {
	Queue<Integer> queue = new LinkedList<>();
	public void push(int element) {
	queue.add(element);
	for(int i=0;i<=queue.size()-1;i++) {
	queue.add(queue.poll());
	}
	}
	public int pop() {
	if(!queue.isEmpty()) {
	return queue.poll();
	}
	return -1;
	}
	}

view raw Stack implementation Using Single Queue hosted with ❤ by GitHub

Implement a Stack using Two Queues

	import java.util.LinkedList;
	import java.util.Queue;
	public class StackUsingTwoQueues {
	public static void main(String a[]) {
	StackUsingQueues stackUsingTwoQueues =
	new StackUsingQueues();
	stackUsingTwoQueues.push(1);
	stackUsingTwoQueues.push(2);
	stackUsingTwoQueues.push(3);
	int poppedElement =
	stackUsingTwoQueues.pop();
	System.out.println(" poppedElement "+poppedElement);
	int poppedElement2 =
	stackUsingTwoQueues.pop();
	System.out.println(" poppedElement "+poppedElement2);
	int poppedElement3 =
	stackUsingTwoQueues.pop();
	System.out.println(" poppedElement "+poppedElement3);
	}
	}
	class StackUsingQueues {
	Queue<Integer> q1 = new LinkedList<>();
	Queue<Integer> q2 = new LinkedList<>();
	public StackUsingQueues() {}
	public void push(int element) {
	q1.add(element);
	}
	public int pop() {
	if(q2.isEmpty()) {
	if(!q1.isEmpty()) {
	for(int i=0;i<q1.size();i++) {
	q2.add(q1.poll());
	}
	int element = -1;
	if(!q1.isEmpty()) {
	element = q1.poll();
	} else {
	return q2.poll();
	}
	swapQueues();
	return element;
	}
	} else {
	return q2.poll();
	}
	return -1;
	}
	private void swapQueues() {
	Queue<Integer> temp = null;
	temp = q1;
	q1 = q2;
	q2 = temp;
	}
	}

view raw Stack Implementation Using Two Queues hosted with ❤ by GitHub