A stack is defined as a list where all insertions and deletions are made only at one end, the top. It is a restricted list. Stack is often called last in first out (LIFO) or first in last out (FILO) data structure.
Every stack abstract
data type (ADT) has a data member, commonly named as top, which points
to the topmost element in the stack.
There are two basic
operations that can be performed on a stack: push and pop.
Insertion of an element
in the stack is called push and
deletion of an element from the stack is called pop.
Operations performed on a stack are:
1. Push—inserts an element on the top of the stack.
2. Pop—deletes an element from the top of the stack.
3. GetTop—reads an element from the top of the stack.
4. Stack_initialization—sets up the stack in an
empty condition.
5. Empty—checks whether the stack is empty.
6. Full—checks whether the stack is full.
Push
The push operation inserts an element on the top of
the stack. Before every push operation,
a check is made whether stack is full.
If stack is full it is called overflow
state.
The push operation modifies the top since the
newly inserted element becomes the topmost element.
Pop
The pop operation
deletes an element from the top of the stack and returns the element to the
user. Pop operation modifies the stack and makes next element in the stack as the
top element.
If there is no element
available on the stack, the stack is said to be empty. If pop is performed
when the stack is empty, then the stack is said to be in an underflow state.
Before every pop, ensure
that the stack is not empty. After deleting the last element from the stack,
the stack should be set to an empty state.
GetTop
The getTop operation
gives information about the topmost element and returns the element on the top
of the stack.
Top will not change
with this operation, a copy of top element is returned to the user. It signals
the stack underflow error if the stack is empty.
Stack
ABSTRACT DATA TYPE
Any sets of elements
that are of the same data type can be used as a data object for stacks.
The following five
functions comprise a functional definition of a stack:
1. Create(S)—creates an
empty stack
2. Push(i, S)—inserts
the element i on the stack S and returns the modified stack
3. Pop(S)—removes the
topmost element from the stack S and returns the modified stack
4. GetTop(S)—returns
the topmost element of stack S
5. Is_Empty(S)—returns
true if S is empty, otherwise returns false
Representation
of StackS using Sequential Organization (Arrays)
A stack can be
implemented using
-
a static data structure (array) and
-
a dynamic data structure (linked list)
The simplest way to
represent a stack is by using a one-dimensional array. The only difficulty with
an array is its static memory allocation. The size of array cannot be modified
during run-time.
Let Stack[n] be a one-dimensional array. When the
stack is implemented using arrays, one of the two sides of the array can be
considered as the top (upper) side and the other as the bottom (lower) side.
The elements are stored in the stack from the first
location onwards. The first element is stored at the 0th location of
the array Stack, which means at Stack[0], the second element at Stack[1], the ith
element at Stack[i - 1], and the nth element at Stack[n - 1].
The array has an integer variable, top, which
points to the top element in the stack. The initial value of top is -1 indicating
an empty stack. It can hold the elements from index 0, and can grow to a
maximum of n - 1.
Create
The stack when created
is initially empty. For array implementation, its size should be predefined,
and its implementation time should not exceed run-time.
For each and every
stack, there is an operational end operator variable called the top which
points to the element at the top of the stack. It is suitable to initialize the
top to -1.
int Stack[100];
int top = −1;
These statements create
an empty stack of size 100, which will hold integer values, and the variable top
is initialized to -1.
Empty
The stack empty state can be checked by comparing the value of top with
the value -1, because top = -1 represents an empty stack.
if(top == −1)
return 1;
else
return 0;
GetTop
The getTop operation checks for the stack empty state. If the stack is
empty, it reports the ‘stack underflow’ error message; else it returns a copy
of the element that is at the top of the stack.
if(top == −1)
cout <<
"Stack underflow (empty)" << endl;
else
return(Stack[top]);
Push
The push operation inserts an element onto the stack. Element insertion
is possible only if the stack is not full.
The stack full state can be verified by comparing the top with
MaxCapacity - 1. If the stack is not full, the top is incremented by 1 and the
element is added on the top of the stack.
if(top ==
MaxCapacity − 1)
cout <<
"Stack overflow (full)";
else
{
top ++;
//increment top by one
stack[top] =
Element; //add the element in new top position
}
Pop
The pop operation deletes the element at the top of the stack and
returns the same. This is done only if the stack is not empty. If the stack is
empty, no deletion is possible.
If the stack is not empty, then the element at the top of the stack is
returned and the top is decreased by one.
if(top == −1)
cout <<
"Stack underflow\n";
else
return(Stack[top−−]);
Code:
Implementation of Stack using Array
class Stack
{
private:
int Stack[50];
int MaxCapacity;
int top;
public:
Stack()
{
MaxCapacity = 50;
top = −1;
}
int getTop();
int pop();
void push(int Element);
int Empty();
int IsFull();
};
int Stack :: getTop()
{
if(!Empty())
return(Stack[top]);
}
int Stack :: Empty()
{
if(top == −1)
return 1;
else
return 0;
}
int Stack :: IsFull()
{
if(top == MaxCapacity − 1)
return 1;
else
return 0;
}
void Stack :: push(int Element)
{
if(!IsFull())
Stack[++top] = Element;
}
int Stack :: pop()
{
if(!Empty())
return(Stack[top−−]);
}
void main()
{
Stack S;
S.pop();
S.push(10);
S.push(20);
cout << S.getTop() << endl;
cout << S.pop() << endl;
cout << S.pop() << endl;
}
No comments:
Post a Comment