4. Creating a Stack

Stack is an abstract data type that allows you to input and output data in a way that the first data which was placed in the stack will be the last one to get out. We use physical examples of stack in our daily lives such as the stack of dishes or stack of coins where you only add or remove objects from the top of the stack. The picture below gives a clearer concept of a stack.

You can see that there is only one end to input and output data, the top of the stack. The first data input was the last to be output, which makes stack a last in first out (LIFO) data structure.

In this tutorial we will make a stack which will store integers and then we will try to make it generalized using templates. Stack has three main functions, namely, push, pop and stackTop, push inserts the data into the stack and pop removes the data from the top of the stack and returns it to the calling object, whereas stackTop returns the data on the top of the stack to the calling object without removing it from the stack.

Stack consists of nodes each node has two members a data and a pointer to next node. The code below implements the class Node.

class Node
{
public:
int Data;
Node *nextptr;
};

Now we shall implement the stack class, every stack has a pointer to the top most node when the stack is empty the top pointer is NULL, as soon as the node is inserted the top pointer points to the new node, whenever a node is deleted the pointer points to the next node in the stack if the stack is not empty. We can and we should keep a count of nodes in a stack so another member of the stack class is the count variable, which keeps the records of the number of nodes present in the stack, six member functions are implemented, push, pop, stackTop (already discussed above), Destroy which destroys the stack by removing all its nodes and releasing the memory, isEmpty tells whether the stack is empty or not and stackCount, returns the number of nodes in the stack.

Consider the code below which implements the stack class.

class stack
{
private:
int count;
Node *top;
public:

stack()//constructor initializing the members
{
top=0;
count=0;
}

bool Push(int D)
{
Node *newNode = new Node; //acquiring memory for new node
if(newNode==NULL) return 0; //returns 0 if not successful
newNode->Data=D; //assigning data to the new node
newNode->nextptr=top; //linking new node to the next pointer
top=newNode; //pointing top to the new node
count++; //incrementing count
return 1; //returns 1 if successful
}

int Pop()
{
if(count==0) return 0; //checks whether stack is empty
Node *temp=top; //points temp to the top
top=top->nextptr; // points top to the next node in stack
int D=temp->Data; //assigning data value to D
delete temp; //deleting top node
count--; //decrementing count
return D; //returning data
}

int stackTop()
{
//checks whether the stack is empty if not
//then returns the data at the top
if(count!=0) return top->Data; else return 0;
}

//function which checks whether the stack is empty or not
bool isEmpty(){if(count=0) return 1; else return 0;}

//returns the number of nodes present in the stack
int stackCount(){return count;}

void Destroy()
{
if(count!=0)//if stack is not empty
{
while(top!=0)//while top is not equal to null
{
Node *temp=top;//points temp to top
top=top->nextptr;//points top to the next node
delete temp;//deleting the top node
}
count=0;//setting count to zero
}
}

~stack()//destructor
{
Destroy();
}

};

Now we shall see how do we use our class, consider the code below which adds and removes some data from the stack showing how each of the function works.

#include <iostream>

//class code goes here

int main()
{
stack s1;
s1.Push(1);
s1.Push(2);
s1.Push(4);
cout<<"Count : "<<s1.stackCount();//count is 3
//4 will be displayed as it was the last input
cout<<"\nPop function called : "<<s1.Pop();
//count decreased to 2
cout<<"\nCount : "<<s1.stackCount()<<endl;
system("pause");
}

Stack has various applications one the most common uses is to reverse the order of the data, as we just saw this is what stack is known for, it is also used for backtracking in computer games and various other applications. Converting an infix expression to a postfix expression and evaluating a post fix expressions are two common tasks easily accomplished by stack.

A generalized implementation of stack is shown below using templates.

#include <iostream>
using namespace std;
template <class Type>
class Node
{
public:
Type Data;
Node *nextptr;
};
template <class Type>
class stack
{
private:
int count;
Node<type> *top;
public:
stack()
{
top=0;
count=0;
}
bool Push(Type D)
{
Node<type> *newNode = new Node<type>;
if(newNode==NULL) return 0;
newNode->Data=D;
newNode->nextptr=top;
top=newNode;
count++;
return 1;
}
Type Pop()
{
if(count==0) return 0;
Node<type> *temp=top;
top=top->nextptr;
Type D=temp->Data;
delete temp;
count--;
return D;
}
Type Top()
{
if(count!=0) return top->Data; else return 0;
}
bool isEmpty(){if(count==0) return 1; else return 0;}
int stackCount(){return count;}
void Destroy()
{
if(count!=0)
{
while(top!=0)
{
Node<type> *temp=top;
top=top->nextptr;
delete temp;
}
count=0;
}
}
void print()
{
Node<type> *current=top;
while(current!=0)
{
cout<<current->Data;
current=current->nextptr;
}
}
~stack()
{
Destroy();
}
};
int main()
{
Stack<char> s1;
s1.Push(‘A’);
s1.Push(‘B’);
s1.Push(‘C’);
cout<<"Count : "<<s1.stackCount();//count is 3
//C will be displayed as it was the last input
cout<<"\nPop function called : "<<s1.Pop();
//count decreased to 2
cout<<"\nCount : "<<s1.stackCount()<<endl;
system("pause");
}

