Learn Stack data structure

 About Stack:

A Stack is a simple data structure used for storing data, in which insertion and deletion are done at one end, called Top.

Stack Abstract Type: 

The following operations make a stack an Abstract Data Type. 

Operations: 

• Main operations: push and pop
• Auxilliary operations: top, size, isEmptyStack, isFullStack

Why and when to use Stack:

• Balancing of symbols.
• Infix to postfix conversion.
• Evaluation of postfix expression.
• Implementing function calls.
• Finding of spans (like in stock market).
• Page history in a web browser.
• Undo sequence in a text editor.
• Matching tags in HTML and XML (parses uses stack while tokenising the input)

Practice questions:

1. Balancing of symbols using stack.
2. Infix to postfix conversion using stack.
3. Postfix evaluation using stack.
4. Can we evaluate the infix expression with stacks in one pass?
5. How to design a stack such that GetMinnimum() should be O(1).
6. Optimized solution in terms of space for Q5.
7. For a given array with n symbols, how many stack permutations are possible?
8. Check if the given string is palindrome or not.
9. Consider a linked list instead of a string literal in Q8.
10. Q9 using stack.
11. How to reverse elements of a stack using only stack operations (push and pop)?
12. Implement one queue using two stacks.
13. Implement one stack using two queues.
14. Implement two stacks using only one array.
15. Implement three stacks using only one array.
16. Another way of solving Q15.
17. Implement m stacks using only one array.
18. If the string S2 can be made from string S1, using only stack operations? Where S donates a push operation and X donates a pop operation. Example: let the numbers: 1,2,3,4,5,6 pushed in a stack in chronological order, can they be permuted in this order:  O1(3,2,5,6,4,1) and O2(1,5,4,6,2,3)?
19. For dynamic array implementation of stack, what will be the complexity of a push operation if we create a new array whose size is (n+k)?
20. For a string of n S's and n X's, where S donates a push and X donates a pop operation, check whether a string S is admissible or not?
21. Intersection point of two linked lists using stack.
22. Finding spans. 
23. Finding spans with O(n) time complexity.
24. Largest area under histogram.
25. Largest area under histogram in O(n) time complexity.
26. How to check whether a stack is growing up or down in a given machine?
27. In a stack of integers, how to check whether the successive pair of numbers are consecutive or not? For stack of odd numbers, consider the top as a left-out pair.
28. Recursively remove all adjacent duplicates in a string.
29. Replace every element in an array of elements with nearest greater element on the right of that element.
30. Q29 with O(n) time complexity.
31. How to implement a stack with the following operations in O(1) time complexity?
1. push
2. pop
3. find the middle element 
4. delete the middle element

Source: Data Structures Made Easy by Narasimha Karumanchi