Implementing Stack in C++ using Class Template

#include<iostream>
using namespace std;

template<class T>
class stack{
T* arr;
static int top;
public:
stack(int);
void push(T);
T pop();
bool empty();
};

template<class T>
int stack<T>::top = -1;

template<class T>
stack<T>::stack(int x){
this->arr = new T(x);
}

template<class T>
void stack<T>::push(T a){
this->arr[++top] = a;
}

template<class T>
T stack<T>::pop(){
T a = this->arr[top--];
return a;
}

template<class T>
bool stack<T>::empty(){
return (top==-1);
}

int main(){
stack<int> s(10);
int i;
for(i=0;i<10;i++){
s.push(i);
}
while(!s.empty()){
cout<<s.pop()<<endl;
}
return 0;
}

Inorder Traversal without using recursion

void inorder(Node* root){
if(root == NULL) return;
Node *temp = root;
push(temp);
while(!isempty()){
temp = temp->left;
while(temp != NULL){
push(temp);
temp = temp->left;
}
temp = pop();
printf("%d ",temp->data);
if(temp->right != NULL){
temp = temp->right;
push(temp);
}
}
}

Preorder traversal of a BST, iteratively using a Stack

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

#define MAX 100

typedef struct node{
 int data;
 struct node* left;
 struct node* right;
}Node;

Node* s[MAX];
int top = -1;

Node* newNode(int data){
 Node* n = (Node *)malloc(sizeof(Node));
 n->data = data;
 n->left = NULL;
 n->right = NULL;
 return n;
}

void insertNode(Node* root,int data){
 if(data < root->data){
  if(root->left == NULL){
   root->left = newNode(data);
  } else {
   insertNode(root->left,data);
  }
 } else {
  if(root->right == NULL){
   root->right = newNode(data);
  } else {
   insertNode(root->right,data);
  }
 }
}

Node* createBST(Node **rootRef){
 Node *root = newNode(4);
 insertNode(root,2);
 insertNode(root,1);
 insertNode(root,3);
 insertNode(root,6);
 insertNode(root,5);
 insertNode(root,7);
 *rootRef = root;
}

void push(Node* n){
s[++top] = n;
}

Node* pop(){
return s[top--];
}

int isempty(){
return (top==-1);
}

void preorder(Node* root){
if(root == NULL){
return;
}
push(root);
while(!isempty()){
Node *temp = pop();
printf("%d ",temp->data);
if(temp->right != NULL){
push(temp->right);
}
if(temp->left != NULL){
push(temp->left);
}
}
}

int main(){
 Node* root = NULL;
 createBST(&root);

 printf("\nPREORDER :\n");
 preorder(root);

 return 0;
}

Push elements into stack. Pop should return the minimum element in the stack.

#include<iostream>

using namespace std;

class stack{
private:
int top;
int a[100];
public:
stack();
void push(int elem);
int pop();
void pushbubble(int elem);
bool isempty();
};

stack::stack(){
this->top = -1;
}

void stack::push(int elem){
a[++(this->top)] = elem;
}

void stack::pushbubble(int elem){
int temp;
if(!this->isempty()){
temp = this->pop();
if(temp > elem){
this->push(temp);
this->push(elem);
} else {
this->pushbubble(elem);
this->push(temp);
}
} else {
this->push(elem);
}
}

bool stack::isempty(){
return (this->top == -1);
}

int stack::pop(){
return a[(this->top)--];
}

int main(){
int a[] = {1,10,2,9,3,8,4,7,5,6};
stack s;
int i;
for(i=0;i<10;i++){
s.pushbubble(a[i]);
}
while(!s.isempty()){
cout<<s.pop()<<endl;
}
return 0;
}

Reverse a stack in place (without extra memory)

// You are given access to functions push, pop and isempty

void reverse(stack s){
        if(!isempty(s)){
                int temp = pop(s);
                reverse(s);
                pushtobottom(s,temp);
        }
}
 
pushtobottom(stack s, int data){
        if(!isempty(s)){
                temp = pop(s);
                pushtobottom(s,data);
                push(s,temp);
        } else {
                push(s,data);
        }
}