Ø Stack
–
·
A stack is an Abstract Data Type (ADT), commonly used in most
programming languages.
·
It is named stack as it behaves like a real-world stack.
·
Stack is a LIFO
(Last in First out) structure or we can say FILO (First in Last
out).
·
Push () function is used to insert new elements into the Stack
and pop() function is used to remove an element from the stack.
·
Both insertion and
removal are allowed at only one end of Stack called Top.
·
Stack is said to be
in Overflow state when it is completely full and is said to be
in Underflow state if it is completely empty.
Stack Representation
The following diagram depicts a stack and its
operations −
A
stack can be implemented by means of Array, Structure, Pointer, and Linked
List. Stack can either be a fixed size one or it may have a sense of dynamic
resizing. Here, we are going to implement stack using arrays, which makes it a
fixed size stack implementation.
Implementation of Stack Data Structure
Stack
can be easily implemented using an Array or a Linked List. Arrays are quick,
but are limited in size and Linked List requires overhead to allocate, link,
unlink, and deallocate, but is not limited in size. Here we will implement
Stack using array.
Operations on stack –
1.
Push()
2.
Pop()
3.
Peek()
4.
Isfull()
5.
Isempty()
1)
Push() – push means
insert or adds an element in an stack. Steps of adds an element in stack –
·
Step 1 −
Checks if the stack is full.
·
Step 2 − If
the stack is full, produces an error and exit.
·
Step 3 − If
the stack is not full, increments top to point next empty
space.
·
Step 4 − Adds
data element to the stack location, where top is pointing.
·
Step 5 −
Returns success.
Algorithm
of push operation –
Begin procedure push: stack,
data
if stack is full
return null
endif
top <- top + 1
stack[top] <- data
end procedure
2) Pop() – pop() means
deleting or removing an element from stack. A Pop operation may involve
the following steps −
·
Step 1 −
Checks if the stack is empty.
·
Step 2 − If
the stack is empty, produces an error and exit.
·
Step 3 − If
the stack is not empty, accesses the data element at which top is
pointing.
·
Step 4 −
Decreases the value of top by
·
Step 5 −
Returns success.
Algorithm of pop() –
Begin procedure push: stack, data
if stack is full
return null
endif
data <- stack[top]
top <- top - 1
end procedure
3) Isfull() –
this function check if the stack is full.
Algorithm
of isfull() –
begine procedure isfull
if top equal to MAXSIZE
return true
else
return false
endif
4)
Isempty
() –this function checks the stack is empty.
Algorithm of isempty()
begine procedure isempty
if top equal to MIN
return true
else
return false
endif
5) Peek() – peek mean
get the top element of the stack