Reversing a String using Stack

#include <bits/stdc++.h>
using namespace std;
// Stack implementation => LIFO which stands for Last-in-first-out
// Reverse a string using stack
const int MAX_SIZE = 10000;

class Stack {
private:
    string array[MAX_SIZE];
    int top;

public:
    Stack() {
        top = 0;
    }

    //Pushing (storing) an element on the stack.
    void push(int x) {
        array[top] = x;
        top++;
    }
    // Removing (accessing) an element from the stack.
    string pop() {
        top--;
        return array[top];
    }

    // get the top data element of the stack, without removing it.
    string peek() {
        return array[top];
    }

    // check if stack is empty.
    bool isEmpty() {
        if (top == 0)
            return true;
        else return false;
    }
};
//reverse a string using stack
int main() {
    Stack s;
    char str[]="Stack";
    int len = strlen(str),i;
    for(i=0;i<len;i++)
        s.push(str[i]);

    for(i=0;i<len;i++)
        cout << s.pop();
    return 0;
}

Breadth First Search (BFS)

// Program to print BFS traversal from a given source vertex. BFS(int s) 
// traverses vertices reachable from s.
#include<iostream>
#include <list>
 
using namespace std;
 
// This class represents a directed graph using adjacency list representation
class Graph
{
    int V;    // No. of vertices
    list<int> *adj;    // Pointer to an array containing adjacency lists
public:
    Graph(int V);  // Constructor
    void addEdge(int v, int w); // function to add an edge to graph
    void BFS(int s);  // prints BFS traversal from a given source s
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}
 
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}
 
void Graph::BFS(int s)
{
    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    for(int i = 0; i < V; i++)
        visited[i] = false;
 
    // Create a queue for BFS
    list<int> queue;
 
    // Mark the current node as visited and enqueue it
    visited[s] = true;
    queue.push_back(s);
 
    // 'i' will be used to get all adjacent vertices of a vertex
    list<int>::iterator i;
 
    while(!queue.empty())
    {
        // Dequeue a vertex from queue and print it
        s = queue.front();
        cout << s << " ";
        queue.pop_front();
 
        // Get all adjacent vertices of the dequeued vertex s
        // If a adjacent has not been visited, then mark it visited
        // and enqueue it
        for(i = adj[s].begin(); i != adj[s].end(); ++i)
        {
            if(!visited[*i])
            {
                visited[*i] = true;
                queue.push_back(*i);
            }
        }
    }
}
 
// Driver program to test methods of graph class
int main()
{
    // Create a graph given in the above diagram
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);
 
    cout << "Following is Breadth First Traversal "
         << "(starting from vertex 2) \n";
    g.BFS(2);
 
    return 0;
}

Linked List

#include <bits/stdc++.h>
using namespace std;

class Node {
private:
    int data;
    Node* next;

public:
    Node() {
        data = 0;
        next = NULL;
    }

    Node(int d) {
        data = d;
        next = NULL;
    }

    Node(int d, Node* n) {
        data = d;
        next = n;
    }

    void setData(int x) {
        data = x;
    }

    int getData() {
        return data;
    }

    void setNext(Node* x) {
        next = x;
    }

    Node* getNext() {
        return next;
    }
};

class LinkedList {
private:
    Node* head;

public:
    LinkedList() {
        head = NULL;
    }

    void insertAtFront(int data) {
        Node* n = new Node(data, head);
        head = n;
    }

    void insertAtBack(int data) {
        Node* n = new Node(data);
        if (head == NULL) {
            head = n;
        } else {
            Node* i;
            for (i = head; i->getNext() != NULL; i=i->getNext())
                ;
            i->setNext(n);
        }
    }

    void insertAfter(int key, int data) {
        // inserts a new node containing data
        // after the node containing key
        // assuming that a node containing key exists

        Node* n = new Node(data);
        Node* i;
        for (i = head; i->getData() != key; i=i->getNext())
            ;
        n->setNext(i->getNext());
        i->setNext(n);
    }

    int removeFromFront() {
        Node* n = head;
        int x = n->getData();
        head = head->getNext();
        delete n;
        return x;
    }

    int removeFromBack() {
        Node* n;
        Node* i;
        int x;
        for (i = head; i->getNext()->getNext() != NULL; i = i->getNext())
            ;
        n = i->getNext();
        x = n->getData();
        delete n;
        i->setNext(NULL);
        return x;
    }

