What is Big-O stack, queue, set and deque?
It really depends on the implementation of each data structure. I'll go over a few so you can figure out how to define this.
Assume that Stack is implemented using class Node
(which can be implemented using LinkedList
, ArrayList
, arrray
etc.).
Node top, bottom;
public Stack(Node n){
top = bottom = n;
}
In the stack has 3 main methods: peek
, push
and pop
.
public int peek(){
return top.value; //only return value
}
Not much processing. It just returned the primitive value. It's O (1) for time and space.
public void push(Node n){
n.next = top;
top = n;
}
There is still no real processing. It's O (1) for time and space. Let it skip pop()
and try something more interesting. Try a method called contains(int v)
. It will search the stack to see if it Node
contains that contains the 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 will navigate through Node links until we find a value or reach the end. In some cases, you will find value early and in some cases later along the way. However, we take care of the worst case! In the worst case, we have to check each one Node
. Let's say there are n nodes , then we have O (n) .
You can apply these parsing skills to other data structures so that you can solve the rest of the problems yourself. It's not so bad. Good luck. :)
source to share
I've used this: http://bigocheatsheet.com/ but there is little to no information on why these large O values are used. You have to dig in and research this for yourself.
source to share
I'm surprised you couldn't find this information online.
There is a difference between the data structures that you listed in the question.
I'll start with the queue and stack data structure. Both the stack and the queue offer specialized access to data since there is no random access, only sequential. Therefore, you cannot talk about random access performance. In this case, any decent stack or queue implementation will offer O (1) access for insert and delete operations (in their respective form).
A set is a very different structure and its performance will largely depend on the underlying implementation. For example, you can implement a set using a base hash table for constant time insert, delete, and lookup operations, or you can implement it using a balanced search tree for O (log n).
source to share
The problem is that these data structures are usually implemented from the point of view of others. For example, it set
can be implemented as a hash table or using the red-black-tree algorithm.
The stack does not allow random access, but is often implemented as a block of memory (such as an array) with a single element pointing to the top of the stack that is updated for push
and operations pop
.
A queue
can be implemented as an array or linked list with very different insert, delete and indexing characteristics. A deque
will most likely be implemented as a linked list, but Microsoft's implementation in the C ++ standard library takes a hybrid approach (see What happens in the memory game? From std :: deque? ).
source to share
Big-O notation is usually reserved for algorithms and functions, not data types.
Also, the time complexity is very implementation dependent. Asking the complex complexity of Big-O "stop" data, as asking the complex complexity of Big-O "sorting". It all depends on the implementation. (More specifically, certain case-specific optimizations and requirements can significantly change the time complexity.)
If you want to use the C ++ STL as a reference implementation, you can find detailed information on the complexity of each of the datatypes you listed from here . Just search for data type and operation.
source to share