c-plus-plus
  1. c-plus-plus-stack
PreviousNext

C++ STL Stack

A Stack is an abstract data type that represents a collection of elements with two main operations: push and pop. In C++, Stack is a container that provides push and pop operations, and follows the Last-In-First-Out (LIFO) principle.

Syntax

#include <stack>

// declaring stack
stack<datatype> s;

// pushing an element onto the stack
s.push(element);

// popping the top element from the stack
s.pop();

// getting the top element of the stack
s.top();

// checking if the stack is empty
s.empty();

// getting the size of the stack
s.size();

Example

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

int main() {
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    cout << s.top() << endl;
    s.pop();
    cout << s.top() << endl;
    return 0;
}

Output

3
2

Explanation

In the above example, we have created a stack of integers and pushed three numbers onto the stack. We then retrieved the top element using the top() method and printed its value. We then popped the top element and printed the new top element.

Use

Stacks are useful in situations where elements need to be processed in a specific order, such as reversing a string or evaluating expressions. 

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

bool isBalanced(string str) {
    stack<char> s;
    for (int i = 0; i < str.length(); i++) {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
            s.push(str[i]);
        } else if (str[i] == ')' && !s.empty() && s.top() == '(') {
            s.pop();
        } else if (str[i] == ']' && !s.empty() && s.top() == '[') {
            s.pop();
        } else if (str[i] == '}' && !s.empty() && s.top() == '{') {
            s.pop();
        } else {
            return false;
        }
 }
    return s.empty();
}

int main() {
    string str1 = "()[]{}";
    string str2 = "([)]";
    cout << boolalpha << isBalanced(str1) << endl; // true
    cout << boolalpha << isBalanced(str2) << endl; // false
    return 0;
}

In the above example, we have implemented a function that checks if a string of brackets is balanced. We use a stack to keep track of the opening brackets and pop them when a closing bracket is encountered. If the stack is empty at the end of the loop, the string is balanced.

Important Points

  • Stack is an abstract data type that represents a collection of elements with two main operations: push and pop.
  • Stack in C++ follows the Last-In-First-Out (LIFO) principle.
  • Stack is a container that provides push and pop operations.
  • Stack can be implemented using an array or dynamically using a linked list.
  • Stack can be used for reversing a string, evaluating expressions, and implementing backtracking algorithms.

Summary

In summary, stack is an essential data structure in computer science. It follows the Last-In-First-Out (LIFO) principle and has many applications such as reversing a string and evaluating expressions. C++ provides the stack container that implements all the necessary functionalities for a stack.

SetQueue
Published on: