Stack Implementation

                             

Stack is a linear data structure in which insertion and deletion is allowed at one end called top.

The order of stack may be LIFO(Last In First Out) or FILO(First In Last Out).

Stack Primary Operation 

1. push() - insert data onto stack.
2. pop() - delete the last inserted element in the stack.
3. top() - return the top element element of the stack.
4. isEmpty() - Return true if stack is empty. else false.
5. isFull() - Return true if stack is full, else false.
6. size() - Return the number of element in the stack.

There are different ways to implement the stack -

• Stack using  array
• Stack using linkedlist 
• Stack using queue

Stack Application

• Infix
• Example 1 : A+B-C
• Example 2 :A*B/C

• Postfix
• Example 1: A+
• Example 2: AB*C/

• Prefix
• Example 1: +A
• Example 2: +*AB/C

                                          

                                             Implement Stack using Array

Problem statement: Implement a stack using an array.

Note: Stack is a data structure that follows the Last In First Out (LIFO) rule.

Example:

Explanation:

• push(): Insert the element in the stack.
• pop(): Remove and return the topmost element of the stack.
• top(): Return the topmost element of the stack
• size(): Return the number of remaining elements in the stack.

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Intuition:  As we know stack works on the principle of last in first out, so we have to put elements in an array such that it keeps track of the most recently inserted element. Hence we can think of using a Top variable which will help in keeping track of recent elements inserted in the array.

Approach:

• Declare an array of particular size.
• Define a variable “Top” and initialize it as -1.
• push(x): insert element is the array by increasing top by one.
• pop(): check whether top is not equal to -1 if it is so, return top and decrease its value by one.
• size(): return top+1.

Code

#include<bits/stdc++.h>
using namespace std;
class Stack {
  int size;
  int * arr;
  int top;
  public:
    Stack() {
      top = -1;
      size = 1000;
      arr = new int[size];
    }
  void push(int x) {
    top++;
    arr[top] = x;
  }
  int pop() {
    int x = arr[top];
    top--;
    return x;
  }
  int Top() {
    return arr[top];
  }
  int Size() {
    return top + 1;
  }
};
int main() {

  Stack s;
  s.push(6);
  s.push(3);
  s.push(7);
  cout << "Top of stack is before deleting any element " << s.Top() << endl;
  cout << "Size of stack before deleting any element " << s.Size() << endl;
  cout << "The element deleted is " << s.pop() << endl;
  cout << "Size of stack after deleting an element " << s.Size() << endl;
  cout << "Top of stack after deleting an element " << s.Top() << endl;
  return 0;
} 

Output

Top of stack is before deleting any element 7
Size of stack before deleting any element 3
The element deleted is 7
Size of stack after deleting an element 2
Top of stack after deleting an element 3

Time Complexity: O(N)

Implement stack using linked list

Approach

Let's focus on each and every operation of the stack and see how we can implement it using a linked list.

We can assume our linked list to be a horizontal stack where the operations like deletion and insertion would take place at the top of the stack or at the head of the linked list.

To perform all the operations our head of the linked list would act as the top of the stack.

push(): pushing an element at the top of a stack

Pushing the element at the top of the stack would mean the same as pushing an element at the end of the linked list.

We can insert it at the beginning of the linked list using the following steps:

• Create a node for our new element.
• Point to the next pointer of our element node to point to the head of the linked list.
• Make the element node our top node.
• Increment the size variable.

For a more detailed explanation of insertion at the beginning of a linked list, refer to this article.

Let's see the function of this implementation

Code

void stackPush(int x) {
stackNode * element = new stackNode(x);
element -> next = top;
top = element;
cout << "Element pushed" << "\n";
size++;
}

pop(): removing an element from the top of a stack

Removing an element from the top of the stack is the same as removing the element from the beginning of our linked list.

The following steps are involved in the pop() method

• Check for underflow conditions in the stack.
• Store the top node in a temp node and top node data in another variable.
• Make the second node of our temp node a top.
• Delete temp node.
• Return the top node’s data.

The following function explains the approach

Code

int stackPop() {
if (top == NULL) {
return -1;
}
int topData = top -> data;
stackNode * temp = top;
top = top -> next;
delete temp;
size--;
return topData;
}

size(): returns the size of the stack

For this, we maintain a size variable. After each push operation, we increment the size variable and after each pop operation, we decrement the size variable.

Let’s see the code implementation for this function.

Code

int stackSize() {
return size;
}

