DS"Quiz Time:Test Your Brainpower!"
Quiz SimulationSTACK
What is Stack?
A stack is a linear data structure in which the insertion of a new element and removal of an existing element takes place at the same end represented as the top of the stack. To implement the stack, it is required to maintain the pointer to the top of the stack, which is the last element to be inserted because we can access the elements only on the top of the stack.
Basic Operations on Stack
In order to make manipulations in a stack, there are certain operations
provided to us.
● push() to insert an element into the stack
● pop() to remove an element from the stack
● top() Returns the top element of the stack.
● isEmpty() returns true if stack is empty else false.
● size() returns the size of stack
Push:
Adds an item to the stack. If the stack is full, then it is said to be an Overflow
condition.
Algorithm for push:
Pop:
Removes an item from the stack. The items are popped in the reversed order
in which they are pushed. If the stack is empty, then it is said to be an
Underflow condition.
Algorithm for pop:
Top:
Returns the top element of the stack.
Algorithm for Top:
isEmpty:
Returns true if the stack is empty, else false.
Algorithm for isEmpty:
Types of Stacks
● Fixed Size Stack:
As the name suggests, a fixed size stack has a
fixed size and cannot grow or shrink dynamically. If the stack is
full and an attempt is made to add an element to it, an overflow
error occurs. If the stack is empty and an attempt is made to
remove an element from it, an underflow error occurs.
● Dynamic Size Stack:
A dynamic size stack can grow or shrink
dynamically. When the stack is full, it automatically increases its
size to accommodate the new element, and when the stack is
empty, it decreases its size. This type of stack is implemented
using a linked list, as it allows for easy resizing of the stack.
Implentation Of Stack
Stack Can Be Implented using Two Ways:
● STACK using ARRAY
● STACK using LINKED LIST
Advantages of Stack
Advantages of array implementation:
● Easy to implement.
● Memory is saved as pointers are not involved
Advantages of Linked List implementation:
● The linked list implementation of a stack can grow and shrink
according to the needs at runtime.
● It is used in many virtual machines like JVM.
Disadvantages of Stack
Disadvantages of array implementation:
● It is not dynamic i.e., it doesn’t grow and shrink depending on
needs at runtime. [But in case of dynamic sized arrays like vector
in C++, list in Python, ArrayList in Java, stacks can grow and
shrink with array implementation as well].
● The total size of the stack must be defined beforehand.
Disadvantages of Linked List implementation:
● Requires extra memory due to the involvement of pointers.
● Random accessing is not possible in stack