¿Qué es una pila? Por favor explique en detalle

1. Conceptos básicos

En informática, una pila es una tabla lineal que se limita a operaciones de inserción o eliminación únicamente al final de la tabla.

Una pila es una estructura de datos, una lista lineal especial que sólo se puede insertar y eliminar en un extremo. Almacena datos de acuerdo con el principio de primero en entrar, último en salir. Los datos que ingresan primero se colocan en la parte inferior de la pila y los últimos datos se extraen en la parte superior de la pila. desde la parte superior de la pila (los últimos datos se leen primero).

Una pila es una lista lineal especial que permite operaciones de inserción y eliminación en el mismo extremo. El extremo que permite las operaciones de inserción y eliminación se llama la parte superior de la pila, y el otro extremo es la parte inferior. La parte inferior de la pila es fija y la parte superior de la pila flota cuando el número de elementos en la pila es cero. , se llama pila vacía. La inserción generalmente se llama PUSH y la eliminación se llama popping (POP). La pila también se denomina tabla de último en entrar, primero en salir (tabla LIFO).

La pila se puede usar para almacenar puntos de interrupción cuando se llaman funciones. ¡La pila se usa cuando se realiza recursividad!

Modelo de pila 2. Algoritmo básico

1. Algoritmo PUSH

① Si TOP ≥ n, se proporcionará información de desbordamiento y el manejo de errores (antes de ingresar). la pila, primero verifique si la pila está llena, si está llena, se desbordará; de lo contrario, haga ②

②Establezca TOP=TOP+1 (el puntero de la pila agrega 1, apuntando a); dirección de inserción);

③S(TOP)=X, end (X es el elemento recién insertado);

2. Algoritmo de pop-off (POP)

①Si TOP≤ 0, se proporcionará información de subdesbordamiento y se realizará el manejo de errores (verifique si la pila está vacía antes de sacarla; si está vacía, se desbordará; si no está vacía, haga ②); /p>

②X=S(TOP), (Los elementos después de salir de la pila se asignan a

3. Implementación de la pila

Implementación bajo pascal

1. Tipo de matriz

Const

m=. el límite superior del número de entradas de la pila

Type

stack=array[1..m] de stype; /p>

Var

s:stack;{stack}

top:integer; {puntero superior de la pila}

2. type

const

m=el límite superior del número de entradas de la pila

type

stack=record

elem: matriz[1..m] de elemtp;

top:0..m; {puntero superior de la pila}

end;

Var

s:stack;{stack}

Algunas operaciones básicas de la pila en C/C++:

Código C:

/*

@**2009/09 /24

Operaciones básicas de pila

*/

#include

#define MaxSize 100

usando el espacio de nombres std;

typedef struct

{

int data[MaxSize];

int top;

}SqStack;

void InitStack(SqStack *st) //Pila de inicialización

{

st->top=-1;

}

int StackEmpty(SqStack *st) //Juzga que la pila está vacía

{

return (st->top==-1 );

}

void Push(SqStack *st,int x) //Los elementos se insertan en el pila

{

if(st ->top==MaxSize-1)

printf("¡Desbordamiento de pila!\n");

else

{

st->top++;

st->datos[st->top]=x;

}

}

void Pop(SqStack *st) //Explota la pila

{

if(st->top ==-1)

printf("Desbordamiento insuficiente de pila\ n");

else

st->top--;

}

int Gettop(SqStack *st) // Obtiene el elemento superior de la pila

{

if(st->top==-1 )

{

printf("La pila está vacía \n");

devuelve 0;

}

else

return st->data[st->top];

}

void Display(SqStack *st) //Imprime los elementos en la pila

{

int i;

printf("Elemento en la pila: ");

for(i=st- >arriba;i>=0;--i)

printf("%d ",st->datos[i]);

printf("\n");

}

int principal()

{<

/p>

SqStack L;

SqStack *st=&L;

InitStack(st);

printf("Pila vacía: %d\ n",StackEmpty(st));

for(int i=1;i<10;++i)

Push(st,i);

Display(st);

printf("Retroceda la pila una vez\n");

Pop(st);

printf("El elemento superior de la pila :%d\n",Gettop(st));

Pop(st);

Display(st);

return 0;

}