To understand the concept of a stack, first, we need to understand the principle of last in first out. For example, we are placing a bunch of books on a table. Now after placing the book, we want to take the books. So in order to take the last book out, first we need to take the books that are placed above it. That means, the book that we have placed last, will be taken first. And the book that we have placed first, will be taken last.
This principle is called the Last in First out principle.
The diagram below shows the diagrammatic representation of how elements are inserted and deleted from the stack in data structures.
Now, we will understand some of the operations that we perform on the stack.
- Push – Adding an element to the top of the stack.
- Pop – Removing an element from the stack. As we know, the element placed at the top will be removed.
- IsEmpty – This function checks if the stack is empty or not.
- IsFull – This function is used to check if the stack is full.
- Peek – This function gets the value at the top without removing the element.
Working of Stack in Data Structures
Now, we will understand the working of this data structure –
- A pointer called top is initialized with the value -1 which I pointing the topmost element of the stack. This is initialized with the value -1 because after inserting the first element, it is placed at index 0.
- On pushing an element, we increase the value of TOP and place the new element in the position pointed to by TOP.
- On popping an element, we return the element pointed to by TOP and reduce its value.
- Before pushing, we check if the stack is already full.
- Before popping, we check if the stack is already empty.
#include <stdlib.h>
#include <iostream>
using namespace std;
#define MAX 10
int size = 0;
struct stack {
int items[MAX];
int top;
};
typedef struct stack st;
void createEmptyStack(st *s) {
s->top = -1;
}
int isfull(st *s) {
if (s->top == MAX - 1)
return 1;
else
return 0;
}
int isempty(st *s) {
if (s->top == -1)
return 1;
else
return 0;
}
void push(st *s, int newitem) {
if (isfull(s)) {
cout << "STACK FULL";
} else {
s->top++;
s->items[s->top] = newitem;
}
size++;
}
void pop(st *s) {
if (isempty(s)) {
cout << "\n STACK EMPTY \n";
} else {
cout << "Item popped= " << s->items[s->top];
s->top--;
}
size--;
cout << endl;
}
void printStack(st *s) {
printf("Stack: ");
for (int i = 0; i < size; i++) {
cout << s->items[i] << " ";
}
cout << endl;
}
int main() {
int ch;
st *s = (st *)malloc(sizeof(st));
createEmptyStack(s);
push(s, 5);
push(s, 6);
push(s, 7);
push(s, 8);
printStack(s);
pop(s);
cout << "\nAfter popping out\n";
printStack(s);
}
Time Complexity for Stack –
The stack has a time complexity of O(1) for basic operations such as push and pop.
But, do we always need to write such big code to use stack?
To use the stack, one doesn’t always need to write such lengthy codes. The STL( Standard Template Library) in C++ provides an inbuilt class stack and all the functions defined.
We can check an example to see how this works –
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> stack;
stack.push(5);
stack.push(6);
stack.push(7);
stack.push(8);
stack.push(9);
stack.pop();
stack.pop();
while (!stack.empty()) {
cout << stack.top() <<" ";
stack.pop();
}
}
Output –
7 8 9
So, in this article, we learned about the stack data structure that is used quite often while programming. Mostly, it is used from the STL library as its easy to use.
Attempt Data structures online test