    void print() {
        for (Node* i = head; i != NULL; i = i->getNext())
            cout << i->getData() << endl;
    }

    int size() {
        int total = 0;
        for (Node* i = head; i != NULL; i = i->getNext())
            total++;
        return total;
    }

    bool isEmpty() {
        if (head == NULL)
            return true;
        else return false;
    }

    bool isPresent(int x) {
        for (Node* i = head; i != NULL; i = i->getNext())
            if (i->getData() == x)
                return true;
        return false;
    }
};

int main() {
    LinkedList list;
    list.insertAtFront(50);
    list.insertAtFront(4);
    list.insertAtFront(14);
    list.insertAtFront(40);
    list.insertAtBack(1);
    list.insertAtBack(2);
    list.insertAfter(40, 5);

    if (list.isPresent(5))
        cout << "5 is present" << endl;
    else cout << "5 is not present" << endl;

    list.print();
    cout << "Total number of elements " << list.size() << endl;

    while (!list.isEmpty())
    {
        cout << "Removing from front " << list.removeFromFront() << endl;
        if(!list.isEmpty())
         cout << "Removing from back " << list.removeFromBack() << endl;
    }

    list.print();
    cout << "Total number of elements " << list.size() << endl;

    return 0;
}

Built in Stack

#include <iostream>
#include <stack>

using namespace std;

int main ()
{
    stack <string> tcr; /* Simple enough to create a stack */
    tcr.push("HT"); /* push() will add a value, think of queues */
    tcr.push("RBH");  /* adding some tcr to the deck */
    tcr.push("KMH");
    tcr.push("SM");
    cout << "There are " << tcr.size ();

    cout << " tcr in SEU, CSE" << endl;
    cout << "The tcr on the top of the is " ;

    cout << tcr.top() << endl;
    tcr.pop();
    cout << "The top tcr is now " << tcr.top() << endl;
    cout << tcr.size();


}

Queue

/*
Tanzila Islam
CSE, Southeast University.
Dhaka-Bangladesh.
id : https://www.facebook.com/prieontypurnotamohita
mail: tanzilamohita@gmail.com
blog: http://tanzilamohita.blogspot.com/

*/


/* Circular array implementation of a Queue */

#include <iostream>

using namespace std;


const int MAX_SIZE = 10000;


class Queue {

private:

    int array[MAX_SIZE];

    int head, tail, count;


public:

    Queue() {

        head = 0;

        tail = 0;

        count = 0;

    }


    void push(int x) {

        array[tail] = x;

        tail++;

        if (tail >= MAX_SIZE)

            tail = 0;

        count++;

    }


    int pop() {

        int x = array[head];

        head++;

        if (head >= MAX_SIZE)

            head = 0;

        count--;

        return x;

    }


    int peek() {

        return array[head];

    }


    bool isEmpty() {

        if (count == 0)

            return true;

        else return false;

    }

};


int main() {

    Queue q;

    q.push(10);

    q.push(13);

    q.push(15);

    while (!q.isEmpty())

        cout << q.pop() << endl;

    return 0;

}

Stack

/*
Tanzila Islam
CSE, Southeast University.
Dhaka-Bangladesh.
id : https://www.facebook.com/prieontypurnotamohita
mail: tanzilamohita@gmail.com
blog: http://tanzilamohita.blogspot.com/

*/


#include <iostream>

using namespace std;


const int MAX_SIZE = 10000;


class Stack {

private:

    int array[MAX_SIZE];

    int top;


public:

    Stack() {

        top = 0;

    }


    void push(int x) {

        array[top] = x;

        top++;

    }


    int pop() {

        top--;

        return array[top];

    }


    int peek() {

        return array[top - 1];

    }


    bool isEmpty() {

        if (top == 0)

            return true;

        else return false;

    }

};


int main() {

    Stack s;

    s.push(10);

    s.push(13);

    s.push(15);


    while (!s.isEmpty())

        cout << s.pop() << endl;

    return 0;

}

Binary Max Heap

/*
Tanzila Islam
CSE, Southeast University.
Dhaka-Bangladesh.
id : https://www.facebook.com/prieontypurnotamohita
mail: tanzilamohita@gmail.com
blog: http://tanzilamohita.blogspot.com/

*/




#include <iostream>

using namespace std;


class BinaryMaxHeap {

private:

    int *A;

    int length;

    int heapSize;


public:

    BinaryMaxHeap(int X[], int l) {

        A = X;

        length = l;

    }