3. Classes in depth

When working with the object oriented paradigms, classes are the most commonly used tools. So here we are to make you understand the simple but the most important concept. This post mainly discusses the concept of encapsulation, where we shall first see what are classes and objects and then relate them to encapsulation.

Starting from the very basics, what are classes and why do we use them? Suppose that your teacher has asked you to develop a program that stores data about cars in a car showroom. Now think over the task and find objects that are required to solve the problem. In this case we only need cars as our object to complete our task.

We use classes to model real life objects; every object is defined by its properties and functions performed on it, for example in this case, car is our object; every car has some properties like color, number of wheels, manufacturer etc; some functions can be performed on the car such as repainting it, driving it etc.

The following code shows a class model of a car

class car
{
char color[8];//stores the color of car
char manufctr[10];//stores the manufacturer of car
int numOfWheels;//stores the number of a car
void drive();//function to drive the car
void repaint(char col[8]);//function to repaint the car
};

The code above shows that the class has three members color, manufctr, numOfWheels and two member-functions drive and repaint. This is how we modeled a object from a real world into our computer.

Now how do we use this class to make objects, this is where we need to learn the concept of encapsulation; allows us to combine data and functions as we just saw that in a single class we gathered all the data and functions together to form a single object. In addition to this encapsulation allows us to restrict access to some or all of the information of the object, we can set our class members as private to object or we may give them a public access where anyone can access it.

The code below shows do we restrict access to objects information

class car
{
private:
char color[8];//stores the color of car
char manufctr[10];//stores the manufacturer of car
int numOfWheels;//stores the number of a car
public:
void drive()//function to drive the car
{
cout<<"The car is being driven"<<endl;
}
void repaint(char col[8])//function to repaint the car
{
strcpy(color,col);
}
};

Private members are those which are only accessible with in the class, for example we used the color property of the car in the repaint function, whereas public members can be accessed from anywhere in the program, by default the members are declared as private. Here we have declared color, manufctr and numOfWheels as private so that no one can change them, but as we are allowed to repaint a car we can change the color of the car through a public function, repaint(the function belongs to the class so it can access color directly), which takes color as a parameter.

The following program shows how to use member functions

#include &lt;iostream&gt;
using namespace std;
class car
{
private:
char color[8];//stores the color of car
char manufctr[10];//stores the manufacturer of car
int numOfWheels;//stores the number of a car
public:
void drive()//function to drive the car
{
cout<<"The car is being driven"<<endl;
}
void repaint(char col[8])//function to repaint the car
{
strcpy(color,col);
}
};
int main()
{
car c1;
c1.drive();
c1.repaint("Black");
system("pause");
}

In the main function we have declared an object, c1, of type car, which now tells us that a class is a user-defined type. We can access its public members by using a dot (.) operator as shown above, notice that here we are not allowed to call or access the private members of the class.

Still the code above is incomplete, what if user wants to get the private information of the car, for example if someone wants to know who is the manufacturer?, we need to give read only access to private members of the class to the user for that we have to write some more functions. Add the following code to the public section of the class.

//returns the color of the car
char* getColor(){return color;}
//returns the manufacturer of the car
char* getManufacturer(){return manufctr;}
//returns the number of wheels
int getNumOfWheels(){return numOfWheels;}

After writing the above functions you can easily access the private information of the car in a way that the user is not able to change it. But after this code you will encounter another problem, we have not yet initialized the members of class, so when you will try to print the information using the functions listed above you will get a garbage value.

We are not allowed to change the value of members directly by assigning it to them in the private block of code. So there must be a way through which we can assign values to them. As we cannot change the values using any other function we have to make sure that values are assigned to the object at the time it is declared.

Constructors are the functions that are implicitly called whenever an instance of a class is created, more precisely; constructors are functions, which are called implicitly, having the same name as the class with no return type. This will help us in initializing our object. Following code shows how do we implement constructors and how do they help us in initializing our class members.

