Stack
A stack is an Abstract Data Type (ADT), commonly used in most programming languages.
A stack in real life is a deck of cards or a pile of plates which allows operations at one end
only.
Stack Representation
The following diagram depicts a stack and its operations −
A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack
can either be a fixed size one or it may have a sense of dynamic resizing. However for the
purpose of discussion an array will be used, which makes it a fixed size stack
implementation.
Basic Operations
Push Operation
The process of putting a new data element onto stack is known as a Push Operation. Push
operation involves a series of steps −
● Step 1 − Checks if the stack is
full.
● Step 2 − If the stack is full,
produces an error and exit.
● Step 3 − If the stack is not full,
increments top to point next
empty space.
● Step 4 − Adds data element to
the stack location, where top is
pointing.
● Step 5 − Returns success.
Pop Operation
Accessing the content while removing it from the stack, is known as a Pop Operation. In an
array implementation of pop() operation, the data element is not actually removed, instead
top is decremented to a lower position in the stack to point to the next value. A Pop
operation may involve the following steps −
● Step 1 − Checks if the stack is
empty.
● Step 2 − If the stack is empty,
produces an error and exit.
● Step 3 − If the stack is not empty,
accesses the data element at
which top is pointing.
● Step 4 − Decreases the value of
top by 1.
● Step 5 − Returns success.
Applications
Reverse a string
Algorithm:
1. Create an empty stack.
2. One by one push all characters of string to stack.
3. One by one pop all characters from stack and put them back to string.
Simulation:
Input Text: reverse
1. Create Empty Stack
2. push( r )
3. r push( e )
4. r e push( v )
5. r e v push( e )
6. r e v e push( r )
7. r e v e r push( s )
8. r e v e r s push( e )
9. r e v e r s e End of Input String
10. r e v e r s e pop() - Output: e
11. r e v e r s pop() - Output: es
12. r e v e r pop() - Output: esr
13. r e v e pop() - Output: esre
14. r e v pop() - Output: esrev
15. r e pop() - Output: esreve
16. r pop() - Output: esrever
17. Empty Stack - end of process
Infix to Postfix
Infix expression:
The expression of the form a op b.
When an operator is in-between every pair of operands.
eg. 1 + 2 * 3
Postfix expression:
The expression of the form a b op.
When an operator is followed for every pair of operands.
eg. 1 2 3 * +
Algorithm:
1. Scan the infix expression from left to right.
2. If the scanned character is an operand, output it.
3. Else,
…..3.1 If the precedence of the scanned operator is greater than the precedence of the
operator in the stack(or the stack is empty or the stack contains a ‘(‘ ), push it.
…..3.2 Else, Pop all the operators from the stack which are greater than or equal to in
precedence than that of the scanned operator. After doing that Push the scanned
operator to the stack. (If you encounter parenthesis while popping then stop there and
push the scanned operator in the stack.)
4. If the scanned character is an ‘(‘, push it to the stack.
5. If the scanned character is an ‘)’, pop the stack and and output it until a ‘(‘ is
encountered, and discard both the parenthesis.
6. Repeat steps 2-6 until infix expression is scanned.
7. Print the output
8. Pop and output from the stack until it is not empty.
Simulation:
Note:
Consider each operand as a single character;
* and / has the same precedence;
+ and - has the same precedence;
* and / has a higher precedence than + and -.
Input Text: 1 + 2 * 3
1. Create Empty Stack
2. Read 1 Output: 1
3. + Read + push(+)
4. + Read 2 Output: 1 2
5. + * Read * push(*) p
recedence over +
6. + * Read 3 Output: 1 2 3
7. + * End of Input reached
8. + * Stack not empty - pop() Output: 1 2 3 *
9. + Stack not empty - pop() Output: 1 2 3 * +
10. Stack empty - end of process - Output: 1 2 3 * +
