Стек

Стеком называется упорядоченный набор элементов, в котором размещение новых и удаление существующих происходит с одного конца, называемого вершиной.

Дисциплина обслуживания — это совокупность правил (упорядочение и алгоритм) обслуживания элементов динамической структуры данных.

В зависимости от дисциплины обслуживания различают те или иные структуры динамических данных.

Принцип работы стека сравнивают со стопкой листов бумаги: чтобы взять второй сверху, нужно снять верхний.

В стеке реализуется дисциплина обслуживания LIFO:

  • LAST - последний
  • INPUT - вошел
  • FIRST - первый
  • OUTPUT - вышел

Различают аппаратный и программный стек.

Аппаратный стек используется для хранения адресов возврата из функций и их аргументов.
Программный стек – это пользовательская модель (структура) данных.

Операции для работы со стеком

Над стеком реализованы следующие операции:

  • инициализация стека init(s), где s — стек
  • помещение элемента в стек push (s, i), где s — стек, i — помещаемый элемент;
  • удаление элемента из стека i=pop(s);
  • определение верхнего элемента без его удаления i=stkTop(s), которая эквивалентна операциям i=pop (s); push (s, i);
  • получение вершины стека (количества элементов) i=gettop(s), где s — стек
  • печать стека stkPrint(s), где s — стек
  • определение пустоты стека isempty(s)
    возвращает true если стек пустой и false в противном случае.
Способы реализации стека

Существует несколько способов реализации стека:

  • с помощью одномерного массива;
  • с помощью связанного списка;
  •  с помощью класса объектно-ориентированного программирования.

Пример реализации стека

Стек можно реализовать в виде следующей структуры:

#define NMAX 100
struct stack {
  float elem[NMAX];
  int top;
};

NMAX — максимальное количество элементов в стеке;
elem — массив из NMAX чисел типа float, предназначенный для хранения элементов стека;
top — индекс элемента, находящегося в вершине стека.

Инициализация стека

Индекс элемента, находящегося в вершине стека, равен 0.

void init(struct stack *stk) {
  stk->top = 0;
}
Помещение элемента в стек
void push(struct stack *stk, float f) {
  if(stk->top < NMAX) {
    stk->elem[stk->top] = f;
    stk->top++;
  } else
    printf("Стек полон, количество элементов: %d !\n", stk->top);
}
Удаление элемента из стека
float pop(struct stack *stk) {
  float elem;
  if((stk->top) > 0) {
    stk->top--;
    elem = stk->elem[stk->top];
    return(elem);
  } else {
    printf("Стек пуст!\n");
    return(0);
  }
}
Извлечение вершины стека
float sktTop(struct stack *stk) {
  if((stk->top) > 0) {
    return( stk->elem[stk->top-1]);
  } else {
    printf("Стек пуст!\n");
    return(0);
  }
}
Получение верхнего элемента стека без его удаления
int gettop(struct stack *stk) {
 return(stk->top);}
Определение пустоты стека
int isempty(struct stack *stk) {
  if((stk->top) == 0)    return(1);
  else return(0);
}
Вывод элементов стека
void stkPrint(struct stack *stk) {
  int i;
  i=stk->top;
  if(isempty(stk)==1) return;
  do {
    i--;
    printf("%f\n", stk->elem[i]);
  }while(i>0);
}

Пример

int main() {
  struct stack *stk;
  int i,n;
  float elem;
  stk = (struct stack*)malloc(sizeof(struct stack));
  init(stk);
  printf("Введите количество элементов в стеке: ");
  scanf("%d", &n);
  for(i=0;i<n;i++) {
    printf("Введите элемент %d:", i);
    scanf("%f", &elem);
    push(stk,elem);
  }
  printf("В стеке %d элементов\n", gettop(stk));
  printf("\n");
  stkPrint(stk);
  printf("Верхний элемент %f\n",stkTop(stk));
  do {
    printf("Извлекаем элемент %f, ", pop(stk));
    printf("в стеке осталось %d элементов\n", gettop(stk));
  } while(isempty(stk)==0);
  getchar(); getchar();
  return 0;
}

Результат выполнения
Результат выполнения: стек

Пример Перевести введенное число в систему счисления с заданным основанием.
Перевод числа в другую систему счисления с использованием стека

int main() {
  struct stack *stk;
  int n, value;
  stk = (struct stack*)malloc(sizeof(struct stack));
  init(stk);
  printf("Введите число: ");
  scanf("%d", &value);
  printf("Введите основание: ");
  scanf("%d", &n);
  do {
    push(stk, value%n);
    value = value /n;
  } while(value > 0);
  do {
    printf("%x",pop(stk));
  } while(isempty(stk)==0);
  getchar(); getchar();
  return 0;
}

Результат выполнения
Результат перевода числа в другую систему счисления
Назад

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *