What's Stack & Implementation?

5MB

StacksAndQueues.pdf

pdf

Stacks are a type of container adaptor with LIFO(Last In First Out) type of work, where a new element is added at one end (top) and an element is removed from that end only. Stack uses an encapsulated object of either vector or deque (by default) or list (sequential container class) as its underlying container, providing a specific set of member functions to access its elements.

If there is confusion in remembering the basic difference between stack and queue, then just have a real-life example for this differentiation, for the stack, stacking of books we can take the top book easily, and for queue remember when you have to stand in queue front of ATM for taking out the cash, then first person near to ATM has the first chance to take out the money from ATM. So, a queue is the FIFO (First In First Out) type working.

Stack Syntax:-

For creating a stack, we must include the <stack> header file in our code. We then use this syntax to define the std::stack:

The functions associated with stack are: empty() – Returns whether the stack is empty – Time Complexity: O(1) size() – Returns the size of the stack – Time Complexity: O(1) top() – Returns a reference to the topmost element of the stack – Time Complexity: O(1) push(g) – Adds the element ‘g’ at the top of the stack – Time Complexity: O(1) pop() – Deletes the most recent entered element of the stack – Time Complexity: O(1)

#include <iostream>
#include <stack>
using namespace std;
int main() {
	stack<int> stack;
	stack.push(21);// The values pushed in the stack should be of the same data which is written during declaration of stack
	stack.push(22);
	stack.push(24);
	stack.push(25);
	int num=0;
	stack.push(num);
	stack.pop();
	stack.pop();
	stack.pop();

	while (!stack.empty()) {
		cout << stack.top() <<" ";
		stack.pop();
	}
}

Output

22 21 

Time complexity: The time complexity of this program is O(N), where N is the total number of elements in the stack. The while loop iterates N times, popping and printing elements from the stack.

Space complexity: The space complexity of this program is O(N), where N is the total number of elements in the stack. The stack data structure uses space proportional to the number of elements stored. In this case, the maximum size of the stack is 5, so the space complexity is constant and can be considered as O(1) as well.