CONCEPT OF STACK AND PROBLEM SET

STACK

A Stack is a basic data structure that can be logically thought of as a linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack. 

The basic concept can be illustrated by thinking of your data set as a stack of plates or books where you can only take the top item off the stack in order to remove things from it. This structure is used all throughout programming.

To clear your concepts you can follow these steps....

Step 1: Visit this article to Clear your basic theory

Step 2: Visit this article to deep dive into the stack

If you have enough time you can follow these videos sequentially to master STACK

1. Intro To Stack

2. Array Implementation

3. Linked List Implementation

4. Infix, Prefix, Postfix

Problem Set: Level Basic

1. Reverse a number using STACK

2. Reverse a number using STACK

Problem Set: Level Intermediate

1.  Infix to postfix expression using stack  (Solution)

2.  Stock span problem                                                                                                       -consider a given array {100 80 60 70 60 75}           then the span for each element it in the array is this Max number of consecutive elements which are lesser than or equal to the given  element

              -for the above span array for each element, it is {1, 1, 1, 2,      1, 4, 6}  (Solution)

3. Evaluate a postfix expression (Solution)

4. Find the next greater element in an array or a linked list using          stack ( for an element if there is no greater element return -1) (Solution)

5. Reverse a stack using recursion (Solution)

6. Length of the longest valid substring  (Solution)

7. Check for balanced brackets in an expression (all opening                 brackets must have a closing one)  (Solution)

8. Given an expression with only ‘}’ and ‘{‘. The expression may not be balanced. Find the minimum number of bracket reversals to make the expression balanced. (Solution)

9.   Maximum depth of nested parentheses 

(We are given a string having parenthesis like below

     “( ((X)) (((Y))) )”
We need to find the maximum depth of balanced parenthesis, like 4 in the above example. Since ‘Y’ is surrounded by 4 balanced parentheses.

If parenthesis is unbalanced then return -1.) (Solution)

10. Maximum equal sum possible in three stacks with the removal of only top elements allowed (Solution)

11.  Check if a given array can represent preorder traversal of the binary search tree (Solution)

12.  Iterative preorder traversal of a binary tree (Solution)

13.  Sort a stack using recursion (Solution)

***"The Celebrity Problem"****

13. In a party of N people, only one person is known to everyone. Such a person may be present at the party, if yes, (s)he doesn’t know anyone at the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in the minimum number of questions. (Solution)