# Applications of Stack in Data Structures

A stack is a *restricted data structure*, because only a small number of operations are performed on it. Elements are removed from the stack in the reverse order to the order of their addition. For more information on stack, go through this article.

In this article here, we’ll discuss real world applications of stack. First we’ll see *infix to postfix conversion*. What is actually done is in *infix to postfix,* an expression is scanned from user in infix form; it is converted into prefix or postfix form and then evaluated without considering the parenthesis and priority of the operators.

### Algorithm for Infix to Postfix

- Examine the next element in the input.
- If it is operand, output it.
- If it is opening parenthesis, push it on stack.
- If it is an operator, then
- If stack is empty, push operator on stack.
- If the top of stack is opening parenthesis, push operator on stack
- If it has higher priority than the top of stack, push operator on stack.
- Else pop the operator from the stack and output it, repeat step 4
- If it is a closing parenthesis, pop operators from stack and output them until an opening parenthesis is encountered. pop and discard the opening parenthesis.
- If there is more input go to step 1
- If there is no more input, pop the remaining operators to output.

**Example:**

Suppose we want to convert 2*3/(2-1)+5*3 into Postfix form

### Evaluating a postfix expression

- Use a stack to evaluate an expression in postfix notation
- The postfix expression to be evaluated is scanned from left to right
- Each operator in a postfix string refers to the previous two operands in the string
- Each time we read an operand we push it into a stack. When we reach an operator, its operands will then be top two elements on the stack
- We can then pop these two elements, perform the indicated operation on them, and push the result on the stack
- So that it will be available for use as an operand of the next operator
- Initialize an empty stack
- While character remain in the input stream
- Read next character
- If character is an operand, push it into the stack
- Else, if character is an operator, pop top two characterss off the stack, apply the operator, and push the answer back into the stack
- Pop the answer off the stack

Picture below depicts *postfix expression using stack*

### Algorithm for evaluating a postfix expression

WHILE more input items exist { If symb is an operand then push (operand_stk, symb) else //symbol is an operator { Opnd1=pop(operand_stk); Opnd2=pop(operand_stk); Value = opnd2 symb opnd1 Push(operand_stk, value); } //End of else } // end while Result = pop (operand_stk);

### Implementation of Stack Data Structure in C++

Click here to see the C++ implementation of Stack Data Structure in C++

### Related Posts

- Queue Implementation in C++
- Doubly Linked Lists
- Bubble Sort: A Graphical Explanation
- Linked lists in C++
- Implementation of Priority Queue using Heap data structure in C++
- This Pointer, Static Members and destructors in C++
- Graph Implementation in C++
- Graph search in C++
- Pointers and Arrays in C++
- Top 10 C++ programming resources
- Comparison of Sorting Algorithms – Bubble Sort, Selection Sort, Insertion Sort
- Applications of Circular Linked List in Data Structures

### 7 Responses to *Applications of Stack in Data Structures*

### Related Links

### Popular Posts (last 30 days)

- Attendance Management System 1016 view(s)
- Circular Linked Lists 652 view(s)
- Graph Implementation in C++ 485 view(s)
- Applications of Stack in Data Structures 448 view(s)
- JAVA Graphical User Interface (GUI) 299 view(s)
- Linked lists in C++ 171 view(s)
- Heap Sort with Graphical Explanation 154 view(s)
- Quick Sort Algorithm with Graphical Explanation 128 view(s)
- Advanced Java Tutorial (For Intermediate) 116 view(s)
- Implementing Stack Data Structure in C++ 110 view(s)

### Tags

Android C-Sharp C/C++ language Classes Data structures Design Pattern Eclipse Game Development Graphics Design Books HTML iPhone JAVA JAVA GUI MIPS Assembly Mobile Programming Books Object Oriented PDF PHP Programming Programming Books Programming Languages Books Python RaphaelJS REST Source Code Threads Tutorial Web Development Books

Its too useful for me thanks for this type of information is published.

Very Good approach…

Have great ideas about stack…

very useful to all…

very useful ideas…………

mga lokoloko walang code!

this is very usefull for all computer students

it is really good i like that