stack

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.

As you know, programs consist of two parts - algorithms and data structures. In a good program, these components effectively complement each other. The selection and implementation of the data structure is as important as the procedures for processing the data. The method of organizing and accessing information is usually determined by the nature of the programmed task. Thus, it is important for a programmer to have at his disposal techniques suitable for different situations.

The degree of data type binding to its machine representation is inversely related to its abstraction. In other words, the more abstract the data types become, the more the conceptual idea of ​​how this data is stored differs from the actual, actual way they are stored in computer memory. Simple types, for example, char or int , are closely related to their machine representation. For example, the machine representation of an integer value approximates well the corresponding programming concept. As they become more complex, data types become conceptually less similar to their machine equivalents. So, floating point real numbers are more abstract than integers. The actual representation of the type of float in the machine rather approximately corresponds to the representation of the average programmer about the real number. Even more abstract is the structure belonging to composite data types.

At the next level of abstraction, the purely physical aspects of the data fade into the background due to the introduction of the data engine to data, that is, the mechanism for storing and retrieving information. Essentially, the physical data is associated with an access mechanism that manages the handling of data from the program. This chapter is dedicated to data access mechanisms.

There are four access mechanisms:

• Queue
• Stack (stack) ^[1]
• Linked list ^[2]
• Binary tree (binary tree) ^[3]

Each of these methods makes it possible to solve problems of a particular class. These methods are essentially mechanisms that perform certain operations of storing and retrieving information transmitted to them based on the requests they receive. They all save and receive an element; here, an element means an information unit. This chapter shows how to create such access mechanisms in C. This illustrates some common programming techniques in C, including dynamic memory allocation and the use of pointers.

• Queues
• Cyclic queue
• Stacks
• Related Lists
• Singly linked lists
• Doubly linked lists
• Mailing List Example
• Binary trees

^[1] Other names: store, stack memory, store memory, store type memory, store type storage device, stack storage device.

^[2] Other names: chain list, list using pointers, list with links, list on pointers.

^[3] Other names: binary search tree.

  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 * /

 / * 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

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 
 #include 

 #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

^[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 .