Stack Data Structure in C++ STL with detailed explanation

by Aug 18, 2021C++, Coding0 comments

A stack in C++ is a type of data structure based on the last-in, first-out (LIFO) technique. Last in first out is a technique of storing data in data structure and retrieving data from the data structure.

It holds all the newly entered objects on top of all previously entered objects. In stack, the push operation does this job. The newly entered data is removed first from the stack. In stack, the pop operation does this job.

This means that the object that is entered last is retrieved first. This is the main reason that this technique is called the last in, first out.

While processing a stack there are two restrictions.

  • When the stack is full, a push operation is not allowed.
  • When the stack is empty a pop operation is not permitted.

C++ stack working explanation

From the given image, you can easily see the working of the stack.

Stack syntax:

To use the stack, we must include a stack header file <stack> “#include<stack>” or create our stack class. We will read about creating our stack class later on.

The syntax of defining the std::stack is as follows.

template <class type, class container = deque<type> > class stack;

TYPE:

It is the type of elements contained by the std::stack. It can be any type, i.e., any user-defined type or any valid type such as int, float, char, string, etc.

Container:

The container is the type of underlying container object.

Member types in C++ stack:

Value type: It is the first template parameter, and it denotes the element types.

Container type: It is the second template parameter, and it denotes the underlying container type.

Size type in the stack: The size type is an unsigned integral type.

Functions in C++ std::stack:

The stack STL (standard template library) provides us with about seven multiple functions and one equal to operator, which are as follows.

  • Stack::push(Val). This function adds the value “val” at the top of the stack. The time complexity of the Stack::push(Val) function is O (1).
  • Stack::pop(). This function deletes the topmost element of the stack. The time complexity of Stack::pop() function is O (1).
  • Stack::top(). This function returns a reference to the topmost element of the stack. The time complexity of Stack::top() function is O (1).
  • Stack::empty(). This function returns true if stack is empty and false if stack is not empty. The time complexity of Stack::empty() function is O (1).
  • Stack::emplace(Val). This function constructs and inserts the new element at the top of the stack. The new element is inserted in a place by stack::emplace() function without performing copy or moving operation. The time complexity of stack::emplace() is O (1).
  • Stack::size(). This function returns the size of the stack. The time complexity of Stack::size() function is O (1).
  • Stack::swap(stack name 2). The main functionality of the stack::swap() function is that it swaps the elements of one stack with another of the same type, but the stack size may vary. The time complexity of stack::swap() function is O (1).
  • Stack::operator=( stack 2 object). The main functionality of stack::operator = () is that it assigns new content to the stack and replaces the old content. It also modifies the size of the operator if necessary. The time complexity of stack::operator() is O (N).

C++ code of stack using Stack standard template library (STL).

//C++ code of stack using Stack standard template library.
#include<iostream>
#include<stack>// stack library or stack standard template library STL
using namespace std;
int main()
{
	stack<int> obj;// create stack object
	obj.push(1);// push 1 in stack
	obj.push(2);// push 2 in stack
	obj.push(3);// push 3 in stack
	obj.push(4);// push 4 in stack
	obj.push(5);// push 5 in stack
	cout << " top value of stack is : " << obj.top() << endl;// it returns the top most value of stack
	cout << " Size of stack is : " << obj.size() << endl;// it returns the current size of stack
	obj.pop();// it popped or removed the top value of stack. in this case it removes 5 from stack
	if (obj.empty())// it returns true if the stack is empty 
		cout << " Stack is empty : " << endl;
	else
		cout << " Stack is not empty : " << endl;
	cout << " top value of stack is : " << obj.top() << endl;// it returns the new top value of the stack
	cout << " Remaining data in stack is : " << endl;
	while (!obj.empty())// this loop iterates untill stack becomes empty
	{
		cout << " " << obj.top() << endl;// it displays the new top value of stack
		obj.pop();//  it removes the top value from the stack
	}
	if (obj.empty())// it returns true if the stack is empty 
		cout << " Stack is empty : " << endl;
	else
		cout << " Stack is not empty : " << endl;
	system("pause");
	return 0;
}

Output image of stack STL code.

Output image of C++ stack STL example code.

C++ code explanation of stack STL.

  • In first step we include stack library #include<stack>.
  • Create stack object in main.
  • Call stack::push() function five times and push data (1,2,3,4,5) in stock.
  • Get the top value of stack using stack::top() function.
  • Get size of stack using stack::size() function.
  • Deletes the topmost element of stack using stack::pop() function.
  • Check if the stack is empty or not using the stack::empty() function and display the desired message.
  • Remove and display all the data in the stack using a while loop.
  • The while loop works in a way that it first checks that the stack is full or not.
  • If the stack is not full, it first displays the top value using the stack::top() function, and then it removes that top value using the stack::pop() function.
  • The number of iterations continued until the stack becomes empty.
  • Again, check if the stack is empty or not using the stack::empty() function and display the desired message.

How to print stack?

