Stack in C++

Stack:

The stack is a very popular data structure. It is the form of data structure that follows a particular order called FIFO(First-In-First-Out). In simple words, a stack is an Abstract Data Type used to store a collection of objects.

Various operations are uniquely associated with stacks. They are namely push, pop, and peek.

Let's look out what is a push, pop and peek or top, and isEmpty.

Push: When an element is pushed inside a stack, it is called Push

      operation.

Pop: When an element is removed from the top of the stack, it is

     called as Pop operation.

Peek or Top: This return top element of the stack.

isEmpty: It return true if stack is empty, else return false.

Pre-Requisites:

Before understanding stacks, one must be familiar with the below fundamentals.

1. Conditional statements like if, else.
2. Pointers.
3. Loops like for, while and do while.
4. Arrays and string primarily.
5. One object oriented programming language like C++ or Java.

All the above operations have 0(1) complexity and no loop is used.

Let us look at basic syntax of stack operations that we involve while implementing it.

Push:

 void push(int information) {
    if(isNotFull()) {
       top = top + 1;  
       stack[top] = information;
    } else {
       printf("Stack is full.");
    }
 } 

Pop:

 int pop(int data) {
    if(isNotempty()) {
       information = stack[top];
       top = top - 1;  
       return information;
    } else {
       printf("Stack is empty.\n");
    }
 } 

Peek or Top:

 int peekOrTop()
 {
    return stack[top];
 } 

isEmpty:

 bool isEmpty()
 {
    if(top == -1)     //-1 denotes empty
       return true;
    else
       return false;
 } 

The above pseudo codes can be combined to show operations in the following code below.

 #include <bits/stdc++.h>
 using namespace std;
 #define max 1000
 class Stack {
     int top;
 public:
     int a[max];
     Stack() { top = -1; }
     bool push(int y);
     int pop();
     int peek();
     bool isEmpty();
 };
 bool Stack::push(int y)
 {
     if (top >= (max - 1)) {
         cout << "Stack Overflow";
         return false;
     }
     else {
         a[++top] = y;
         cout << y << " is pushed inside stack \n";
         return true;
     }
 }
 int Stack::pop()
 {
     if (top < 0) {
         cout << "Stack Underflow";
         return 0;
     }
     else {
         int x = a[top--];
         return x;
     }
 }
 int Stack::peek()
 {
     if (top < 0) {
         cout << "Stack is Empty";
         return 0;
     }
     else {
         int x = a[top];
         return x;
     }
 }
 bool Stack::isEmpty()
 {
     return (top < 0);
 }
 int main()
 {
     class Stack s;
     s.push(100);
     s.push(200);
     s.push(300);
     cout << s.pop() << "Popped out from stack\n";
     return 0;
 } 

Output:

Explanation:

In the above code, we have used an object-oriented programming method so that we can handle code complexity and make it more readable.

Let us take into consideration the below algorithms to understand the logic behind our code.

START

1. Top = 0
2. Exit

PUSH(STACK,TOP,MAX,ITEM)

1. Top = max then

    B. Print “Stack full”;

    C. Exit out of the stack.

    Otherwise

• Top: = Top + 1;        //increasing top
• Check Stack(Top)= ITEM;
• End IF
• Exit

POP_STACK(STACK,TOP,ITEM)

A. IF Top = zero

        Print “Empty Stack”;

        Exit;

• Otherwise

        ITEM: =Stack (Top);

        Top:=Top – 1;

•  End IF
•  Exit

END

These algorithms are usually followed in the above code to show how the push and pop operations are commonly carried out.

Applications of Stacks

The applications of stacks are listed below:

1. Memory management:

The continuous memory blocks help in memory assignment when it takes place. With stack, we do it functionally and the size of the memory to be allocated will be already known by the compiler. When a functional call is executed, memory is allocated and de-allocated when it is already used. These executions happen at defined intervals so that the users do not have to worry about memory management.

• Evaluating Expressions and Conversions:

Expressions in stacks primarily work on the operator precedence. Say (2*2)+4 will give us 8 since the * or the parenthesis has higher priority. So, they can also be used for parenthesis matching in an expression when a user has not defined the correct order.

• Backtracking Occurrences:

For complex algorithms like the 8 -Queens problem of Knights Tour problem, backtracking is specifically used to get to the last point where we found the value. Thus, a stack is very efficient in providing backtracking methods. It was used to get back from the current state we may need the previous state and then got into some other paths.

Insights:

In real-world applications, Stack plays a crucial role in particular. From the application perspective stacks are most applicable in the scientific calculations. The undo option in text editors use the stack to roll back to the previous elements.

In programming, it may be used to reverse a word, language processing, defining, and keeping records in a database, and also used to support recursion.