1. Introduction to Stacks #
Created Wednesday 22 January 2020
Every DS has its pros and cons:
- Variables can store and acess elements, but not more than one.
- Arrays store many variables all at once, but cannot be resized due. This is not applicable to vectors.
- Linked list solves the issue of no. of elements, i.e no space is wasted. Non contiguity is allowed. But we cannot go back and forth, in a singly linked list.
We can compare access, insertion and removal for all the possible cases.
Stack is an Abstract Data Type. i.e LIFO(from the elements POV) owill be followed for any operations. Both LL and Arrays can be used here.
- As it is an ADT, the internal physical DS’s arrays and LLs are not to worried about.
- Visualize as a vertical stack.
- FIFO means that entry and exit points are same. And that they change with each deletion and insertion.
Working
- We will block direct access by making the DS’s address as private.
- Only the interface functions are available to the user
Jargon(Stack interface):
- push - insertion into the stack
- pop - deletes an(the element at top) element and returns the value.
- top() - Access the top most element. Returns a copy of the topmost element. No changes made in the stack.
- size() - returns number of elements in the stack.
- isEmpty() - returns boolean true if stack is empty, else false.
- Recursion requires stack ADT. The elements are the activation records.