STACKS IN C++
Presented by.
Kafayat (BSE-O88)
Noor Zakriya (075)
Mavia Zafar(056)
Makhdoom Hamza(089)
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> Ei;EVLJU;I
using namespace std;
const int MAX=4;
int stack_array[MAX];
int top = -1;
void push(int data);
int main(){
int data;
push(1);
push(2);
push(3);
push(4);
// push(5);
data = pop();
}
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 while(1)
{ strcpy(arr[top].name,n); { cout<<”1.push”<<”\n
int roll; 2.pop”<<”\
char name[20]; arr[top].total=tot; } n3.display”<<”\n 4.exit”;
float total; void pop() cout<<”Enter choice :”;
}; { if (top== -1) cin>>ch;
class stack cout<<”Stack is if (ch==1)
{ stu arr[size]; empty “; { cin>>data;
int top; else
public: { cout<<arr[top].roll<< s1.push(data); }
stack() { top=-1; } else if (ch == 2)
void push(int r, arr[top].name<<arr[top].tot; { s1.pop(); }
char top - -; } else if (ch==3)
n[20],float tot) void display() { s1.display();
{ if { }
(top==size-1) for(int i=top;i>=0;i--) else
cout<<arr[top].roll<< 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.
Questions
or
Queries?
Thank you!
