What do you mean by stack in Data structure and an algorithm?

Question

Stacks 

• What do you mean by stack? 
• Figure
• Examples
• Its representation
• Array representation
• linked list representation
• Full operations on stacks
• Its various algorithms 
• Evaluating expression using stacks with algorithms
• Code generation for stack machines
• Reversing a list of items

Answer 1

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

1. Start
2. If top≥size 
3. Print “stack is full” 
4. Else 
5. Top=top+1 
6. A[Top]=item 
7. End if  
8. 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

1. Start 
2. If top<1 
3. Print “stack is an empty” 
4. Else 
5. Item=A[top] 
6. Top=top-1 
7. Stop 

Status 

Algorithm

1. Start
2. If top<1 then 
3. Print “stack is an empty” 
4. Else 
5. If (top≥size) then 
6. Print “stack is full” 
7. Else 
8. Print “the element at top is”, A[top] 
9. Free=(size-top) /size*100 
10. Print “percentage of free stack is” free 
11. End if  
12. End if  
13. 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:

• Infix
• Postfix
• Prefix

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:

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

Implementation of Stack 

Implementation of Stack in Python

---