Stack data collection
STACK DATA STRUCTURE IN C++
All That You Need To Know About Stack In C++.
Stack is a fundamental data structure which is used to store elements in a linear fashion.
Stack follows LIFO (last in, first out) order or approach in which the operations are performed. This means that the element which was added last to the stack the will be the first element to be removed from stack.
STACK IN C++
As shown above, there is a pile of plates stacked on top of each other. If we want to add another item to it, then we add it at the top of the stack as shown in the above figure (left-hand side). This operation of adding an item to stack is called “Push”.
On the right side, we have shown an opposite operation i.e. we remove an item from the stack. This is also done from the same end i.e. the top of the stack. This operation is called “Pop”.
As shown in the above figure, we see that push and pop are carried out from the same end. This makes the stack to follow LIFO order. The position or end from which the items are pushed in or popped out to/from the stack is called the “Top of the stack”.
Initially, when there are no items in the stack, the top of the stack is set to -1. When we add an item to the stack, the top of the stack is incremented by 1 indicating that the item is added. As opposed to this, the top of the stack is decremented by 1 when an item is popped out of the stack.
Next, we will see some of the basic operations of the stack data structure that we will require while implementing the stack.
Basic Operations
Following are the basic operations that are supported by the stack.
- push – Adds or pushes an element into the stack.
- pop – Removes or pops an element out of the stack.
- peek – Gets the top element of the stack but doesn’t remove it.
- is Full – Tests if the stack is full.
- is Empty – Tests if the stack is empty
The above illustration shows the sequence of operations that are performed on the stack. Initially, the stack is empty. For an empty stack, the top of the stack is set to -1.
Next, we push the element 10 into the stack. We see that the top of the stack now points to element 10.
Next, we perform another push operation with element 20, as a result of which the top of the stack now points to 20. This state is the third figure.
Now in the last figure, we perform a pop () operation. As a result of the pop operation, the element pointed at the top of the stack is removed from the stack. Hence in the figure, we see that element 20 is removed from the stack. Thus the top of the stack now points to 10.
In this way, we can easily make out the LIFO approach used by stack.
Applications of Stack
Let us discuss some of the applications of the stack data structure. The stack data structure is used in a range of applications in software programming mainly because of its simplicity and ease of implementation.
We will briefly describe some of the applications of the stack below:
#1) Infix To Postfix Expressions
Any general Arithmetic expression is of the form operand1 OP operand 2.
Based on the position of operator OP, we have the following types of expressions:
- Infix – The general form of infix expression is “operand1 OP operand 2”. This is the basic form of the expression and we use in mathematics all the time.
- Prefix – When an operator is placed before the operands, it is a prefix expression. The general form of infix expression is “OP operand1 operand2”.
- Postfix – In postfix expressions, operands are written first followed by the operator. It has the form “operand1 operand2 OP”.
Consider the expression “a+b*c”. The compiler scans the expression either from left to right or right to left. Taking care of operator precedence and associativity, it will first scan the expression to evaluate the expression b*c. Next, it will again have to scan the expression to add the result of b*c to a.
As the expressions grow more and more complex, this kind of approach of again and again scanning the expression becomes inefficient.
In order to overcome this inefficiency, we convert the expression into postfix or prefix such that they can easily be evaluated using a stack data structure
#3) Tree Traversals
The tree data structure can be traversed to visit each node in many ways and depending on when the root node we have is visited.
- inOrder traversal
- preorder Traversal
- postOrder traversal
To efficiently traverse the tree, we make use of stack data structure in order to push intermediate nodes on the stack so that we maintain the order of traversal.
#4) Sorting Algorithms
Sorting algorithms like quicksort can be made more efficient using the stack data structures.
Conclusion
The stack is the simplest data structure and easier to implement as a program. It used the LIFO (last in, first out) approach which means the element entered last is the one that is removed first. This is because stack uses only one end to add (push) and remove (pop) elements.
The stack data structure has many uses in software programming. The prominent one among them is expression evaluations. Expression evaluation also includes converting the expression from infix to postfix or prefix. It also involves evaluating the expression to produce the final result.
In this tutorial, we have seen the illustration and implementation of the stack as well as its various operations.
OTHER RELATED VIDOES--------------#
Good
ReplyDeleteexcellent
ReplyDeleteKeep it up bruh h
ReplyDeleteNice it help full
ReplyDelete