The following source codes are used in this chapter. A stack is a data structure that comprises two basic operations: insert (push) a new item, and remove (pop) the item that was most recently inserted. Also it is known as last-in, first-out (LIFO) discipline.

Stack using array

1. Main function using Stack class

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 7: Stacks

// Stack
// using array

#include "stack_array.h"

int main() {
  Stack<char> st(5);
  const char *s="stacks";
  char ch;
  int i = 0;
  
  while (*(s+i) && st.push(*(s+i))) 
    cout << "push <-- " << *(s+i++) << endl;
  while(st.pop(ch)) 
    cout << "pop --> " << ch << endl;
}

2. Header file: stack_array.h

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 7: Stacks

// Stack class using array
// Filename: stack_array.h

#include <iostream>
using namespace std;

template <class Type>
class Stack {
  int top, MaxSize;
  Type *stack;
public:
  Stack(int Msize) : MaxSize(Msize)
    { stack = new Type[MaxSize]; top = -1; }
  ~Stack()
    { delete [] stack; }
  bool push(const Type item);
  bool pop(Type& item);
  bool empty();
  bool full();
};

template<class Type> bool Stack<Type>::push(const Type item) {
  if(full()) {
    cout << "Stack is full" << endl;
    return false;
  }
  else {
    stack[++top] = item;
    return true;
  }
}

template<class Type> bool Stack<Type>::pop(Type &item) {
  if(empty()) {
    cout << "Stack is empty" << endl;
    return false;
  }
  else {
    item = stack[top--];
    return true;
  }
}

template<class Type> bool Stack<Type>::empty() {
  return top < 0 ? true : false;
}

template<class Type> bool Stack<Type>::full() {
  return top >= MaxSize-1 ? true : false;
}

Stack using linked list

1. Main function using Stack class

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 7: Stacks

// Stack
// using linked list

#include "stack_list.h"

int main() {
  Stack<char> st;
  char ch;
  for(ch = 65; ch<75; ch++){
    st.push(ch);
    cout << "push <-- " << ch << endl;
  }
  while(st.pop(ch))
  cout << "pop --> " << ch << endl;
}

2. Header file: stack_list.h

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 7: Stacks
// Chapter 9: Trees
// Chapter 11: Advanced sorting algorithms

// Stack class using linked list
// Filename: stack_list.h

#include <iostream>
using namespace std;

template<class Type>
class Stack {
   struct Node{
      Type data; Node *link;
   };
   Node *top;
public:
   Stack()   { top=NULL; }
   ~Stack();
   bool push(const Type item);
   bool pop(Type& item);
   bool empty();
};

template<class Type> Stack<Type>::~Stack() {
  Node *temp;
  while (top) {
    temp = top; top = top->link;
    delete temp;
  }
}

template<class Type> bool Stack<Type>::push(const Type item) {
  Node *new_node;
  new_node = new Node;
  if(new_node) {
    new_node->data = item;
    new_node->link = top;
    top = new_node;
    return true;
  }
  else return false;
}

template<class Type> bool Stack<Type>::pop(Type& item) {
  if(empty()) {
    cout << "Stack is empty" << endl;
    return false;
  }
  else {
    Node *temp = top;
    item = top->data;
    top = top->link;
    delete temp;
    return true;
  }
}

template<class Type> bool Stack<Type>::empty() {
  if(!top) return true;
  else return false;
}

Stack Usage

1. Decimal to Binary Conversion

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 7: Stacks

// Decimal to Binary Conversion
// using Stack

#include "stack_list.h"

int main() {
  Stack<int> binary;
  int n;
  char ch;
  do {
    cout << "n = "; cin >>n;

    while(n) {
      binary.push(n%2);
      n /= 2;
    }

    cout << "Binary: ";
    while(!binary.empty()) {
      binary.pop(n); 
      cout << n;
    }

    cout << "\nMore (Y or N) ? :";
    cin >> ch;
    
  } while(ch=='Y' || ch == 'y');
}

2. Check the Balanced Parentheses

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 7: Stacks

// Check if given Parentheses expression is balanced or not 
// using Stack

#include <cstring>
#include "stack_array.h"
#define STLEN 80

char match(char cp) {
  char op;
  switch (cp) {
  case ')' : op = '('; break;
  case '}' : op = '{'; break;
  case ']' : op = '['; break;
  }
  return op;
}

int main() {
  Stack<char> st(100);
  char s[STLEN], ch;
  int i = 0;

  cout << "Enter the expression with parentheses: ";
  fgets(s, STLEN, stdin);
  while (s[i]) {
    if(strchr("{[(",s[i])) st.push(s[i]);
    if(strchr("}])",s[i])) {
      if((!st.pop(ch)) || (ch != match(s[i]))) {
        cout << "Unbalanced" << endl;
        exit(1);
      }
    }
    i++;
  }
  if(st.empty()) 
    cout << "Parenthesis are balanced" << endl;
  else
    cout << "Unbalanced" << endl;
}