C++ stack

📚 C++ stack (LIFO Data Structure)

std::stack is a container adapter in the C++ STL that follows the LIFO (Last In, First Out) principle.
You can insert and remove elements only from the top.

🔹 1. Why Use Stack?

  • Function call management

  • Undo / Redo operations

  • Expression evaluation

  • Parenthesis checking

  • Backtracking (DFS)

🔹 2. Include Header

#include <stack>

🔹 3. Declaring a Stack

std::stack<int> s;

With underlying container:

std::stack<int, std::vector<int>> s;
std::stack<int, std::deque<int>> s; // default

🔹 4. Basic Stack Operations

s.push(10); // insert
s.push(20);

cout << s.top(); // 20

s.pop(); // removes top

🔹 5. Check Size and Empty

s.size();
s.empty();

🔹 6. Traversing a Stack

❌ No iterators provided

✔ Use copy to traverse:

stack<int> temp = s;

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

🔹 7. Stack Example: Reverse a String

#include <stack>
#include <string>

string str = "HELLO";
stack<char> s;

for (char c : str)
s.push(c);

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

Output:

OLLEH

🔹 8. Stack Example: Parenthesis Checking

bool isBalanced(string expr) {
stack<char> s;

for (char c : expr) {
if (c == '(')
s.push(c);
else if (c == ')') {
if (s.empty()) return false;
s.pop();
}
}
return s.empty();
}

🔹 9. Stack Using Array (Manual)

int stack[5];
int top = -1;

stack[++top] = 10; // push
top--; // pop

(STL stack preferred)

🔹 10. Stack Time Complexity

OperationComplexity
pushO(1)
popO(1)
topO(1)

🔹 11. Stack vs Vector vs List

Featurestackvectorlist
AccessTop onlyRandomSequential
Iterators❌✔✔
Use caseLIFOGeneralInsert/delete

❌ Common Mistakes

s.pop();
cout << s.top(); // ❌ undefined behavior

✔ Always check:

if (!s.empty())

📌 Summary

  • Stack follows LIFO

  • push(), pop(), top()

  • No iterators

  • Built on top of deque/vector/list

  • Used in recursion, parsing, undo systems

You may also like...