public:
car()
{
repaint("white");
strcpy(manufctr,"BMW");
numOfWheels=4;
}
void drive()//function to drive the car
{
cout<<"The car is being driven"<<endl;
}
void repaint(char col[8])//function to repaint the car
{
strcpy(color,col);
}

Notice that the first function after the public statement is the constructor of the class, having the same name, in the body of the constructor we have accomplished three tasks, assigned a color to the car using a repaint function we have already declared in the class, assigned a manufacturer as it is a string we used strcpy to copy the value, and assigned the number of wheels. Now try calling the get functions we wrote above you won’t get a garbage value.

Doing this is somewhat hard coding, as all the objects we declare will be of white color having four wheels, manufactured by BMW, but this is what we don’t want, to solve this issue we can parameterize our constructor.

car()//default constructor
{
repaint("white");
strcpy(manufctr,"BMW");
numOfWheels=4;
}
car(char col[8], char man[10], int num)//parametric constructor
{
strcpy(color,col);
strcpy(manufctr,man);
numOfWheels=num;
}

The code above shows the parametric constructor, this will allow us to assign different values to different instances of our class, remember that we can have multiple constructors at the same time. As in this case we have both parametric and a default constructor, this is known as polymorphism, we will study this in more detail in our next posts but just for know polymorphism means that one function can have more than one implementations.

int main()
{
car c1;
c1.drive();
c1.repaint("Black");
cout<<c1.getColor()<<endl;
cout<<c1.getManufacturer()<<endl;
cout<<c1.getNumOfWheels()<<endl;

car c2("blue","Ferrari",4);
cout<<c2.getColor()<<endl;
cout<<c2.getManufacturer()<<endl;
cout<<c2.getNumOfWheels()<<endl;
system("pause");
}

Code above shows that default constructor was called when c1 was declared, whereas c2 was instantiated by the parametric constructor by passing our desired was values in the parameters at the time when object was declared. By now our class seems to be complete and we can implement our task by creating array of objects of type car and storing information in those objects.

2. Some Basic Concepts

There are three main concepts one should know if working with the object oriented paradigm, namely encapsulation, inheritance and polymorphism.

Encapsulation
Encapsulation is one of the very basic concepts of object oriented programming, the process of binding data and functions that manipulate data together is known as encapsulation. The functions and data are combined to form an object, in other words objects allow us to implement encapsulation. As we saw in our previous post that data and functions all were accessible through a single object. In addition to this, encapsulation allows us to restrict access to some of the objects information. Data may be public or private to that object. If access to data is restricted only to that object it means that data is private else if data is available to other parts of program also it is known as public. More precisely if data is only available to the same class it belongs to it is private where as if data of a class is accessible by other classes and modules of a program then it is said to be public.

Inheritance
Inheritance is one of the most powerful features, object oriented programming offers, inheritance means to inherit someone’s properties i.e. a process by which one object acquires the properties and method of other object is known as inheritance. The figure below explains this concept more clearly.

The class person has some properties and methods another class programmer inherits those properties and methods, now programmer has its own properties and some inherited ones, here programmer is said to be the derived class and person is called the parent class. This helps us in code modularization and reusability.

Polymorphism
Polymorphism (poly means many and morph means forms) as the name suggests means many forms, here in programming is used in the same sense, it means one interface multiple implementations. For example, we know that + operator is used to add two numbers, polymorphism allows us to customize it so that we can accomplish tasks such as adding two objects together. In this case the + operator will have two implementations one for adding numbers and second for adding objects. Similarly if you have two classes namely square and circle both derived from a class called shapes, having a function named calculate_area(), both square and circle will be having different implementation of the same method. This helps us implementing functions in the context they are used.

1. Introduction to Object Oriented Programming

Introduction to object oriented programming

This tutorial series is aimed to teach you the concepts of object oriented programming (OOP). We will use C++ as our tool to learn this programming paradigm. There are many modern programming languages now support OOP at least as an option. It is assumed that you have some prior programming experience, if you don’t you can go through our beginner’s tutorials.

What is object oriented programming?

Traditionally we had two separate parts of our program the data and the functions defined on that data. OOP allows you to keep the two things in the same place. When solving problems using procedural language such as C we use predetermined types such as floats and integers and our main consideration is what a particular program does, where as when working with OOP we are allowed to build our own data-types (user defined types) and our main consideration is what things are required to solve a problem, i.e. we model things in our real life, instances of those user defined types are known as objects, we then use these objects to solve our problem.

As I discussed that we are allowed to make our own data types what does it actually mean and how do we do that? We know a lot about built-in types in C/C++ such as integers, floats, characters etc, now we want a type, car, for example, where we can store data about the number of doors and transmission type of the car, this is where concept of classes is introduced. In very lay terms class is a definition of our data type i.e. what data we want to store and what actions do we want to perform on that data, is programmed in a class. Consider the code below to see how do we implement classes?

