User Name:


User Email:




This information will only be saved for the purposes of communicating with those who have provided this information voluntarily regarding our services.We will never sell your name or email address to anyone.
© 2017 - First Crazy Developer (Abhishek Kumar)
  

crazydeveloper 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


crazydeveloper Home Page 19 August 2017

Become a Fan