isEmpty(): returns a boolean value for whether the stack is empty or not.

To do this, we check if our top is equal to NULL.

bool stackIsEmpty() {
return top == NULL;
}

The following code compiles every function to form a complete stack implementation using a linked list.

Final Code:

Code

#include<iostream>
using namespace std;

struct stackNode {
  int data;
  stackNode * next;
  int size;
  stackNode(int d) {
    data = d;
    next = NULL;
  }
};
struct stack {
  stackNode * top;
  int size;
  stack() {
    top = NULL;
    size = 0;
  }
  void stackPush(int x) {
    stackNode * element = new stackNode(x);
    element -> next = top;
    top = element;
    cout << "Element pushed" << "\n";
    size++;
  }
  int stackPop() {
    if (top == NULL) {
      return -1;
    }
    int topData = top -> data;
    stackNode * temp = top;
    top = top -> next;
    delete temp;
    size--;
    return topData;
  }
  int stackSize() {
    return size;
  }
  bool stackIsEmpty() {
    return top == NULL;
  }
  int stackPeek() {
    if (top == NULL) return -1;
    return top -> data;
  }
  void printStack() {
    stackNode * current = top;
    while (current != NULL) {
      cout << current -> data << " ";
      current = current -> next;
    }
  }
};
int main() {
  stack s;
  s.stackPush(10);
  cout << "Element popped: " << s.stackPop() << "\n";
  cout << "Stack size: " << s.stackSize() << "\n";
  cout <<"Stack empty or not? "<<s.stackIsEmpty()<<"\n";
  cout << "stack's top element: " << s.stackPeek() << "\n";
  return 0;
}

Output

Element pushed
Element popped: 10
Stack size: 0
Stack empty or not? 1
Stack's top element: -1

Standard Template Library (STL)

In C++, the Standard Template Library (STL) provides a stack container that allows you to manage collections of elements with operations to push, pop, and access the top element.

Key Features of STL Stack:

1. LIFO Structure: The last element added to the stack is the first one to be removed.
2. Dynamic Size: The size of the stack can grow or shrink as needed.
3. Member Functions: The STL stack provides several functions to manage the stack effectively.

Key Member Functions of STL Stack:

push(const T& val): Adds an element val to the top of the stack.

pop(): Removes the top element from the stack.

top(): Returns a reference to the top element of the stack without removing it.

empty(): Returns true if the stack is empty; otherwise, returns false.

size(): Returns the number of elements in the stack.

Example of Using Stack in STL

Here’s a simple example that demonstrates how to use the stack in C++ with the STL:

#include <iostream>

#include <stack>   // Include the stack header

using namespace std; 

int main() {

  stack<int> myStack;    // Create a stack of integers

    myStack.push(10);      // Push elements onto the stack

    myStack.push(20);     // Push elements onto the stack

    myStack.push(30);     // Push elements onto the stack

    cout << "Stack size after pushing elements: " << myStack.size() << std::endl;

   

 // Access the top element

    std::cout << "Top element: " << myStack.top() << std::endl; // Output: 30

     myStack.pop();    // Pop an element from the stack

    std::cout << "Stack size after popping one element: " << myStack.size() << std::endl;

    // Access the top element again

    std::cout << "Top element after pop: " << myStack.top() << std::endl; // Output: 20

    // Check if the stack is empty

    if (!myStack.empty()) {

        std::cout << "Stack is not empty." << std::endl;

    }

    // Pop remaining elements

    myStack.pop();

    myStack.pop();

    std::cout << "Stack size after popping all elements: " << myStack.size() << std::endl;

    if (myStack.empty()) {

        std::cout << "Stack is now empty." << std::endl; // Output: Stack is now empty.

    }

    return 0;

}

Explanation of the Example:

1. Including Headers: The #include <stack> directive includes the stack header from the STL.
2. Creating a Stack: We create a stack called myStack that stores integers.
3. Pushing Elements: We use push() to add elements (10, 20, and 30) to the stack.
4. Accessing Top Element: The top() function retrieves the element at the top of the stack without removing it.
5. Popping Elements: The pop() function removes the top element of the stack.
6. Checking Size: The size() function gives the current number of elements in the stack.
7. Checking Empty: The empty() function checks whether the stack has no elements.

Output of the Example:

Stack size after pushing elements: 3

Top element: 30

Stack size after popping one element: 2

Top element after pop: 20

Stack is not empty.

Stack size after popping all elements: 0

Stack is now empty.