UNIT II

STACK

A Stack is linear data structure. A stack is a list of elements in which an element may be inserted
or deleted only at one end, called the top of the stack. Stack principle is LIFO (last in, first out). Which
element inserted last on to the stack that element deleted first from the stack.

As the items can be added or removed only from the top i.e. the last item to be added to a stack is
the first item to be removed.

Real life examples of stacks are:

REPRESENTATION OF A STACK

A stack may be represented in the memory in various ways.

There are two main ways:

 One-dimensional array
 Single linked list.

ARRAY REPRESENTATION OF STACK

In the computer’s memory, stacks can be represented as a linear array.

Every stack has a variable called TOP associated with it, which is used to store the address of the
topmost element of the stack.

It is this position where the element will be added to or deleted from. There is another variable
called MAX, which is used to store the maximum number of elements that the stack can hold. If TOP =
NULL, then it indicates that the stack is empty and if TOP = MAX–1, then the stack is full.

The stack in Fig. shows that TOP = 4, so insertions and deletions will be done at this position.In
the above stack, five more elements can still be stored.

OPERATIONS ON A STACK

A stack supports three basic operations: push, pop, and peek.

PUSH: The push operation adds an element to the top of the stack
 POP: The pop operation removes the element from the top of the stack.

PEEK: The peek operation returns the value of the topmost element of the stack.

PUSH OPERATION

The push operation is used to insert an element into the stack. The new element is added at the
topmost position of the stack. However, before inserting the value, we must first check if TOP=MAX–
1,because if that is the case, then the stack is full and no more insertions can be done. If an attemptis
made to insert a value in a stack that is already full, an OVERFLOW message is printed.

To insert an element with value 6, we first check if TOP=MAX–1. If the condition is false, then
we increment the value of TOP and store the new element at the position given by stack [TOP].

Algorithm to PUSH an element in a stack

Step 1: If Top = Max-1, Then

Print “Overflow”

Goto Step 4

[End Of If]

Step 2: Set Top = Top + 1

Step 3: Set Stack [Top] = Value

Step 4: End

To insert an element in a stack, we first check for the OVERFLOW condition, then TOPis
incremented so that it points to the next location in the array, the value is stored in the stack at the
location pointed by TOP.

POP OPERATION

The pop operation is used to delete the topmost element from the stack. However, before deleting
the value, we must first check if TOP=NULL because if that is the case, then it means the stack is empty
and no more deletions can be done. If an attempt is made to delete a value from a stack that isalready
empty, an UNDERFLOW message is printed.

Algorithm to POP an element from a stack

Step 1: If Top = Null, Then

Print “Underflow”

Goto Step 4
 [End Of If]

Step 2: Set Val = Stack[Top]

Step 3: Set Top = Top - 1

Step 4: End

To delete the topmost element, we first check if TOP=NULL. If the condition is false, then we
decrement the value pointed by TOP.

To delete an element from a stack, we first check for the UNDERFLOW condition, the value of
the location in the stack pointed by TOP is stored in VAL, TOP is decremented.

PEEK/PEEP OPERATION

Peek is an operation that returns the value of the top most element of the stack without
deleting it from the stack. However, the Peek operation first checks if the stack is empty ,i.e., if
TOP = NULL, then an appropriate message is printed, else the value is returned.

Algorithm for Peek/Peep Operation

Step 1: If Top =Null, Then

Print “Stack Is Empty”

Go To Step 3

[End of If]

Step 2: Return Stack [Top]

Step 3: End

Here, the Peek operation will return 5, as it is the value of the topmost element of the stack.
LINKED LIST REPRESENTATION OF STACKS

Although array representation of stacks is very easy and convenient but it allows the
representation of only fixed sized stacks. A single linked list structure is sufficient to represent any stack.
Here, the DATA field is for the ITEM, and the LINK field is, as usual, to point to the next' item.

In the linked list representation, the first node on the list is the current item that is the item at the
top of the stack and the last node is the node containing the bottom-most item. Thus, a PUSH operation
will add a new node in the front and a POP operation will remove a node from the front of the list.
APPLICATIONS OF STACKS

In this section we will discuss typical problems where stacks can be easily applied for a simple
and efficient solution. The topics that will be discussed in this section include the following:

 Reversing a list
 Parentheses checker
 Conversion of an infix expression into a postfix expression
 Evaluation of a postfix expression
 Conversion of an infix expression into a prefix expression
 Evaluation of a prefix expression
 Recursion
 Tower of Hanoi
 Parsing
 Browsers
 Editors
 Tree Traversals

BALANCED PARANTHESES:

Use of parentheses - must be balanced

Examples : A { b [c (d + e)/2 –f ] + 1}, } ] ) ( [ {

Figure 1 The contents of a stack during the scan of an expression that contains the balanced

delimiters { [ ( ) ] }

CONVERTING AND EVALUATING ALGEBRAIC EXPRESSIONS:

 An algebraic expression is a legal combination of operators and operands.

 Operand is the quantity on which a mathematical operation is performed. Operand may
be a variable like x, y, z or a constant like 5, 4, 6 etc.
 Operator is a symbol which signifies a mathematical or logical operation between the
operands. Examples of familiar operators include +, -, *, /, ^ etc.

An algebraic expression can be represented using three different notations.

 They are infix, postfix and prefix notations:

Infix: It is the form of an arithmetic expression in which we fix (place) the arithmetic operator in
between the two operands.

Example: A + B
Prefix: It is the form of an arithmetic notation in which we fix (place) the arithmetic operator before
(pre) its two operands. The prefix notation is called as polish notation.

Example: + A B

Postfix: It is the form of an arithmetic expression in which we fix (place) the arithmetic operator after
(post) its two operands. The postfix notation is called as suffix notation and is also referred to reverse
polish notation.

Example: A B +

Algorithm Infix To Postfix

Input: E, simple arithmetic expression in infix notation delimited at the end by the right parenthesis ')',
incoming and in-stack priority values for all possible symbols in an arithmetic expression.

Output: An arithmetic expression in postfix notation.

Data structure: Array representation of a stack with TOP as the pointer to the top-most element.
Convert the following infix expression into postfix expression using the algorithm

A – (B / C + (D % E * F) / G)* H

(A – (B / C + (D % E * F) / G)* H)

Evaluation of postfix expression:

The postfix expression is evaluated easily by the use of a stack.

1. When a number is seen, it is pushed onto the stack;

2. When an operator is seen, the operator is applied to the two numbers that are popped from the stack
and the result is pushed onto the stack.

3. When an expression is given in postfix notation, there is no need to know any precedence rules; this is
our obvious advantage.