What is stack in data structure
Introduction Stack
Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
There are many real-life examples of a stack. Consider an example of plates stacked over one another in the canteen. The plate which is at the top is the first one to be removed, i.e. the plate which has been placed at the bottommost position remains in the stack for the longest period of time. So, it can be simply seen to follow LIFO(Last In First Out)/FILO(First In Last Out) order.
stack
Some key points related to stack:
1). It is called as stack because it behaves like a real-world stack, piles of books, etc.
2).A Stack is an abstract data type with a pre-defined capacity, which means that it can store the elements of a limited size.
3).It is a data structure that follows some order to insert and delete the elements, and that order can be LIFO or FILO.
Standard Stack Operations:
The following are some common operations implemented on the stack:
- push(): When we insert an element in a stack then the operation is known as a push. If the stack is full then the overflow condition occurs.
- pop(): When we delete an element from the stack, the operation is known as a pop. If the stack is empty means that no element exists in the stack, this state is known as an underflow state.
- isEmpty(): It determines whether the stack is empty or not.
- isFull(): It determines whether the stack is full or not.'
- peek(): It returns the element at the given position.
- count(): It returns the total number of elements available in a stack.
- change(): It changes the element at the given position.
- display(): It prints all the elements available in the stack.
Stack Time Complexity
For the array-based implementation of a stack, the push and pop operations take constant time, i.e. O(1).
Applications of Stack Data Structure
Although stack is a simple data structure to implement, it is very powerful. The most common uses of a stack are:
- To reverse a word - Put all the letters in a stack and pop them out. Because of the LIFO order of stack, you will get the letters in reverse order.
- In compilers - Compilers use the stack to calculate the value of expressions like 2 + 4 / 5 * (7 - 9) by converting the expression to prefix or postfix form.
- In browsers - The back button in a browser saves all the URLs you have visited previously in a stack. Each time you visit a new page, it is added on top of the stack
- Balancing of symbols: Stack is used for balancing a symbol.
- String reversal: Stack is also used for reversing a string.
- UNDO/REDO: It can also be used for performing UNDO/REDO operations. For example, we have an editor in which we write 'a', then 'b', and then 'c'; therefore, the text written in an editor is abc.
- Recursion: The recursion means that the function is calling itself again. To maintain the previous states, the compiler creates a system stack in which all the previous records of the function are maintained.
- DFS(Depth First Search): This search is implemented on a Graph, and Graph uses the stack data structure.
- Expression conversion: Stack can also be used for expression conversion. This is one of the most important applications of stack
- Memory management: The stack manages the memory. The memory is assigned in the contiguous memory blocks. The memory is known as stack memory as all the variables are assigned in a function call stack memory.
stack operations Algorithm by using Linked list
1. PUSH:-When we insert an element in a stack then the operation is known as a push. If the stack is full then the overflow condition occurs.
{
ListNode temp = new ListNode(data);
temp.next=top;
top=temp;
length++;
}
2. POP:- When we delete an element from the stack, the operation is known as a pop. If the stack is empty means that no element exists in the stack, this state is known as an underflow state.
{
int result =top.data;
top=top.next;
length--;
return result;
}
3.isEmpty:- It determines whether the stack is empty or not.
{
return lenght==0;
}
4. peek:- It returns the element at the given position.
{
if(isEmpty())
{
System.out.println("stack is empty");
}
return top.data;
}
stack implementations ways
- how implement stack By using array
- how implement stack By using Linked list
- how implement stack By using stack class
Next Topic
No comments:
Post a Comment