Stacks.md

Stacks

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).

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 top most 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 top most element of the stack – Time Complexity : O(1)

// CPP program to demonstrate working of STL stack
#include <bits/stdc++.h>
using namespace std;

void showstack(stack <int> s)
{
	while (!s.empty())
	{
		cout << '\t' << s.top();
		s.pop();
	}
	cout << '\n';
}

int main ()
{
	stack <int> s;
	s.push(10);
	s.push(30);
	s.push(20);
	s.push(5);
	s.push(1);

	cout << "The stack is : ";
	showstack(s);

	cout << "\ns.size() : " << s.size();
	cout << "\ns.top() : " << s.top();


	cout << "\ns.pop() : ";
	s.pop();
	showstack(s);

	return 0;
}

Output:

The stack is :     1    5    20    30    10

s.size() : 5
s.top() : 1
s.pop() :     5    20    30    10

Standard Problems based on Stack :

1. Infix to Postfix Conversion using Stack
2. Prefix to Infix Conversion
3. Prefix to Postfix Conversion
4. Postfix to Prefix Conversion
5. Postfix to Infix
6. Convert Infix To Prefix Notation
7. The Stock Span Problem
8. Check for balanced parentheses in an expression
9. Next Greater Element
10. Next Greater Frequency Element