What's the Big-O of a stack, queue, set, and deque?

Question

What is the Big-O efficiency of a stack, queue, set, and deque as it pertains to insertion, search, indexing, space, and deletion complexities?

Answer 1

This really depends on the implementation of each data structure. I'll go over a few, so you can get the idea of how to determine this.

Let's assume the Stack class is implemented using a Node (it can be implemented with an LinkedList, ArrayList, arrray, etc. as well).

Node top, bottom;
public Stack(Node n){
    top = bottom = n;
}

Stack has 3 primary methods: peek, push, and pop.

public int peek(){
    return top.value; //only return value
}

There wasn't much processing involved. It just returned a primitive value. This is O(1) for both time and space.

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

Still no real processing. This is O(1) for both time and space. Let's skip pop() and try something more interesting. Let's try a method called contains(int v). It will search the stack to see if it contains a Node which contains a value equal to v.

public bool contains(int v){
    Node current = top;
    while(current != null){
        if(current.value == v){
            return true;
        }
        current = current.next;
    }
    return false;
}

Basically we'll move through the Node references until we find the value or we reach the end. In some cases, you'll find value early and in some cases later down the road. However, we care about the worst case! The worst possible case would be we have to check every single Node. Say there are n Nodes, then we have O(n).

You can apply these analysis skills to the other data structures, so you can solve the rest yourself. It's not too bad. Good luck. :)