Stack Data Structure In C With Illustration - JohnHau/mis GitHub Wiki
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 will be the first element to be removed from the stack.
What You Will Learn: [hide]
Stack In C++ Basic Operations Illustration Implementation #1) Using Arrays #2) Using A Linked List Applications of Stack #1) Infix To Postfix Expressions #2) Expression Parsing/Evaluation #3) Tree Traversals #4) Sorting Algorithms #5) Towers Of Hanoi Conclusion Recommended Reading
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.
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.
#1) Using Arrays Following is the C++ implementation of stack using arrays:
#include using namespace std;
#define MAX 1000 //max size for stack
class Stack { int top; public: int myStack[MAX]; //stack array
Stack() { top = -1; } bool push(int x); int pop(); bool isEmpty(); }; //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; } }
//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); }
// 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; } Output:
The Stack Push
2
4
6
The Stack Pop:
6
4
2
In the output, we can see that the elements are pushed into the stack in one order and are popped out of the stack in the reverse order. This exhibits the LIFO (Last in, First out) approach for the stack.
For the above array implementation of the stack, we can conclude that this is very easy to implement as there are no pointers involved. But at the same time, the size of the stack is static and the stack cannot grow or shrink dynamically.
Next, we will implement the stack using arrays in Java programming language.
class Stack { static final int MAX = 1000; // Maximum Stack size int top; int myStack[] = new int[MAX];
boolean isEmpty() { return (top < 0); } Stack() { top = -1; }
boolean push(int item) { if (top >= (MAX-1)) { System.out.println("Stack Overflow"); return false; } else { myStack[++top] = item; System.out.println(item); return true; } }
int pop() { if (top < 0) { System.out.println("Stack Underflow"); return 0; } else { int item = myStack[top--]; return item; } } } //Main class code class Main { public static void main(String args[]) { Stack stack = new Stack(); System.out.println("Stack Push:"); stack.push(1); stack.push(3); stack.push(5); System.out.println("Stack Pop:"); while(!stack.isEmpty()) { System.out.println(stack.pop()); } } } Output:
Stack Push:
1
3
5
Stack Pop:
5
3
1
The implementation logic is the same as in C++ implementation. The output shows the LIFO technique of pushing in and popping out of the elements to/from the stack.
As already stated stack implementation using arrays is the simplest implementation but is of static nature as we cannot dynamically grow or shrink the stack.
#2) Using A Linked List Next, we implement stack operations using a linked list in both C++ and Java. First, we will demonstrate the C++ implementation.
#include using namespace std;
// class to represent a stack node class StackNode { public: int data; StackNode* next; };
StackNode* newNode(int data) { StackNode* stackNode = new StackNode(); stackNode->data = data; stackNode->next = NULL; return stackNode; }
int isEmpty(StackNode *root) { return !root; }
void push(StackNode** root, int new_data){ StackNode* stackNode = newNode(new_data); stackNode->next = *root; *root = stackNode; cout<<new_data<<endl; }
int pop(StackNode** root){ if (isEmpty(root)) return -1; StackNode temp = *root; *root = (*root)->next; int popped = temp->data; free(temp);
return popped; } int peek(StackNode* root) { if (isEmpty(root)) return -1; return root->data; }
int main() { StackNode* root = NULL; cout<<"Stack Push:"<<endl; push(&root, 100); push(&root, 200); push(&root, 300); cout<<"\nTop element is "<<peek(root)<<endl; cout<<"\nStack Pop:"<<endl; while(!isEmpty(root)){ cout<<pop(&root)<<endl; }
cout<<"Top element is "<<peek(root)<<endl;
return 0; } Output:
Stack Push:
100
200
300
Top element is 300
Stack Pop:
300
200
100
Top element is -1
Next, we present the Java implementation of the stack using a linked list.
class LinkedListStack {
StackNode root;
static class StackNode { int data; StackNode next;
StackNode(int data) {
this.data = data;
}
}
public boolean isEmpty() { if (root == null) { return true; } else return false; }
public void push(int new_data) { StackNode newNode = new StackNode(new_data);
if (root == null) { root = newNode; } else { StackNode temp = root; root = newNode; newNode.next = temp; } System.out.println(new_data); }
public int pop() { int popped = Integer.MIN_VALUE; if (root == null) { System.out.println("Stack is Empty"); } else { popped = root.data; root = root.next; } return popped; } public int peek() { if (root == null) { System.out.println("Stack is empty"); return Integer.MIN_VALUE; } else { return root.data; }
}
} class Main{ public static void main(String[] args) {
LinkedListStack stack = new LinkedListStack(); System.out.println("Stack Push:"); stack.push(100); stack.push(200); stack.push(300); System.out.println("Top element is " + stack.peek());
System.out.println("Stack Pop:"); while(!stack.isEmpty()){ System.out.println(stack.pop()); } System.out.println("Top element is " + stack.peek()); } } Output:
Stack Push:
100
200
300
Top element is 300
Stack Pop:
300
200
100
Stack is empty
Top element is -2147483648
We have just seen C++ and Java implementations for a stack using linked lists. We represent each stack entry as a node of the linked list. The most important advantage of this implementation is that it is dynamic. This means that we can grow or shrink the stack size as per our requirement.
This is unlike the case of stack implementation using arrays in which we have to declare the size beforehand and cannot change it dynamically.
The con for this implementation is that as we use pointers everywhere, it takes up a little too much space when compared to array implementation.
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+bc”. 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 bc. 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.
#2) Expression Parsing/Evaluation Using stack, we can also carry out actual expression evaluation. In this, the expression is scanned left to right, and operands are pushed on to the stack.
Whenever an operator is encountered, operands are popped out and the operation is performed. The result of the operation is again pushed into the stack. This way in which the expression is evaluated by using stack and the final result of the expression is usually the current top of the stack.
#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.
#5) Towers Of Hanoi This is a classic problem involving n number of discs and three towers and the problem involves moving the discs from one tower to another with the third tower used as intermediate.
This problem can be efficiently tackled using the stack as we push the discs to be moved on to the stack as stack basically acts as a tower used to move the discs.
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.
Further reading =>> Frequently asked Data Structure Interview Questions
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.
In our upcoming tutorial, we will learn about the queue data structure in detail.