#include <iostream>

using namespace std;

//code to write a class starts here
class car //name of the class
{
public: //the access modifier
//the data we want to store in our datatype
bool auto_transmission;
int num_doors;
}; //class ends here
int main()
{
car c1, c2;

c1.auto_transmission=true;
c1.num_doors=4;

c2.auto_transmission=false;
c2.num_doors=2;

cout<<"Data C1, Auto Transmission: "<<c1.auto_transmission<<" No. of Doors: "<<c1.num_doors<<endl;

cout<<"Data C2, Auto Transmission: "<<c2.auto_transmission<<" No. of Doors: "<<c2.num_doors<<endl;

system("pause");
}

We have defined a data-type in our code above known as car; with in that class we have two more fields to store data, the number of doors and the transmission type of the car. You see a keyword public, this is known as access modifier which controls the access of your data, public means that your data can be accessed from anywhere in the program, that any block of code can access members of your class. There are two more, private and protected which will be discussed later. In the main function we have declared two objects of type car, or the two instances of class car, c1 and c2. To access the members of class we use the dot operator (.), as c1 and c2 are two different instances they both can have different values.

Similarly we can define functions in the same class and access them as shown below.

#include <iostream>

using namespace std;

//code to write a class starts here
class car //name of the class
{
public: //the access modifier
//the data we want to store in our datatype
bool auto_transmission;
int num_doors;
void display_info()
{
cout<<"Data C1, Auto Transmission: "<<auto_transmission<<" No. of Doors: "<<num_doors<<endl;
} //class ends here
};
int main()
{
car c1, c2;
c1.auto_transmission=true;
c1.num_doors=4;
c2.auto_transmission=false;
c2.num_doors=2;
//accesing the member functions
c1.display_info();
c2.display_info();
system("pause");
}

A function is added in the class members, which displays the state of the object that called the function, such as c1.display_info() shows the values of c1.

So this was a simple concept of what are classes and objects and how can we use them model real life things to solve or problems.

How to Target your Programming Problems

If I want you to leave this page with only one sentence, it would be this: “The sooner you start coding, the deeper you get stuck.”

When you face a programming problem, just don’t start coding the first idea that comes to your mind. Move back and look at it. Think about it. Think about it hard because there are overwhelming chances that the first idea is not the best one. Even if it gives you a correct solution, it will probably require more effort, take more space and be less efficient.

The example I am giving you here might seem a little obvious but extend it to other problems and you will get my point.

Let us write a program to list all factors of a given integer n. I am coding the first idea I had. Here it is:

void printFactors(int n)
{
	for(int i = 1; i <= n; ++i)
	{
		if ( n % i == 0)
			cout << i << ", ";
	}
}

Yes the solution is correct. And if you want the factors of a few small numbers, its fine too. But think about it. Our function does a hell lot of useless operations. It continues the loop till 'n' while no factor of 'n' can be greater than 'n/2' except for 'n' itself. So we can make 'i <= n/2' instead of 'i <= n' and then print n.

Now wait a minute… what if 'n' is odd? There is 50% chance that it is. If it is odd, we keep dividing it by numbers like 4, 6, 8, 10 and so on which is useless. So we can divide 'n' by 2 in the beginning and then know if we only need to divide it by odd numbers.

Well… it seems thats about it. But it is not. Let us assume n = 10. When i = 2, then dividing 10 by 2 gives no remainder and 2 is a factor. But the number we multiply 2 with i.e. 5, is also a factor right? So along with i, n/i is a factor too. If we run the loop with this to n/2, we get double entries for all the factors. So we reduce the upper limit of i from n/2 to the square root of n. Now let me code this for you.

void printFactors(int n)
{
	int limit = sqrt( (float)n); //sqrt() needs a float, double or long double argument

	int increment;
	if(n % 2 == 0)
		increment = 1;
	else
		increment = 2;

	for(int i = 1; i <= limit; i+= increment)
	{
		if (n % i == 0)
		cout << i << ", " << n/i << ", ";
	}

	cout << n;
}

To prove the improvement in efficiency, the first function took 40 seconds for 100 large numbers and the latter took only 1 second for the same. That is 40 times faster.

This solution took more effort and space but was much more efficient than the previous one. And it doesn't print the factors in order but that can be arranged. A good program design for a bigger problem which comes after thinking hard will very likely give you all the three advantages.

So lads, its better to think an hour and code an hour than to think a mintue and code ten hours. Coming up with a solution quicker doesn't necessarily make you better :)