Stacks on the example of the C language

Stack (stack) is like the opposite of the queue, because it works on the principle of "last come - first out" (last-in, first-out, LIFO) ^[1] . To visualize the stack, remember the stack of plates. The first plate on the table will be used last, and the last plate placed on top will be used first. Stacks are often used in system software, including compilers and interpreters.

When working with stacks, the entry and retrieval operations of the element are basic. These operations are traditionally called "pushing into the stack" (push) ^[2] and "pushing out of the stack" (pop) ^[3] . Therefore, to implement the stack, you need to write two functions: push () , which "pushes" the value onto the stack, and pop () , which "pushes" the value out of the stack. You also need to allocate a memory area that will be used as a stack. For this purpose, you can allocate an array or dynamically allocate a fragment of memory using the C language functions provided for dynamic memory allocation. As in the case of a queue, the extraction function retrieves an item from the list and deletes it if it is not stored anywhere else. Below is the general form of the push () and pop () functions that work with an integer array. Other data type stacks can be organized by changing the underlying data type of the array.

  int stack [MAX];
 int tos = 0;  / * top of stack * /

 / * Push item to stack.  * /
 void push (int i)
 {

   if (tos> = MAX) {
     printf ("Stack full \ n");
     return;
   }
   stack [tos] = i;
   tos ++;
 }

 / * Get the top of the stack.  * /
 int pop (void)
 {
   tos--;
   if (tos <0) {
     printf ("The stack is empty \ n");
     return 0;
   }
   return stack [tos];
 }

The variable tos ("top of stack" - "top of the stack" ^[4] ) contains the index of the top of the stack. When implementing these functions, you must consider the cases when the stack is full or empty. In our case, the sign of an empty stack is the equality tos to zero, and a sign of stack overflow is an increase in tos that its value points somewhere outside the last cell of the array. An example of the stack is shown in Table. 22.2.

A perfect example of using a stack is a four-action calculator. Most modern calculators perceive a standard notation of expressions, called an infix notation ^[5] , the general form of which looks like an operand-operator-operand . For example, to add 100 and 200, you must enter 100 , press the "plus" ("+") button, then enter 200 and press the "equals" ("=") button. In contrast, many early calculators (and some of those produced today) use a postfix notation ^[6] , in which both operands are first entered, and then the operator. For example, to add 100 and 200 in a postfix notation, you must enter 100 , then 200 , and then press the plus key. In this method, the input operands are pushed onto the stack. When the operator is entered, operands are retrieved (pushed out) from the stack, and the result is pushed back to the stack. One of the advantages of the postfix form is the ease of entering long complex expressions.

The following example demonstrates the use of a stack in a program that implements a postfix calculator for integer expressions. First you need to modify the functions push () and pop () , as shown below. You should be aware that the stack will be placed in a dynamically allocated memory, and not in a fixed-size array. Although the application of dynamic memory allocation is not required in such a simple example, we will see how to use dynamic memory to store stack data.

  int * p;  / * pointer to free memory * /
 int * tos;  / * pointer to the top of the stack * /
 int * bos;  / * pointer to the bottom of the stack * /

 / * Putting an item on the stack.  * /
 void push (int i)
 {
   if (p> bos) {
     printf ("The stack is full \ n");
     return;
   }
   * p = i;
   p ++;
 }

 / * Getting the top item from the stack.  * /
 int pop (void)
 {
   p--;
   if (p <tos) {
     printf ("The stack is empty \ n");
     return 0;
   }
   return * p;
 }

Before using these functions, it is necessary to allocate memory from the free memory area using the malloc () function and assign the address of the beginning of this area to the variable tos , and the address of its end to the variable bos .

The text of the postfix calculator program is shown below.

  / * A simple four-action calculator.  * /

 #include <stdio.h>
 #include <stdlib.h>

 #define MAX 100

 int * p;  / * pointer to free memory * /
 int * tos;  / * pointer to the top of the stack * /
 int * bos;  / * pointer to the bottom of the stack * /

 void push (int i);
 int pop (void);

 int main (void)
 {
   int a, b;
   char s [80];

   p = (int *) malloc (MAX * sizeof (int));  / * get stack memory * /
   if (! p) {
     printf ("Error allocating memory \ n");
     exit (1);
   }
   tos = p;
   bos = p + MAX-1;

   printf ("Calculator with four actions \ n");
   printf ("Press 'q' to exit \ n");

   do {
     printf (":");
     gets (s);
     switch (* s) {
       case '+':
         a = pop ();
         b = pop ();
         printf ("% d \ n", a + b);
         push (a + b);
         break;
       case '-':
         a = pop ();
         b = pop ();
         printf ("% d \ n", ba);
         push (ba);
         break;
       case '*':
         a = pop ();
         b = pop ();
         printf ("% d \ n", b * a);
         push (b * a);
         break;
       case '/':
         a = pop ();
         b = pop ();
         if (a == 0) {
           printf ("Divide by 0. \ n");
           break;
         }
         printf ("% d \ n", b / a);
         push (b / a);
         break;
       case '.': / * show the contents of the top of the stack * /
         a = pop ();
         push (a);
         printf ("The current value at the top of the stack:% d \ n", a);
         break;
       default:
         push (atoi (s));
     }
   } while (* s! = 'q');

   return 0;
 }

 / * The item is pushed onto the stack.  * /
 void push (int i)
 {
   if (p> bos) {
     printf ("The stack is full \ n");
     return;
   }
   * p = i;
   p ++;
 }

 / * Getting the top item from the stack.  * /
 int pop (void)
 {
   p--;
   if (p <tos) {
     printf ("The stack is empty \ n");
     return 0;
   }
   return * p;
 }

^[1] In other words, in the store order .

^[2] And also: push (to the stack), put on the stack, put on the stack, put on the stack, put on the stack, save on the stack .

^[3] And also: push data out of the stack, pushing it out of the stack, pushing data out of the stack, removing it from the stack, removing it from the stack, reading it from the stack, pulling it out of the stack .

^[4] Also called apex .

^[5] Other names: infix representation, infix notation .

^[6] Other names: postfix notation, Polish inverse .