STACKS IN C++

INTRODUCTION TO STACK
DEFINITION:

 A stack is a data structure that provides temporary storage of data in such

a way that the element stored last will be retrieved first.
 This method is also called LIFO – Last In First Out.

EXAMPLE:

In real life we can think of stack as a stack of copies, stack of plates etc. The first
copy put in the stack is the last one to be removed. Similarly last copy to put in the
stack is the first one to be removed.
OPERATIONS ON STACK
 A stack is a linear data structure.
 It is controlled by two operations: push and pop.
 Both the operations take place from one end of the stack,
usually called top. Top points to the current top position of the
stack.
 Push operation adds an element to the top of the stack.
 Pop operation removes an element from the top of the stack.
 These two operations implements the LIFO method .
IMPLEMENTATION OF STACK
Stack can be implemented in two ways:

 As an Array
 As a Linked List
STACK AS AN ARRAY
Array implementation of stack uses 4

3
 an array to store data
 an integer type variable usually called the top, which 30
2
points to the top of the stack.
2 20 1

TOP
NOTE: The variable top contains the index number of 10 0

the top most filled element of the array.

PUSH OPERATION
 Initially when the stack is empty, TOP can have any integer value other
than any valid index number of the array. Let TOP =
-1;
 The first element in the empty stack goes to the 0th position of the array
and the Top is initialized to value 0.
 After this every push operation increase the TOP by 1 and inserts
new data at that particular position.
 As arrays are fixed in length, elements can not be inserted beyond the
maximum size of the array. Pushing data beyond the maximum size of
the stack results in “data overflow”.
PUSH OPERATION EXPLAINED

NOTE: Pushing one more element into the stack will result in overflow.
POP OPERATION
The pop operation deletes the most recently entered item from
the stack.
Any attempt to delete an element from the empty stack results in
“data underflow” condition.
The variable TOP contains the index number of the current top
position of the stack.
Each time the pop operation is performed, the TOP variable is
decremented by 1.
POP OPERATION EXPLAINED

top = 2
PROGRAM TO ILLUSTRATE OPERATIONS ON STACK AS AN INTEGER ARRAY
#include<iostream void pop() cout<<”1.push”<<”\n
.h> { if (top== -1) 2.pop”<<”\n3.display”
#include<process. cout<<”Stack is <<”\n 4.exit”;
h> const int size=5 empty “; else cout<<”Enter choice :”;
class stack { cin>>c
{ int arr[size]; cout<<arr[top h; if
int top; //top will point to the last item ]; top - -; } (ch==1)
//pushed onto the stack } { cout<<”enter item to
public: void display() be pushed in the
stack() { top=-1; } //constructor to { stack”; cin>>data;
create an for(int s1.push(data);
//empty stack, top=-1 i=top;i>=0;i--) }
indicate cout<<arr[to else if (ch == 2)
//that no item is present in the p]; {
array void push(int item) } s1.pop(); }
{ if(top==size-1) void main() else if (ch==3)
cout<<”stack is full, given item { stack s1; { s1.display(); }
cannot be added”; int else
else ch,data; exit(-1);
{ top++; while(1) }}
arr[top]=item {
;}
 PROGRAM TO ILLUSTRATE OPERATIONS ON STACK
AS AN ARRAY OF OBJECTS
#include<iostream.h> else void main()
#include<process.h> { top++; { stack s1;
const int size=5 arr[top].roll=r; int ch,data;
struct stu strcpy(arr[top].name,n); while(1)
{ arr[top].total=tot; } { cout<<”1.push”<<”\n
int roll; void pop() 2.pop”<<”\n3.display”<<”\n
char name[20]; { if (top== -1) 4.exit”;
float total; cout<<”Stack is empty “; cout<<”Enter choice :”;
}; else cin>>ch;
class stack { cout<<arr[top].roll<< if (ch==1)
{ stu arr[size]; arr[top].name<<arr[top].tot; { cin>>data;
int top; top - -; } s1.push(data); }
public: void display() else if (ch == 2)
stack() { top=-1; } { { s1.pop(); }
void push(int r, char for(int i=top;i>=0;i--) else if (ch==3)
n[20],float tot) cout<<arr[top].roll<< { s1.display(); }
{ if (top==size-1) arr[top].name<<arr[top].tot<<”\n”; else
cout<<”overflow”; } exit(-1); } }
 APPLICATIONS OF STACK
A stack is an appropriate data structure on which information is stored and
then later retrieved in reverse order. The application of stack are as
follows:

When a program executes, stack is used to store the return address at time
of function call. After the execution of the function is over, return address
is popped from stack and control is returned back to the calling function.

Converting an infix expression o postfix operation and to evaluate the

postfix expression.

Reversing an array, converting decimal number into binary number etc.

INFIX AND POSTFIX OPERATIONS
 The infix expression is a conventional algebraic
expression, in which the operator is in between
the operands.
For example: a+b

 In the postfix expression the operator is

placed after the operands.
For example: ab+
NEED OF POSTFIX EXPRESSION
The postfix expressions are special because

 They do not use parenthesis

 The order of expression is uniquely reconstructed
from the expression itself.

These expressions are useful in computer applications.

CONVERTING INFIX TO POSTFIX EXPRESSION
CONVERT_I_P(I,P,STACK) Where I = infix expression, P = postfix expression, STACK = stack as an array
Step 1. Push ‘(‘ into STACK and add ‘)’ to the end of I.
Step 2. Scan expression I from left to right and repeat steps 3-6 for each element of I
until the stack is empty.
Step 3. If scanned element =‘(‘ , push it into the
STACK. Step 4. If scanned element = operand, add it to
P.
Step 5. If scanned element = operator, then:
a)Repeatedly pop from STACK and add to P each operator from the top of the
stack until the operator at the top of the stack has lower precedence than the
operator extracted from I.
b) Add scanned operator to the top of the STACK.
Step 6. If scanned element = ‘)’ then:
c)Repeatedly pop from STACK and add to P each operator until the left
parenthesis is encountered.
d) Pop the left parenthesis but do not add to P.
CONVERTING INFIX TO POSTFIX EXPRESSION
Q Convert the following infix
operation to
postfix operation.

((TRUE && FALSE) || !

(FALSE || TRUE))

Ans. The Postfix expression is:

TRUE FALSE && FALSE

TRUE || ! ||
EVALUATION OF POSTFIX EXPRESSION
Evaluate(P, result, STACK)
where P=Postfix expression, STACK =stack, result=to hold the result of evaluation

Step 1. Scan the postfix expression P from left to right and repeat the steps 2, 3
until the STACK is empty.
Step 2. If the scanned element = operand, push it into the STACK.
Step 3. If the scanned element = operator, then
a) Pop the two operands viz operand A and operand B from the STACK.
b) Evaluate ((operand B) operator (operand A))
c) Push the result of evaluation into the STACK.
Step 4. Set result=top most element of the STACK.
 EVALUATING POSTFIX EXPRESSION
