Stack
Tags: python, datastructure, stacks, queues
Published: 2020-12-01 10:12:26

  The **stack** may be a linear arrangement that follows a specific order during which the operations are performed. The order of stack could also be LIFO (Last in First Out) or FILO (First In Last Out).
A stack is generally an **Abstract Data Type (ADT)**. This ADT is generally used in most programming languages it's an easy arrangement that permits adding and removing elements during a particular order. whenever a component is added, it goes on the highest of the stack, and therefore the only element which will be removed is that the element that's at the highest of the stack, a bit like a pile of objects.

This is named the stack because this behaves like a real-world stack application the stack ADT will allow all the data operations at one end only at any time, we can use the top element of a stack


![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/j1bcjg4ij4j81w6yt5hk.png)

Generally, a stack is an abstract data type that is a set of elements, with two main principal operations:
1)	Push (a)
2)	Pop ()

**Push**: which adds a component to the gathering, and

**Pop**: which removes the foremost recently added element that wasn't yet removed.

Not only push and pop but there are also other operations in a stack. They are :
1)	IsEmpty ()
2)	is full ()
3)	Peek ()
4)	Top ()
5)	Search ()


![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/1vwzbwoz20ayklqd7dwy.png)



Now let us see the time complexity of all the operations in the stack:
1) push (a) – 0(1)
2) pop () – 0()1
3) IsEmpty () – 0(1)
4) ISFull () – 0(1)
5) peek () – 0(1)
6) top () – 0(1)
7) search () – 0(n)

We can generally write stacks in any of the major programming languages but I'm now writing stacks in ”python”
Ok, let's see how we can implement stacks in python. Generally in Python stack can be implemented in 3 ways. they're implementation method using List 
Python’s built-in arrangement list is often used as a stack. Instead of push(), append() is employed to feature elements to the highest of the stack while pop() removes the element in LIFO order.
Unfortunately, the list has a few shortcomings. The biggest issue is that it can run into speed issues because it grows. The items in the list are stored next to every other in memory, if the stack grows bigger than the block of memory that currently hold it, then Python needs to do some memory allocations. This can cause some append() calls taking for much longer than other ones.

**Features of stacks**:

•They are Dynamic data structures
•They Do not have a fixed size and also 
•They Do not consume a fixed amount of memory

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/db72caupua77i5igg8gv.jpeg)


**Uses of Stacks**:

Basically, there are some particular uses of stacks in data structures. They are 

**1)Expression Handling**
    
1.Infix to suffix or Infix to Prefix Conversion −

The stack is accustomed convert some infix expression into its suffix equivalent, or prefix equivalent. These suffixes or prefix notations are employed in computers to specific some expressions. These expressions aren't most acquainted with the infix expression, however, they need some nice blessings additionally. we tend to don't got to maintain operator ordering and parenthesis.
     
2.Postfix or Prefix analysis analysis

After changing into a prefix or ending notations, we've got to gauge the expression to urge the result. For that purpose, conjointly we want the assistance of stack organization.

**2) Backtracking Procedure** −

Backtracking is one in every of the formula coming up with technique. For that purpose, we tend to dive away, if that method isn't economical, we tend to return to the previous state and go in another way. to induce back from the current state, we'd like to store the previous state. For that purpose, we'd like a stack. Some samples of backtracking are finding the answer for Knight Tour downside or N-Queen downside etc.


3) Another nice use of stack is throughout the call and come back method. after we decided a operate from one alternative operate, that call statement might not be the primary statement. when career the operate, we tend to even have to come back from the operating space to the place, wherever we've left our management. thus we would like to resume our task, not restart. For that reason, we have a tendency to store the address of the program counter into the stack, then head to the operating body to execute it. when completion of the execution, it pops out the address from the stack and assign it to the program counter to resume the task once more.

4) **Syntax Parsing**-
           Many compilers use a stack for parsing the syntax of expressions, program blocks, etc. before translating into low-level code.

5) **Parenthesis Checking** -
            The stack is used to check the proper opening and closing of the parenthesis.

6) **String Reversal**
            The stack is used to reverse a string. We push the characters of the string one by one into the stack and then pop character from the stack.

Not only these but there are many uses of stacks like Function call, Memory Management, etc, etc 

```
# initial empty stack  
my_stack = []  
# append() function to push   
# element in the my_stack   
my_stack.append('k')  
my_stack.append('p')  
my_stack.append('s')  
print(my_stack)  
#pop() function to pop   
# element from my_stack in    
# LIFO order   
print('\nElements poped from my_stack:')  
print(my_stack.pop())  
print(my_stack.pop())  
print(my_stack.pop())	  
print('\nmy_stack after elements are poped:')  
print(my_stack)