Stacks

The practical instances of data structures plays a vital role in their learning and mild programming knowledge has also made their implementation as natural as breathing in the real digital spectrum of computer science. Thus, programmers with technically analyzing vision also possess robust coding skills or vice versa. Both these attributes complement each other to brew an all rounded software engineer, who can translate his visionary skills into code with significant ease. In short, knowledge of practical instances of data structures have significant impact on development of the programming mindset.

In our effort to learning data structures along with their practical instances, we have come to stacks and queues. Both have mutually exclusive set of properties in terms of approach and implementation. The two can be regarded as converse of each other to some extent. In the following sections, we will discuss each of stack data structure individually for purpose of simplification and symmetry.

Concept

After arrays, the stacks have utmost significance in computer science. You might have listen keywords like FILO or LIFO, when in debate about stacks. It is not strange and only remembering these words is not a litmus test of the quality of your coding knowledge. There are wide range of practical examples demonstrating the application and principles of stacks. Car parking garage is one of the common example. Suppose a garage has capacity to hold ten cars in series, such that each upcoming car has to be parked after the existing car. In this way, the person whose car is parked in the last will be the first person to get his car. On the other hand, the owner of last car (parked first) has to wait until all the other cars be removed. In technical terms, accessing the first pushed element of the stack will have time complexity of O(n), where n is the number of elements in the stacks. Now moving back to the acronym, LIFO or FILO, which are abbreviations of “Last In First Out” or “First In Last Out”. To condense these concepts into simple statement, we would say stack is a structure where first element entering the stack will be the last element leaving it or vice versa. 

Advantages

The ultimate advantage of using stack lies in its time complexity. Most operations in the stack has constant time complexity i.e. O(1), which makes it really desirable data-structure to implement on wide range of problems. The particular strata of problems, stack deals, involve some kind of order. For example if you are solving problem in which order of steps is mandatory to regard then obvious data-structure that should come to your mind would be stacks. 

Most operations in the stack has constant time complexity i.e. O(1).

Building Stacks

Surprisingly, we can hold different datatypes in one stack but it is not regarded as a good practice. So, try to make different stacks for different datatypes unless there is no memory bottleneck. Due to widespread use this data structure most of the languages provide built in functions or libraries to create stacks with minimum lines of code. In python creating stack/array/queue are all same with modification in accessing the elements stored. Whereas, Standard Template Library (STL) in C++ provides dedicated library/template for handling all relevant functionality of stacks.

Before getting into the functionality of the stacks and their corresponding operations, we would go through general syntax to create a stack in C++. Without creating stack we cannot implement its functionality anyways.

Following steps are additive to the common syntax of the C++ code.

1.      Import stack library at top of your code.

2.      Declare stack in the main function.

Keyword - stack, is actually the name of the library we imported in the first step.

Data-type tells the kind of data we should store in the stack data-structure.

Name of the data-structure is what we will always use in our program to talk about this data-structure created above.

# At this point we have successfully created our data-structure but keep in mind it is empty.

Modifiers

Now, we want to add some data/content into our recently created data-structures (named stack_1). STL has provided us different methods to modify our data-structure. The unique feature of modifiers is that they impact the data-structure being applied to. The data-structure after applying modifier will not be the same.

Following are some of the modifiers commonly used as well as provided by the STL.

3.      Add elements into the stack using push modifier.

Name: To talk about the data-structure we have created in above lines.

Dot-operator: It is also called member access operator to access member functions of the class (In our case class is stack and the member function we are trying to access is push).

Data: It will be the main part to be added into the stack.

# You might observe that we declare integer as datatype in step-2 and we added different datatypes # in our stack but when we print the result we only get desired datatype. It is only for demonstration # purpose and is not a recommended practice.

# After writing the above code we came to know that we added few wrong type of data so we want to remove it.

4.      Remove elements from top of the stack using pop modifier.

Pop modifier always do not require any input between parentheses and removes the last pushed element from the stack.

# Other than that there are also uncommon modifiers as well such as emplace(), often with classes to # push elements and works same as push.

5.      We can also use swap modifier to interchange content of two stacks.

Order of arguments of the swap modifier do not matter much and result would always be the same for all cases, but it is important to keep regard of the datatypes of the stacks. Swap between stacks of different datatypes will throw an error.

# Finally we are now comfortable adding and removing elements from the stacks as well as interchanging the content of entire stacks using swap modifier.

As discussed earlier, we can only add and remove elements from top of the stack only, thus we can also access only the top element of the stack.

Element access

STL has only one function to access the top element of the stack.

6.      Access the top element of the stack using the top() element access function.

Unlike modifiers, element access functions have return type similar to the one defined by user at the declaration of the data-structure (in our case at step – 1).

Other than that we also often need to check the capacity of our data-structure and there are also few functions in STL to accomplish this task.

Capacity

7.      Check whether the stack data-structure is empty or not.

empty() return 1 (true) if the data-structure is empty and 0 (false) in all other cases. Thus, two values possible return-type values.

8.      We can also get the accurate size of the data-structure using the size function.

size() function returns the number of elements present in the stack and thus its return type will always be integer or long (for large size structures).

Print stack Function

Till this point we have developed basic concept of stack and how to manage this data structure. Now we are capable to write a simple print function to print all the elements of the stack.

For loop in line-10 is used to add element into the stack, simple functions of the stacks data-structure is used in the print_stack() function.

At the end of this function the stack_1 would be empty.

Logical Comparison and Custom Comparison

Furthermore, logical operators are also used to make different comparisons between stacks. Following are the six primary expressions of comparison offered by the STL for stack data-structures. These comparison operators return boolean values, true in case the comparison between the data-structures satisfies the operator being used and false otherwise.

The above operator can also be replaced with the following code by using the keyword operator followed by the comparison operator itself.

The above syntax of comparison is often used in customized sorting, defines custom function for the operator to make comparison and then sort accordingly.

As in the above case, I have created custom comparison function with the name operator> which makes comparison on the basis of second element pushed in the stack of pair. As the second element of the stack_1 is larger than second element of stack_2 thus the result of comparison would be “1” i.e. true.

Problems

Try to solve at least 10-20 problems related to the data-structure in order to get practical insight about its implementation. Different resources can be availed to accomplish the above outlined milestone but in keep in regard that the problem should challenge your problem solving skills and you should spend sometime to come up with the solution. Intuitive and easy problem are also good for getting started but try to target medium problems as much as possible. Among the many useful resources, leetcode is one of them, and try to solve its problems (precisely, relevant to stacks).