Stacks in Cpp

Introduction to Stacks in Cpp

In this article, you will be learning about the STL stack with some useful examples which will help you understand the concept better.

Stacks are a type of container adaptors with LIFO (Last In First Out) type of work, where a new element is added at one end called the top and an element is removed from the same end only. Stack used an encapsulation 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.

Creating a Stack

The header that has all the functionality of the stack is <stack> header file. We must include it in our program to create and use the stack.

Syntax:

stack<type> stack_name;

Now that we know how to create a stack let’s look at some functions associated with a stack:

• 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 in the stack – Time Complexity: O(1)
• push(i) – Adds the element ‘i’ to the top of the stack – Time Complexity: O(1)
• pop() – Deletes the topmost element of the stack – Time Complexity: O(1)

Let’s look at some example programs using the above functions:

Adding Elements to the stack

We use the push() method to add an element to the stack.

For example,

#include <iostream>
#include <stack>

using namespace std;

int main() {

  // create a stack of strings
  stack<string> colors;

  // push elements into the stack
  colors.push("Red");
  colors.push("Orange");

  
  cout << "Stack: ";

  // print elements of stack
   while(!colors.empty()) {
    cout << colors.top() << ", ";
    colors.pop();
  }
 
  return 0;
}

Output

Stack: Orange, Red, 

So, in the above example, we have created a stack of strings called colors. Then, we used the stack method push() to add elements to the stack.

colors.push("Red");
colors.push("Orange");

To print the stack elements we used a while loop along with some stack methods top(), pop(), and empty() which are used to get the top element, remove the top element, and check if the stack is empty.

We will see more examples about pop(), top() and empty().

We should also notice that we have inserted the elements in the order {“Red”,” Orange”}. But while printing we get {“Orange”,” Red”} this shows that the stack is a LIFO data structure, which means that the elements inserted last are retrieved first.

NOTE: We cannot use a ranged for loop to iterator through a stack. As a stack is a container adapter, which provides restrictive access to make it behave like a standard stack data structure.

Removing Elements from the stack

We can remove an element from the stack using the pop() method. For example

#include <iostream>
#include <stack>
using namespace std;

// function prototype for display_stack utility
void display_stack(stack<string> st);

int main() {

  // create a stack of strings
  stack<string> colors;

  // push elements into the stack
  colors.push("Red");
  colors.push("Orange");
  colors.push("Blue");
  
  cout << "Initial Stack: ";
  // print elements of stack
  display_stack(colors);
  
  // removes "Blue" as it was inserted last
  colors.pop();

  
  cout << "Final Stack: ";

  // print elements of stack
  display_stack(colors);
  
  return 0;
}

// utility function to display stack elements
void display_stack(stack<string> st) {

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

  cout << endl;
}

Output

Initial Stack: Blue, Orange, Red, 
Final Stack: Orange, Red,

In the above program, we have created a function to print the stack elements and used the pop() method to remove an element from the stack.

// removes top element
colors.pop() 

This removes the element at which the top is pointing.

Conclusion:

That’s it for this article. In the next article, we will be looking at more stack operations and accessing the elements in the stack.

We will also be looking at some of the in-built functions that can be used with a stack.

Thank You!