So far, we have read about Vectors, Arrays, and Strings. Now it is time to get familiar with a new data structure called as Stacks. So let's get started.

What is a Stack?

As the name sugggests, Stack is a data structure where data is stacked on top of each other. A visual representation would be helpful i guess..

In the above image, you can see a vertical container and some operations being done on it. We will talk about the operations in detail ahead. The vertical container is a stack. Stack is a very useful data structure.

• It is used to solve a lot of famous DSA Interview questions.
• Stacks are used to implement functions, parsers, expression evaluation, and backtracking algorithms.
• A stack is a Last In First Out (LIFO) structure, that is, last item you put in is first item you can take out.
• A pile of books, a stack of dinner plates, a box of pringles potato chips can all be thought of examples of stacks.

Syntax and In-Built Functions.

• There are two ways to create a stack. One is to build a stack manually with an array and 2 pointers and the other is by using an in-built stack (which most programming languages have). We will talk about the second way here. If you are interested in knowing how stacks are built internally, feel free to go and read this article.
• We will use the in-built stack data type to learn about stacks. Below is the syntax to create a stack.

  stack<int> st;  // stack <data_type> <name of the stack>
  

  Easy right. The stack has 3 major operations. Push, Pop, and Top/Peek
• Push: This operation is used to push a new element on the top of the stack.
• Pop: This operation is used to remove the top-most element of the stack.
• Top/Peek: In C++, it is Top and in Java it is Peek. This function is used to peek at the top-most element of the stack.

st.push(3); // stack is [3]
st.push(7); // stack is [3,7]
st.push(1); // stack is [3,7,1]
st.pop(); // stack is [3,7]
int curr = st.top(); // returns 7

Time Complexities

There are other in-built functions like empty() and size()which are useful while using a stack. The time complexities of all the functions of a stack are as follows.

• Push: O(1)
• Pop: O(1)
• Peek: O(1)
• Size: O(N)
• Empty: O(N)

Code Example.

Here is a complete code snippet of all the functions discussed above.

#include<bits/stdc++.h>

using namespace std;

int main()
{
   stack<int>st;
   st.push(3);
   st.push(7);
   st.push(1);
   st.pop();
   int y = st.top();
   bool x = st.empty();
   int sz = st.size();
}

Conclusion

This concludes our article on Stacks. Now you have a good understanding of the basics of a stack and its time complexities. You can now go on your IDE and play around with them.