Агуулга: Энэ бүлэгт ашигласан программын кодуудыг энд үзүүллээ. Стек нь өгөгдөл хийх ба авах гэсэн үндсэн хоёр үйлдэл бүхий шугаман бүтэц бөгөөд эдгээр үйлдлүүдийг стекийн орой гэх зөвхөн нэг төгсгөлд гүйцэтгэдэг. Иймээс стекийг “сүүлд орсон нь эхэлж гарах” (LIFO - last in, first out) жагсаалт ч гэж нэрлэх нь бий.

Стекийг массиваар

1. Стекийн классыг main() функцэд

// 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. Толгой файл: 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;
}

Стекийг жагсаалтаар

1. Стекийн классыг main() функцэд

// 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. Толгой файл: 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;
}

Стекийн хэрэглээ

1. Аравтаас хоёртын тоололд хөрвүүлэх

// 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. Хаалтуудын баланс шалгах

// 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;
}