Data Structure - Stack

A stack is an ordered collection of homogeneous data elements, where the insertion and deletion operation take place at one end.
 Similar to array and linked list, attack is also linear data structure.
 Only difference compared to array and link list, insertion and deletion operations takes place at any position.
 In stack, Insertion and deletion operation specially termed as PUSH and POP respectively.
 Some terminologies of stack are TOP, ITEM, and SIZE.
TOP – Position of the stack, where operations are preformed.
ITEM – Element in a stack.
SIZE – Maximum number of elements that a stack can accommodate.


Fig. 1. Schematic diagram of stack.
Representation of Stack:
 Stack may be represented in the memory in various ways.
 The two main ways are,
1. Stack using one dimensional array.
2. Stack using single link list.
Array Representation:
 First, we have to allocate a memory block of sufficient size to accommodate the full capacity.
 Start from the first location of the memory block.
 For array representation the following two ways, stated
Empty: Top < 1 Full: Top >= u, s = u + 1-1
 Where S is the size of the stack.
 l and u are the lower and upper value respectively.
Operations on Stack (Array):
 Basic operations required to manipulate a stack,
PUSH – To insert an item into a stack
POP – To remove an item from a stack
Algorithm PUSH:
1. If Top >= Size, then
2. Print “Stack is full”
3. Else
4. Top = Top + 1
5. A[Top] = Item
6. Endif
7. Stop
Algorithm POP:
1. If Top<1, then 2. Print “Stack is empty” 3. Else 4. Item = A[Top} 5. Top = Top – 1 6. Endif 7. Stop Link List Representation of Stack:  Even though array representation of stack is very easy but it allows only pre defined stack size.  Some application size of the stack may vary during execution.  To overcome this problem we go for stack using link list.  In line the DATA field and LINK field as usual to point the next item.  In link list, first nose is the current item (top) of the stack.  Last node containing the bottom most element.  PUSH and POP operations perform the normal function. (Insertion, Deletion)  The size of the stack is not important here because, it follows dynamic stack instead of stack.  In link list, the test for overflow is not applicable in this case. Stack head Top Fig. 2. Representation of Stack in Linked List Algorithm PUSH: /* Linked List*/ 1. New = Get node (Node) /*Insert at front*/ 2. New DATA = Item 3. New LINK = Top 4. Top = New 5. Stack head LINK = Top 6. Stop Algorithm POP: /* Linked List*/ 1. If Top = NULL 2. Print “Stack is empty” 3. Exit 4. Else 5. ptr = Top LINK 6. Item = Top DATA 7. Stack head LINK = ptr 8. Top = ptr 9. Endif 10. Stop 11. Application of Stack:  Classical application in a compiler design is the evaluation of arithmetic expression.  Compiler uses a stack to translate an input arithmetic expression into its corresponding object code.  Some programming languages uses stack to run recursive program.  Another important feature of any programming language is the binding of memory variables. Evaluation of Arithmetic Expressions:  An arithmetic expression consists of operands operators.  Operands – Variables are constant.  Operators – Various types such as arithmetic unary and binary operators. There are three types of expressions, 1. Infix expressions 2. Postfix expression 3. Prefix expression Infix Expressions:  In this type of expressions the arrangement of operands and operator as follows, Infix expression = Operand1 operator operand2 For Ex: 1. (a+b) 2. (a+b) * (c-d) 3. (a+b/e) *(d+f)  Infix expressions are the most natural way of representing the expression. Postfix Expressions:  In this type of expressions the arrangement of operands and operator is as follow Postfix expression = Operand1 operand2 Operator For Ex: 1. ab+ 2. ab+cd–* 3. ab+e/df+*  In postfix expressions there are no parenthesis used. All the corresponding operands comes first and then operators can be placed. Prefix Expressions:  In these type of expressions the arrangement of operands and operator is as follows, Prefix expression = Operator Operand1 operand2 For Ex: 1. +ab 2. *+ab-cd 3. */+ abe + df  In prefix expressions, there is no parenthesis used.  All the corresponding operators come first and then operands are arranged. Rules for Converting Infix expression to Postfix: 1. The expression is to be read from left to right. 2. Read one character at a time from infix expression. 3. Make use of the stack to store the operators. 4. There should not be any parenthesis in the postfix form. Sample Conversion: (a + b) * (c – d), convert to prefix, Prefix expression = Operator Operand1 operand2 = (+ ab) * (– cd) = t * s = * ts = * + ab – cd ((a+b)/e) * (d+f), convert to postfix, Postfix expression = Operand1 operand2 Operator = (ab +/e) * (df+) = (t/e) * (df+) = (te/) * (df+) = (ab + e/) * (df +) = ab +e / df +* (a*b) + (c/d), convert to postfix, = (ab*) + (cd/) = t+s = ab* cd/ + ((a+b) + (c/d) – (E ^ (F*G)), convert to postfix, = ((a+b) + (c/d) – (e^(fg*)) = ((ab+) + (cd/) – (efg*^) = x + y – z = ab+ cd/ efg*^+– Infix to postfix using stack, A + (B*C) Input Stack Output A A + + A ( +( A B +( AB * +(* AB C +(* ABC ) +(*) ABC + ABC* ABC*+ ((A – (B+C)) * D $ (E+F)) to post fix, Input Stack Output ( ( ( (( A (( A – ((– A ( ((–( A B ((–( AB + ((–(+ AB C ((–(+ ABC ) ((–(+) ABC ((– ABC+ ) ((–) ABC+ ( ABC+– * (* ABC+– D (* ABC+–D $ (*$ ABC+–D ( (*$( ABC+–D E (*$( ABC+–DE + (*$(+ ABC+–DE F (*$(+ ABC+–DEF ) (*$(+) ABC+–DEF (*$ ABC+–DEF+ ) (*$) ABC+–DEF+ ABC+–DEF+$* 1) Infix to prefix using stack, (A+B) * C, Reverse the given expression, => C * ) B + A (
Input Stack Output
C C
* * C
) *) C
B *) CB
+ *)+ CB
A *)+ CBA
( *)+( CBA
CBA+
CBA+*

Reversing again the obtained result, => *+ABC
(A+B) * (C–D)
Reverse the given expression, => )D–C( * )B+A( ,
Input Stack Output
) )
D ) D
– ) – D
C ) – DC
( ) –( DC
DC–
* * DC–
) *) DC–
B *) DC–B
+ *)+ DC–B
A *)+ DC–BA
( *)+( DC–BA
* DC–BA+
DC–BA+*
Reversing again the obtained result, *+AB–CD