    int left(int i) {

        return 2 * i;

    }


    int right(int i) {

        return 2 * i + 1;

    }


    int parent(int i) {

        return i / 2;

    }


    void maxHeapify(int i) {

        int l = left(i);

        int r = right(i);

        int largest;

        if (l <= heapSize && A[l] > A[i])

            largest = l;

        else largest = i;

        if (r <= heapSize && A[r] > A[largest])

            largest = r;

        if (largest != i) {

            int t = A[i];

            A[i] = A[largest];

            A[largest] = t;

            maxHeapify(largest);

        }

    }


    void buildMaxHeap() {

        heapSize = length;

        for (int i = length / 2; i >= 1; i--)

            maxHeapify(i);

    }


    void heapSort() {

        buildMaxHeap();

        for (int i = length; i >= 2; i--) {

            int t = A[i];

            A[i] = A[1];

            A[1] = t;

            heapSize = heapSize - 1;

            maxHeapify(1);

        }

    }

};


int main() {

    int X[] = {-1, 5, 12, 54, 32, 13, 67, 90, 23, 12, 36, 45, 23, 15, 56};

    int n = sizeof(X) / sizeof(X[0]) - 1;

    cout << "Before calling heapSort" << endl;

    for (int i = 1; i <= n; i++)

        cout << X[i] << " ";

    cout << endl;

    BinaryMaxHeap h(X, n);

    h.heapSort();

    cout << "After calling heapSort" << endl;

    for (int i = 1; i <= n; i++)

        cout << X[i] << " ";

    cout << endl;

    return 0;

}

Stack implementation using linked list

#include <cstdlib>

#include<iostream>

using namespace std;

class node

{

public:

int data;

node* next;

};

class StackusingList

{

public:

StackusingList(int max)

{

top = NULL;

maxnum = max;

count=0;

}

void push(int element)

{

if(count == maxnum)

cout<<"stack is full";

else

{

node *newTop = new node;

if(top == NULL)

{

newTop->data = element;

newTop->next = NULL;

top = newTop;

count++;

}

else

{

newTop->data = element;

newTop->next = top;

top = newTop;

count++;

}

}

}

void pop()

{

if(top == NULL)

cout<< "nothing to pop";

else

{

node * old = top;

top = top->next;

count--;

delete(old);

}

}

void print()

{

node *temp;

temp = top;

while(temp!=NULL)

{

cout<<temp->data<<",";

temp=temp->next;

}

}

private:

node *top;

int count; //head

int maxnum;

int stackData;

};

int main(int argc, char** argv) {

StackusingList *sl = new StackusingList(5);

sl->push(1);

sl->push(2);

sl->push(3);

sl->push(4);

sl->push(5);

sl->push(6);

sl->pop();

cout<<"new stack\n";

sl->print();

return 0;

}

DFS Implementation

#include<iostream>

#include<conio.h>

#include<stdlib.h>

using namespace std;

int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10];

main()

{

int m;

cout <<"enterno of vertices";

cin >> n;

cout <<"ente no of edges";

cin >> m;

cout <<"\nEDGES \n";

for(k=1;k<=m;k++)

{

cin >>i>>j;

cost[i][j]=1;

}

cout <<"enter initial vertex";

cin >>v;

cout <<"ORDER OF VISITED VERTICES";

cout << v <<" ";

visited[v]=1;

k=1;

while(k<n)

{

for(j=n;j>=1;j--)

if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)

{

visit[j]=1;

stk[top]=j;

top++;

}

v=stk[--top];

cout<<v << " ";

k++;

visit[v]=0; visited[v]=1;

}

}

BFS Implementation

#include<iostream>

#include<conio.h>

#include<stdlib.h>

using namespace std;

int cost[10][10],i,j,k,n,qu[10],front,rare,v,visit[10],visited[10];

main()

{

int m;

cout <<"enterno of vertices";

cin >> n;

cout <<"ente no of edges";

cin >> m;

cout <<"\nEDGES \n";

for(k=1;k<=m;k++)

{

cin >>i>>j;

cost[i][j]=1;

}

cout <<"enter initial vertex";

cin >>v;

cout <<"Visitied vertices\n";

cout << v;

visited[v]=1;

k=1;

while(k<n)

{

for(j=1;j<=n;j++)

if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)

{

visit[j]=1;

qu[rare++]=j;

}

v=qu[front++];

cout<<v << " ";

k++;

visit[v]=0; visited[v]=1;

}

}