Stacks
Algorithms & Data Structures
2
Introduction to Stacks
What is a Stack?
Stack implementation using array.
Stack implementation using structure.
Applications of Stacks.
Stacks
3
A stack is a linear data structure which can be
accessed only at one of its ends for storing and
retrieving data.
A LIFO (Last In First Out) structure
What is a Stack?
4
A stack is a data structure in which data is added and removed at
only one end called the top.
To add (push) an item to the stack, it must be placed on the top of
the stack.
To remove (pop) an item from the stack, it must be removed from
the top of the stack too.
Thus, the last element that is pushed into the stack, is the first
element to be popped out of the stack.
i.e., A stack is a Last In First Out (LIFO) data structure
An Example of a Stack
5
top 2
top 8 8
top 1 1 1
Push(8) Push(2)
7 7 7
2 2 2
pop()
top 8
top 1
1
top 7 7 pop()
pop() 7
2 2
2
Operations on a stack
6
initialize(stack) --- clear the stack
empty(stack) --- check to see if the stack is empty
full(stack) --- check to see if the stack is full
push(el, stack) --- put the element el on the top of the stack
pop(stack) --- take the topmost element from the stack
AbstractContainer class and implements the Stack interface
7
In our implementations, a stack is a container that
extends the AbstractContainer class and
implements the Stack interface:
//…………………..filename.h (for example ty.h) ……………….
#define max 6
struct stackst
{
int stackarray[max];
int top;
};
Stack Implementations
8
// stack.h: interface for the stack class.
#include "ty.h"
class stack
{
public:
void clear(stackst *s);
int pop(stackst *s);
void push(stackst *s,int x);
int full(stackst *s);
int empty(stackst *s);
stack();
virtual ~stack();
};
// stack.cpp: implementation of the stack class.
9 #include "stack.h"
#include <iostream.h>
#include <stdlib.h>
void stack::clear(stackst *s)
{
s->top=-1;
}
int stack::full(stackst *s)
{
if(s->top==max)
return(1);
else
return(0);
}
int stack::empty(stackst *s)
{
if(s->top==-1)
return(1);
else
return(0);
}
10 void stack::push(stackst *s,int x)
{
s->top++;
if(full(s))
{
cout<<"Stack full......"<<endl;
exit(0);
}
s->stackarray[s->top]=x;
}
int stack::pop(stackst *s)
{
if(empty(s))
{
cout<<"Stack empty......"<<endl;
exit(0);
}
return(s->stackarray[s->top--]);
}
11
Lab Exercise:-
Write a program in C++ to implement stack using:-
1- by using array of structure.
Homework:-
1- write a C++ program for concatenation of two strings using stack?
2- Write a c++ program to sort an unsorted stack?
