CareerCup

Stacks can be implemented using
1) vector
Complexity: pop is O(1). and for push, if resizing is needed O(N), otherwise, O(1). This approach uses not very memory efficient as vector occupy double the size of the number of elements.
2) Linked list:
Complexity is O(1) for push and pop. Memory efficient but the memory is not contiguous.
3) Deque (default implementation of the std library)
Complexity is O(1) for push and pop
Memory efficient (uses contiguous memory mostly, and may use dynamic memory if the size grows too large). Contiguous memory is not guaranteed.
4) Array (If the stack max size is known and fixed)
Complexity is O(1) for push and pop.

For unknown size stack, Deque is the most efficient approach regarding memory usage and complexity O(1) for insert and remove.

Linked List.
O(1) push, pop.

/*
 * Homemade implementation
 */
public class Stack {

	class Node{
		String val;
		Node next;
	}

	private Node top;

	public void push(Node n) {
		n.next = top;
		top = n;
	}

	//Returns null for empty list
	public Node pop() {
		Node t = top;
		top = top.next;
		return t;
	}

	public void toString() {
		Node c = top;
		System.out.println("[");
		while(c != null) {
			System.out.println(c.val + ", ");
			c = c.next;
		}
		System.out.println("]");
	}

}

It is implemented using deque (double-ended queue) which is implemented using vector of vectors. Thus you get constant time push and pop O(1).
[If you use linked list how would you get O(1) for push and pop??]

we can use push front and pop front of a list STL container to achieve this

Constant Time O(1).

import java.util.*;
public class Stack {

	public static LinkedList<String> l = new LinkedList<String>();
	
	public static void push(String s, LinkedList<String> l){
		
		l.add(s);
	}
	
	public static String pop(LinkedList<String> l){
		
		String s = l.getLast();
		l.removeLast();
		return s;
		
	}
	
	public static void main(String[] args) {
		
		push("a",l);
		push("b",l);
		push("c",l);
		push("d",l);
		pop(l);
		
		System.out.println("Contents of the Stack " + l);

	}

}