**Stacks **

- A stack is an ordered collection of homogenous data elements where the insertion and deletion operations occurs at only one end

Or

- Stack is a linear data structure , collect the homogenous data items, to perform the insertion and delete operations at one end only called as ‘Top’.

**Representation of a stack **

- To implement the stack principle using arrays and linked list.
- It follows last in first out(LIFO).
- Array reprsentation
- By using fixed size of array to perform the stack operation.
- Linked list representation
- To perform collection of data elememt dynamically by using linked list with stack data structure.

**Operations on stack **

To perform ,insertion and deletion operations by using stacks.

- Push(insertion)
- Pop(deletion)
- Status

**Push operation **

- To perform the insertion operation at one end called as push operation

Or

- The process of putting a new data element on to stack is known as push operation.

**Algorithm**

- Start
- If top≥size
- Print “stack is full”
- Else
- Top=top+1
- A[Top]=item
- End if
- stop

**Pop-operation:**

- Accessing the content while removing it from the stack is known as a pop-operation.
- To perform pop operation every time to check the condition is top<1 when top=1

**Algorithm**

- Start
- If top<1
- Print “stack is an empty”
- Else
- Item=A[top]
- Top=top-1
- Stop

**Status**

**Algorithm**

- Start
- If top<1 then
- Print “stack is an empty”
- Else
- If (top≥size) then
- Print “stack is full”
- Else
- Print “the element at top is”, A[top]
- Free=(size-top) /size*100
- Print “percentage of free stack is” free
- End if
- End if
- Stop

**Applications of stack **

- Evaluation of Arithmatic Expression
- Code generation for stack machine
- Implementation of Recursion
- Activation Record management
- Reversing a list of items.
- Backtracking
- Decimal to Binary conversion

**Evaluation of Arithmatic Expression **

Based an expression evaluation process are derived into three categories:

Expression is a collection of operators and operence.

**Infix expression:**

- The operator placed in between two operance called as infix expression.

__Eg__:A+B

c/d

E*F

**Post-fix expression**

- The operator placed after the operance.

__Eg__:

AB+

CD/

EF*

**Prefix expression **

- The operator placed before the operance.

__Eg__:+AB

/CD

*EF

**Evaluation of expression by using stacks **

*Algorithm for conversion from infix to postfix expression:*

Scan the infix, string from left-right.

2) Create an empty stack.

3) a) if the scan character is operand , then add it to the postfix string.

b) If the scan character is an operator , then push into the stack, when stack is empty.

4) If the scan character is an operator and the stack is not empty, then compare the precedence of the character with an operator presented in the top of the stand stack.

If the top of the stack has higher precedence than scan character(operator) , then pop the stack and add it into the postfix string else the scan character push into the stack.

5) Continue 3) and 4) steps until all the characters are scanned.

6) Return to the postfix string.

**Algorithm steps for postfix evaluation **

Scan the expression from left to right.

2) Create an empty stack.

3) a) If the scanf character is operand , then add the postfix string.

b) If the scanf character is an operator, then push into the stack when stack is empty.

4) If operand is found, then push into the stack.

a) If the operator is found, then pop the required number of operands from the stack and evaluate the operator.

5) Push the result back into the stack.

6) end if

7) end if

8) pop out the result from the stack, display on the screen.

**Code generation for stack machines **

- Stack machine is a machine which use a stack instead of registers to store immediate results temporaries.
- Using a stack, we can easily generate an assembly code from a postfix notation.

**Examples**

- LDA A To load the accumulator with the memory content of A and the content of A will remains unchanged.
- ADD A To add the value of memory content A with the value of the accumulation and the result will be stored in accumulator.
- Similarly , SUB B,
- MUL C,
- DIV D, etc.
- These codes are called single address codes. These codes are for those machines which maintain a number of registers.

- Some machine will have a very limited number of registers, so those machines uses a stack instead of registers to store temporaries.
- For stack machines, we can generate the optimized code from the postfix notation by using stacks.

**Reversing a list of items **

Reversing data requires that a given set of data will be reordered. So that the first and last elements are exchanged, with are of the positions between the first and last being relatively exchanged also.

**Convert decimal to binary**

The idea of reversing a series can be used in solving classifical peoblems such as converting a decimal number to a binary number.

**Algorithm DCC**- Binary

**Input**:A number in decimal format

**Output**: A binary number.

*Steps*:

- Read number(n)
- while (n>0) ||remainder
- push(rem)
- m=n/2||quotient
- end while
- pop the stack and print the results one digit at a time
- stop.

Implementation of Stack

Implementation of Stack in Python