¿Por qué inicializamos la parte superior de la stack como -1?

¿Por qué tengo que inicializar una de las stacks a -1? ¿A dónde apuntaría top1?

int ar[SIZE]; int top1 = -1; int top2 = SIZE; void push_stack1 (int data) { if (top1 < top2 - 1) { ar[++top1] = data; } else { printf ("Stack Full! Cannot Push\n"); } } 

La diferencia es si permite que top1 apunte al último elemento utilizado o al primer elemento libre.

Con -1 dejas que apunte al último elemento utilizado.

Con 0 dejas que apunte al primer elemento libre.

También hay simetría en el uso de pre-incremento / decremento y post-incremento / decremento.

Inicializar a -1 implica ++top1 para push y top1-- para pop.

Inicializar a 0 implica top1++ para push y --top1 para pop.

No, no tendría que inicializar top1 como -1 si su código hubiera sido:

 int ar[SIZE]; int top1 = 0; // 0 `here` int top2 = SIZE; void push_stack1 (int data) { // v conditional check with `<=` instead of `<` if (top1 <= top2 - 1) // even better: `if (top1 < top2)` { ar[top1++] = data; // ^ using "top1++" instead of "++top1" } else { printf ("Stack Full! Cannot Push\n"); } } 

++something (también conocido como pre-incremento) incrementará el valor de something y luego devolverá el valor incrementado.

Mientras que, something++ (también conocido como post-incremento) incrementará el valor de something , pero devolverá el valor original que something tenía antes de ser incrementado.

Pero debe tener en cuenta que si es ++top1 o top1++ , siempre pasamos 0 como primer índice a ar porque 0 es el primer índice de cualquier matriz / lista en todos los idiomas.

Es realmente extraño que empiece a pensar que en la implementación de la estructura de datos de la stack, tendría que inicializar top con -1 . ¿Qué libro dijo eso? Si algún libro lo hizo, en su mejor versión puede significar que la implementación que mostraron está siguiendo eso .

¿A dónde apuntaría top1 ? Si indexa directamente en un objeto de matriz, entonces sí, probablemente intentaría acceder a una memoria que está fuera del límite de la matriz, lo que seguramente es un comportamiento indefinido (las matrices están indexadas en 0 en C). Pero en todos los escenarios, vemos una implementación donde la top se incrementa primero (en caso de que la top se inicie con -1 ) ++top y luego ese valor se usa para indexar en la matriz (por primera vez, esto dará como resultado 0 ), Es precisamente el caso aquí. (La matriz se menciona aquí porque parece que la estructura de datos subyacente del código que mostró usa eso).

Así que top=-1 inicialmente significará que está en un estado vacío y puede decir que no se está agregando ningún miembro a la estructura de datos de la stack. Aquí podría haber inicializado top con 0 , siempre y cuando tuviera que cambiar su push , pop o isEmpty() y otras funciones auxiliares asociadas con la implementación de esta estructura de datos según corresponda, según sea necesario.

También puede verificar la implementación de su otra función para obtener la justificación de top=-1 para la implementación con la que está trabajando.


Además, si tiene dudas sobre lo que ++ hace aquí y por qué es significativo: vea lo que el estándar C11 tiene que decir al respecto (N1570Draft)

En la sección § 6.5.3.1¶2.

El valor del operando del operador prefijo ++ se incrementa. El resultado es el nuevo valor del operando después del incremento.

++top1 resultará en el nuevo valor incrementado que es 0 en caso de que fuera -1 anterior.