Stacks

Stacks: One Stop

CONCEPT:

Stacks are linear data structures with a simple idea: just stack the elements! You can think of it as a pile of books stacked over each other(as a very trivial example). And you can only take books from the top, and if you want to take book at a any other position you would have to take the books up to that one out and then only you can reach that book(I know you can directly pull that off, but lets consider that is not an option). 

Application

Stacks are very powerful if used in a smart manner. Like think of it you can add to top in O(1) time, remove from top in O(1) and access to top in O(1). Moreover they are used with loops to solve quite difficult problems like bracket matching, post-fix to prefix and vice-versa. Real world applications are doing undo and redo (just think of it!),browsers for going to previous URLs, and much more. 

There are just these four operations in stack:

• Push: Push an element to the top(Inserting element at top)
  
• Pop: Pop from the stack(removing the top most element)
  
• Peek: Reading top-most value of stack
  
• isEmpty: Checking if stack is empty or not

And all of them work in O(1)!

Implementation:

Stack follows FILO(First In Last Out). This means that the first one to enter the stack would leave at the last which is quite obvious considering its structure of pile of books.

Three types of implementations:

• Through arrays
• Through linked list
• Through STL

Through arrays:

You can think of a fixed array(of a declared size(though the size maybe large)) and we just make a variable which would be used in the four operations. Push would just assign the value you want to push at top+1 position and increment top by 1. Similarly pop would just make your top decrement by 1. Peek would just show array[top] and isEmpty would be a simple if condition.

Code: here

Pros and Cons:

You got it easily. This is only good thing about implementing through arrays. This uses fixed size which is obviously not what we need these times.

Implementing using linked list:

Okay, this is quite difficult to implement than it seems to be. The concept is same, make a new node on push operation and make it as the top, delete the node and free the node in case of pop and similarly for peek and isEmpty().

Code:(this code is copied from gfg article) here

Pros and cons:

difficult to implement but dynamic. 

Implementation using STL:

This is what we are going to do to implement stacks unless asked for any other implementation. 

You just declare a stack like this: stack<int> name_of_stack

And now you can do the following operations: 

name_of_stack.pop()

name_of_stack.push(5)

name_of_stack.top()

name_of_stack.size()

Some Basic Questions:

•  Bracket Problem: 

Hint 1: Match the brackets. Quite simple, just iterate over the string of brackets and push if its an opening bracket and pop if its a closing bracket. If you can't pop(in case if stack is empty and a closing bracket appears) , then its not balanced, else balanced. 

 

Hint 2: If there are multiple types of brackets, make separate stacks for all o the cases. 

 

Question Link: A cool problem

 

Code Link: Code Link

•  Maximum Element:

Hint 1: Another beautiful question on stacks. Have multiple approaches: I use a multi set which is obviously a bad approach here.

 

Hint2: Another good approach is to have two stacks, one for the main elements and other to keep track of max elements. You just insert maximum elements(actually repeatedly) in max stack and pop it from both in the pop case and output the top element in third case. 

 

Hint3:A slight improvement of the same algorithm is to push only the current max element in the stack(for eg if I give you 90(initial element) you push it in the stack, and now if I give you 20, you still push 90 in the stack(the curr max) ) . And you pop normally as you do. In this way you just output the top in case of max query.

 

Question link(hacker rank): here. 

Code Link: here

 

•