There is no built-in function to print a stack. We have to make a user-defined function to print a stack. The best approach to print a stack is to create a recursive function of void type. Let’s take a look at this code to print a stack.

C++ code of printing a stack using recursive function.

//C++ code of printing a stack using recursive function.
#include<iostream>
#include<stack>// stack library or stack standard template library STL
using namespace std;
template <typename type>
void printStack(stack<type> obj);// print function prototype
int main()
{
	stack<int> obj;// create stack object
	obj.push(1);// push 1 in stack
	obj.push(2);// push 2 in stack
	obj.push(3);// push 3 in stack
	obj.push(4);// push 4 in stack
	obj.push(5);// push 5 in stack
	cout << " data is: " << endl;// display message 
	printStack(obj);// function call to print all the data of stack 
	cout << endl;
	
	return 0;
}
template <typename type>
void printStack(stack<type> obj)// function definition
{
	if (obj.empty())// base condition if stack is empty it will stop the recursion process
		return;

	type temp = obj.top();// assign the value of the top position of stack to temp variable

	obj.pop();// remove data from top location of stack

	cout << " " << temp;// print value 

	printStack(obj);// function call recursively

	obj.push(temp);// again push data in stack to maintain its position
}

The output of printing stack using the recursive function:

data is:
 5 4 3 2 1

C++ code explanation of printing a stack using recursive function.

  • First include the iostream header file #include<iostream> to use its functions.
  • Include the stack header #include<stack> file in our code to use its functions. 
  • Include the std namespace (using namespace std) to use its classes. If we do not include it in our code, we need to write (std::) every time before using its classes.
  • Create the template function have stack object as a parameter.
  • Call the main function (main ()). And write the Whole program logic in it.
  • Create a stack obj to store integer values.
  • Use push functions five times and insert values 1,2,3,4,5 respectively.
  • Print a message on console “data is:” using the “cout” operator.
  • Call “printStack” function and pass obj as a parameter.
  • In the “printStack” function, first add a base condition that returns from the function if the stack is empty.
  • Make a temp variable of template type and assign the top value of the stack to it.
  • Now, call the pop function and remove the top value from the stack.
  • Display the value of the temp.
  • Now recursively call the function again and again until the stack becomes empty.
  • Points 10 to 14 will repeat in every recursion.
  • The recursive functions work with the stack. We will talk about the working of recursion later on.
  • The return value of functions in recursion is stored in stack and is retrieved respectively.
  • After the last iteration of the recursive process, the value of temp from the stack used by recursion is popped and again pushed to the original stack.

Representation of stack in C++:

The stack can be represented in computer in two ways.

Stack using arrays:

We can represent a stack by using arrays. The length of an array represents the number of data elements that we can push on the stack.

The user can not push an unlimited number of elements in the stack. It is simple to implement the representation of a stack with the array. It also provides less flexibility.

Stack using linked list.

We can also represent a stack by allocating memory dynamically using a linked list. In a stack using a linked list, the length of the stack is not specific. According to the exact requirements of the user, we can maintain the stack during execution.

In a stack using a linked list, the user can push an unlimited number of items. Dynamic representation of stack with pointers is also challenging and complex to implement. But it also provides more flexibility.

If you find anything incorrect or want to share more information about the topic discussed above, please write a comment.

Frequently Asked Questions.

What is Stack in C++?

A stack in C++ is a type of data structure based on the last-in, first-out (LIFO) technique. Last in first out is a technique of storing data in data structure and retrieving data from the data structure.

It holds all the newly entered objects on top of all previously entered objects. In stack, the push operation does this job. The newly entered data is removed first from the stack. In stack, the pop operation does this job.

How to declare a stack in C++?

We can declare stack in C++ using stack header file #include<stack>. Or we can also create our own stack class.

How do you input in stack?

To input any element in the stack we use the stack::push(Val) function. We write the value in parameters that we want to push.

How many functions are in stack standard template library?

There are about seven different functions and one “equal to” operator in the stack’s standard library.

These functions are.

  1. stack::push()
  2. stack::pop()
  3. stack::top()
  4. stack::empty()
  5. stack::size()
  6. stack::emplace()
  7. stack::swap()
  8. stack::operator=()

In how many ways we can represent stack?

We can represent a stack in two different ways.

  1. Stack using arrays.
  2. Stack using linked list.

Explain the representation of stack using arrays.

We can represent a stack by using arrays. The length of an array represents the number of data elements that we can push on the stack.

The user can not push an unlimited number of elements in the stack. It is simple to implement the representation of a stack with the array. It also provides less flexibility.

Explain the representation of stack using linked list.

We can also represent a stack by allocating memory dynamically using a linked list. In a stack using a linked list, the length of the stack is not specific. According to the exact requirements of the user, we can maintain the stack during execution.

In a stack using a linked list, the user can push an unlimited number of items. Dynamic representation of stack with pointers is also challenging and complex to implement. But it also provides more flexibility.

If you find it helpful then don't forget to Share it :

0 Comments

Submit a Comment

Your email address will not be published. Required fields are marked *

Latest Posts

More From The Blog