Stack Abstract Data Type in Data structures

Stack Abstract Data Type in Data structures

1. Stack ADT
•A Stack is a linear data structure where the collection of items are
accessed by Last In First Out (LIFO) or First In Last Out (FILO) order.
•A Stack represents an ordered collection of homogeneous (same data
type) elements.
•Both insertion , deletion operations can be done only at one end (last
element), called the top of the stack.
•We can implement Stack using Array or Linked List.
•Stack also referred as “Push-down lists”.
•Real-Time Examples of Stack :
- Car Parking
- Pile of Coins
- Stack of trays
- Pile of Notebooks - Coaches of Train

2. Representation of Stack Model:

3. •The first element placed in the stack will be the bottom of the
stack.
•The last element placed in the stack will be at the top of the stack.
•The last element added to the stack is the first element to be
popped out.
•Hence stacks are referred to as Last In First Out or First In Last
Out.

4. •Exceptional Conditions: Overflow Condition:
- An attempt to insert an element when the stack is full
is said to be Overflow and the new can not be pushed.
•Underflow Condition:
- An attempt to delete an element when the stack is
empty is
•said to be Underflow and
•Ways of Implementation of Stack :
→Array Implementation
→Linked List Implementation

5. Implementation of Stack
•A stack represents an ordered collection of
homogeneous elements.
•It can be implemented using arrays / linked list.
•Arrays – Better implementation when the number of
elements are known.
•Linked list – Better implementation when the number
of elements are not known.

6. Array Implementation of Stack:

7. Operations of Stack
•Create (S) – Create an empty Stack
•Push (S, element) – Inserts an element
•Pop (S) – Deletes an element
•ShowTop (S) – Returns the Top element

8. Create (S)
void create (STACK *S)
{
S[TOP] = -1; // S→Top
}
•Create an empty stack.
•Initializes the space to be used for elements to be pushed.
•Allocation of space can be Static using arrays or Dynamic using linked
list.
•As all operations are performed on the top element, we need to have
the index or the pointer to it ( Top pointer).
•Top pointer should be properly initialized to denote an empty stack.

9. class Stack {
int top;
public:
int myStack[MAX]; //stack array
Stack()
{
top = -1;
}
bool push(int x);
int pop();
bool isEmpty();
};

10. //pushes element on to the stack
bool Stack::push(int item)
{
if (top >= (MAX-1))
{
cout << "Stack Overflow!!!";
return false;
}
else
{
myStack[++top] = item;
cout<<item<<endl;
return true; } }

11. //removes or pops elements out of the stack
int Stack::pop()
{
if (top < 0)
{
cout << "Stack Underflow!!";
return 0;
}
else
{
int item = myStack[top--];
return item; } }
//check if stack is empty
bool Stack::isEmpty()
{
return (top < 0);
}

12. // main program to demonstrate stack functions
int main()
{ class Stack stack;
cout<<"The Stack Push "<<endl;
stack.push(2);
stack.push(4);
stack.push(6);
cout<<"The Stack Pop : "<<endl;
while(!stack.isEmpty())
{
cout<<stack.pop()<<endl;
}
return 0; }