Стек. Основни операции.

Стек се нарича списък, при който включването на нови елементи, както и изключването на елементи се извършва само от едната страна на списъка, наречена връх на стека. Възможен е пряк достъп само до елемента, който се намира във върха на стека. Синоним на стек е термина LIFO (last in – first out).

За представяне на последователни стекове се използва последователно разпределена памет, т.е. елементи на стека се записват в последователно разположени полета в оперативната памет на компютъра.

Алгоритъм за добавяне на елемент:
n++; x[n] = addvalue;

Алгоритъм за изключване на елемент:
savevalue = x[n]; n--;

Недостатъкът на тези алгоритми е, че те не отчитат случаите при които няма достатъчно памет за добавяне на нов елемент или когато се прави опит за изключване на елемент от празен стек. Ще ги модифицираме, нека M е максималният допустим за върха на стека.

Алгоритъм за добавяне на елемент:
ако n==M, препълване; край;
ако n < M, n++; x[n] = addvalue;


Алгоритъм за изключване на елемент:
ако n==0, празен стек; край;
ако n > 0, savevalue = x[n]; n--;


Примерна програма.

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define M 100
  5. typedef float ElementType;
  6.  
  7. struct Stack
  8. {
  9.     int t;
  10.     ElementType StackArray[M];
  11. };
  12.  
  13. void push(struct Stack *s, ElementType x)
  14. {
  15.     if(s->t == M)
  16.     {
  17.         printf ("Препълване на стека!\n");
  18.         exit (1);
  19.     }
  20.     s->StackArray[s->t++] = x;
  21. }
  22.  
  23. ElementType pop( struct Stack *s)
  24. {
  25.     ElementType x;
  26.     if(s->t==0)
  27.     {
  28.         printf ("Празен стек!\n");
  29.         exit (1);
  30.     }
  31.     x = s->StackArray[--s->t];
  32.     return x;
  33. }
  34.  
  35. void main()
  36. {
  37.     Stack s;
  38.     int i;
  39.     s.t = 0;
  40.     for (i = 1; i <= 100; i++)
  41.         push(&s, 1.1f);
  42.     for (i = 1; i <= 100; i++)
  43.         printf("%.2f\n", pop(&s));
  44. }