Q Evaluate the following Postfix expression:

TRUE FALSE || FALSE TRUE && ! ||

Ans. TRUE Step Symbol Scanned Operation Performed Stack Status

No.
1 TRUE TRUE
2 FALSE TRUE FALSE
3 || TRUE || FALSE =TRUE TRUE
4 FALSE TRUE FALSE
5 TRUE TRUE FALSE TRUE
6 && FALSE &&TRUE = FALSE TRUE FALSE
7 ! ! FALSE =TRUE TRUE TRUE
8 || TRUE || TRUE TRUE
STACK AS A LINKED LIST
LINKED LIST IMPLEMENTATION OF STACK USES

 A linked list to store data

 A pointer TOP pointing to the top most position of the stack.

NOTE: Each node of a stack as a linked list has two parts : data part and link part and
is created with the help of self referential structure.
The data part stores the data and link part stores the address of the next node of the
linked list.
NODE

TOP

DAT LIN
A K
PROGRAM TO ILLUSTRATE OPERATIONS ON STACK
AS A LINKED LIST
void stack::push() #include<iostream.h> node *temp=top; void main()
{ #include<conio.h> top=top->next; { stack st;
node *temp; temp=new struct node cout<<temp->roll<<temp- char ch;
node; cout<<"Enter roll { >name<<temp->total do
:"; cin>>temp->roll; int roll; <<"deleted { cout<<"stack
cout<<"Enter name :"; char name[20]; "; delete temp; options\nP
cin>>temp->name; float total; } push
cout<<"Enter total :"; node *next; else \nO Pop \nD
cin>>temp->total; temp- }; cout<<"Stack empty"; Display \nQ
>next=top; top=temp; class stack } quit"; cin>>ch;
} { void stack::display() switch(ch)
void stack::pop() node *top; { { case 'P':
{ public : node *temp=top; st.push();break
if(top!=NULL) stack() while(temp!=NUL ; case 'O':
{ { top=NULL;} L) st.pop();break;
void push(); { case 'D':
void pop(); cout<<temp->roll<<temp- st.display();break;
void display(); >name<<temp->total<<" }
}; "; temp=temp->next; }while(ch!='Q');
} } }
 PROGRAM TO ILLUSTRATE OPERATIONS
ON STACK
AS A LINKED LIST : EXPLANATION
struct node
{ Self Referential Structure: These are special structures which
int roll; contains pointers to themselves.
char name[20]; Here, next is a pointer of type node itself.
float total; Self Referential structures are needed to create Linked Lists.
node *next;
};

class stack
{
node *top;
public : class stack: It contains pointer TOP which will point to the top
stack() of the stack.
{ top=NULL;} The constructor function initializes TOP to NULL.
void push();
void pop();
void
display();
};
 PROGRAM TO ILLUSTRATE OPERATIONS ON STACK
AS A LINKED LIST : EXPLANATION
void stack::push() void stack::pop()
{ {
node *temp; // pointer of type node if(top!=NULL) // if stack is not empty
temp=new node; // new operator will create a new {
//node and address of new node node *temp=top; // temp is a pointer
// is stored in temp //containing address of first node
cout<<"Enter roll :"; top=top->next; // top will now contain address of
cin>>temp->roll; These lines will input //second node
cout<<"Enter name :"; values into roll , name
cin>>temp->name; and total of newly cout<<temp->roll<< // This line will
cout<<"Enter total :"; created node. temp->name<<temp->total display
cin>>temp->total; <<"deleted"; // data stored in
temp->next=top; // address stored in TOP gets // deleted node
//stored in next of newly delete temp; // delete operator will delete the node
//created node. // stored at temp
top=temp; // Top will contain address of }
// newly created node else
} cout<<"Stack empty";}