### Let Start Stack with Me

**STACK** : A **Stack** is an ordered List in which insertion and deletion are done at one end called **TOP.** In the simple terms we can say that the last element inserted is the first one to be deleted. That’s why, it is called the ** Last in First out (LIFO)** or

**.**

*First in Last out (FILO)***Main Stack Operations:**

**1.)**** PUSH** -** Insert value in the Stack.**

**2.)** **POP** - **Removes and returns the last inserted value from the Stack.**

**Auxiliary Stack Operations:**

**1.) TOP** - **Get the last inserted value without removing that.**

**2.) SIZE** - **Get the number of elements stored in the stack.**

**3.) IsEmptyStack** - **Check whether any elements are stored in the stack or not.**

**4.) IsFullStack** - **Check whether the stack is full or not.**

**Exception:**

**1.) UnderFlow** - **POP from an empty Stack**

**2.) OverFlow** - **PUSH from full empty Stack**

**Let see the following image to understand the structure:**

**Following are some of the scenario in which stacks play an important role:**

**1.) Balancing of symbols**

**2.) Evaluation of postfix expression**

**3.) Implementing function calls**

**4.) Finding of Span**

**5.) Page visited history in a Web Browser**

**6.) Undo sequence in text editor**

**7.) Matching Tags in HTML and XML**

*Implementation*

*SImple Array Implementation** : In the array we add elements from left to right ans use a variable to keep track of the index of the TOP element.*

*Performance:*

*1. Space Complexity - O(n)*

*2. Time Complexity for Push() - O(1)*

*3. Time Complexity for Pop() - O(1)*

*4. Time Complexity for Size() - O(1)*

*5. Time Complexity for IsEmptyStack - O(1)*

*6. Time Complexity for IsFullStack - O(1)*

*6. Time Complexity for DeleteStack- O(1)*

*But the maximum size of the stack first be defined and it can't be changed.*

**Dynamic Array Implementation: In Dynamic Array we can use repeated doubling technique.**

*Performance:*

*1. Space Complexity - O(n)*

*2. Time Complexity for Push() - O(1) - Average*

*3. Time Complexity for Pop() - O(1)*

*4. Time Complexity for Size() - O(1)*

*5. Time Complexity for IsEmptyStack - O(1)*

*6. Time Complexity for IsFullStack - O(1)*

*6. Time Complexity for DeleteStack- O(1)*

**To many doublings may cause memory overflow exception.**

*Linked List Implementation** : By using Linked List Push() operation is implemented by inserting element at beginning of the List and Pop() operation is implemented by deleting the header node.*

*Performance:*

*1. Space Complexity - O(n)*

*2. Time Complexity for Push() - O(1)*

*3. Time Complexity for Pop() - O(1)*

*4. Time Complexity for Size() - O(1)*

*5. Time Complexity for IsEmptyStack - O(1)*

*6. Time Complexity for IsFullStack - O(1)*

*6. Time Complexity for DeleteStack- O(n)*

**Let compare between Array and Linked List Implementation:**

**Array Implementation:**

**1. Operations take Constant Time.**

**2. Expensive doubling operation every once ina while.**

**Linked List Implementation:**

**1. Grows and Shrink gracefully.**

**2. Every operation takes Constant Time O(1)**

**3. Every operations uses extra space and time to deal with reference.**

**In next article we will discuss Problems and Solutions on Stacks.**

**Thanks & regards:**

**Abhishek Kumar**