Algorithms for Complete Beginners : Array, Vector and Stack Data Structures

Part 5 : Array, Vector and Stack Data Structures

Part 1 : Introduction and Data Structures
Part 2 : Bubble Sort
Part 3 : Selection Sort
Part 4 : Insertion Sort


Hey,
Had to have some days break off [after the all hard work ;)]. So, lets move on, this time a little than practicals, but again these are more than important in solving the problems in the real world. As I said that will explain more about the different types of the data structures while we move on, here I'll explain 3 of the most basic data structures as we need them to continue with the algorithms. (please keep with ma paint drawings :D)

Array

   I'm not going to go through the "what's an array" stuff, as I'm damn sure than there's nothing to explain about it. But i guess a little about "how array works" is good for future references.

Array in the memory

  Arrays are really nice stuff, they are one of the most efficient data structures in inserting, retrieving, indexing data as it does those function in O(1) time. (you already know that it means with only 1 CPU call). So lets see how arrays do the magic. First hand remember that arrays are core data structures, or a structure that comes with the language, so it has the full CPU support over there unlike most of the other data structures.
Creating of an array has 3 steps:
1. Declaration
2. Construction
3. Initialization

There;s no point in explaining each step but rather here's a memory diagram [not an actual one] which represent an array of size 5, but only 4 are filled.

As you can see, the slots are already there waiting for numbers in the array, so you can see how it becomes both an advantage as well as a HUGE disadvantage.

Disadvantage:
1. You cannot increase / decrease the size of an array, once constructed
2. You cannot remove as element from an array, but you can put a null pointer or no value to it, but not removing item
3. You cannot insert an item in a place YOU LIKE, or more generally at a specific index. It's like what ever new you add, it goes to the end, unless you are overwritting an existing one.

So as for these things, new data structure were made, and Vector is one of the oldest to imerge, yet most used even now. Lets see how it differs.

Vector

What is a Vector?

Vector in common term is a super array (only from functionality basis). But in geek words, a Vector is an array with a dynamic size. Now what the hell? The concept is simple, instead of having a pre difined size to the structure it increases, decreases its size as you add/remove elements from/ to it. Which together gives as some other advantages as adding elements at a specific index and removing from a specific index. Yet sadly, vector is not as fast as the array, but altogether efficient.

This will be how a Vector with 4 elements looks like.

Practical Usage of Vector

In real world terms, once you get caught with the Vector, the next thing is that you will be using it for each and everything (which is not so good anyway). We'll go through some examples.

ex: Find the Highest Common Factor of 2 numbers.
As you see, for this the factors of the 2 numbers should be first stored in a structure and then compare, but you cannot use an array because you dont know how many factors are there for a specific number. So the simplest way would be to use a Vector (two vectors rather) and store for later use.

Vectors in C++

The STL (Standard Template Library)

The C++ creators are really awesome, because with time they managed to assemble a complete library of most common data structures,functions, algorithms and ship it with the C++ Compiler. This library is known as the Standard Template Library and contains a vast number of most useful stuff in day to day programming. As you have guessed, the Vector is one of them. Although it would be good if we implement our own Vector structure, only this time we'll skip because, practically their version is the best for the case :).

Refer the C++ documentation about vector data structure for full details

Vectors in Java

In Java too, as they ship a one BIG library (or package in their term) you have all the wanted data structures. (Even more than C++).But there are two structure doing the function of Vector in java.
1. Vector class
2. ArrayList

The ONLY difference between those 2 types are the Thread safety, that is all the methods in the Vector class is synchronized (if you are not the Java guy please scroll down FAST). As a matter of fact, in problem solving, when time is of greatest important dont use the Vector class instead use the ArrayList Class.

Java documentation for:
  1. Vector
  2. ArrayList

So there went the Vector thing but remember one thing, make sure you become EXTREMELY familiar with those data structure in the language you are working on. These are of immense importance.
We have one other, rather simple structure remaining. Stack.

Stack

What is a Stack?
As the name says, it is a Stack. Image a pile of books inside a box, so that if you add a new book it goes the very top and if you want to reach a certain book, you should keep removing all the book on top of it. These kind of structures are called, FILO (First-In-Last-Out) structures. (I call them unfair structures :D). So i guess you get the idea, if not here's what i've been trying to tell you.





Common now why to use the Stack when Vector are there?

Good point (although i myself asked it), the answer it there arent any good reason, but ease of use in manipulating in problem can be taken. That's sometimes, when you are deeply inside a problem, if the structure is having more than functions you need it drives you craZZzzy. For these instances putting up a mock layer saying "Stack" on a vector would be useful. Other than that Stacks help us to learn the Recursion algorithm (comes next) as this data structure is used in storing function call int the memory when a program is running. (that part on the Recursion part). Well for the time it is important to know how to implement a quick stack data structure using either Vector or Array as the base typer. (Note: If using an array, you would have to make it a fixed size stack)

For out convenience let's use Vector as the base type. A common Stack class should have following methods:
1. push(Object o) : Put  something onto the stack
2. pop() : pull out the top most something from the stack
3. size() : give the size of the stack
Before scrolling down, try to implement your own Stack, if you cant, common man you can :)

Stack Implementation in C++ using vector to store int

1. #include<iostream>
2. #include<vector>
4. using namespace std;
6. class Stack{
7.       private:
8.               vector<int> obj; //rememeber we are just making to store ints, but you can make this generic.
9.       public:
10.              void push(int);
11.              int pop();
12.              int size();    
13. };
15. void Stack::push(int no){
16.      obj.push_back(no); //We add the element to the abck of the vector
17. }
19. int Stack::pop(){
20.     //We should of course check whether our stack is empty before calling pulling out the element
21.     if(obj.size()!=0){
22.        int ele = obj.back();
23.        obj.pop_back();
24.        return ele;
25.     }else{
26.        cout << "Stack is empty!";
27.     }
28. }
30. int Stack::size(){
31.     return obj.size(); //Big deal hah?
32. }
34. int main(){
35.     Stack* stack = new Stack();
36.     stack->push(10);
37.     stack->push(20);
38.    
39.     cout << stack->size() << endl;
40.    
41.     stack->pop();
42.     cout << stack->size() << endl;
43.     stack->pop();
44.     cout << stack->size() << endl;
45.     stack->pop();
46.    
47. }

Stack Implementation in Java using ArrayList to store Integer(wrapper for int)

1. import java.util.ArrayList;
3. class Stack{
4.         private ArrayList<Integer> obj = new ArrayList<Integer>(); //In java rembemer we cannot use primitices in Collections
5.        
6.         public void push(int no){
7.                 obj.add(no); //We add the element to the abck of the vector
8.         }
9.        
10.         public int pop(){
11.                 //We should of course check whether our stack is empty before calling pulling out the element
12.                 if(obj.size()!=0){
13.                         return obj.remove(obj.size()-1);
14.                 }else{
15.                         System.out.println("Stack is empty!");
16.                         return 0;
17.                 }
18.         }
19.        
20.         public int size(){
21.                 return obj.size();
22.         }
23.        
24.         public static void main(String args[]){
25.                         Stack stack = new Stack();
26.                        
27.                         stack.push(10);
28.                         stack.push(20);
29.                        
30.                         System.out.println(stack.size());
31.                        
32.                         stack.pop();
33.                         System.out.println(stack.size());
34.                         stack.pop();
35.                         System.out.println(stack.size());
36.                         stack.pop();
37.                        
38.         }
39. }

Here's end of another somewhat tutorials, so till the next part you MUST keep practicing with those structures and of course read a lot about them (not that i did all these when my tutors told me :D) but it's good, believe me.

Next time ....