Resumen de la revisión de la estructura de datos Capítulo 3 Pila y cola
Capítulo 3 Pila y cola
Pila
La definición y operaciones básicas de la pila
La pila está limitada a un solo extremo de la tabla La tabla lineal de operaciones de inserción y eliminación también se denomina tabla de último en entrar, primero en salir (tabla LIFO). El extremo de inserción y eliminación se denomina parte superior de la pila y el otro extremo se denomina parte inferior de la pila. pila. No hay elementos en la tabla y se llama pila vacía. Las operaciones básicas son
) initstack(s) Construir una pila vacía
<. p> ) stackempty(s) determina que la pila está vacía;
) stackfull(s) determina que la pila está llena
) push(s x) empuja hacia la pila;
) pop(s) salen de la pila
) stacktop(s) toman el elemento superior de la pila
Sequence Stack
La estructura de almacenamiento secuencial de la pila se denomina pila secuencial. El tipo de pila secuencial se define como
#define stacksize
typedef char datatype; p> typedef struct{
datatype data[stacksize];
int top;
}seqstack
Empujar cuando la pila está full La operación inevitablemente producirá un desbordamiento de espacio, lo que se denomina desbordamiento. Cuando la pila está vacía, una operación emergente inevitablemente producirá un desbordamiento de espacio, lo que se denomina desbordamiento. Se debe evitar el desbordamiento. El desbordamiento insuficiente se utiliza a menudo como condición para la transferencia del control del programa.
En secuencia Operaciones básicas en la pila
) Vaciar la pila
Void initstack(seqstack *s )
{
s >top=
}
) Determinar la pila vacía
int stackempty( seqstack *s)
>top==
}
) Determinar la pila llena
int stackfull(seqstack *s)
{
Return s >top==stacksize
}
) Empujar a la pila
Void push(seqstack *s tipo de datos x)
{
if(stackfull(s))
error( desbordamiento de pila
); s >data[++s >top]=x;
}
) Pop la pila
Tipo de datos pop(seqstack *s)
{
if(stackempty (s))
error( desbordamiento de pila
return S >data[s >top ]; p>
}
) Obtener el elemento superior de la pila
Dtatatype stacktop(seqstack *s)
{
if(stackempty(s))
error( desbordamiento de pila );
return S >data[s >top]
}
Pila de cadena
La estructura de almacenamiento en cadena de la pila. Se dice que el puntero superior de la pila de cadena es el puntero principal de la lista vinculada. Definición de tipo de la pila de cadena.
typedef struct stacknode{
datos de tipo de datos;
struct stacknode *next;
}stacknode;
typedef struct{
stacknode *top;
}linkstack;
Operaciones básicas en la pila de enlaces
) Construcción de pilas
Void initstack( linkstack *s)
{
s >top=NULL
}
) Determinar la pila vacía
{
return s >top==NULL
}
) Empujar en la pila;
Void push(linkstack *s tipo de datos x)
{
stacknode *p=(stacknode *)malloc(sizeof(stacknode)
>p >datos=x;
p >siguiente=s >arriba
s >arriba=p
}
) Pop
Tipo de datos pop(linksatck *s)
{
tipo de datos x
stacknode *p=s > arriba;
if(stackempty(s))
error( desbordamiento de pila
x=p >datos; >top=p >next;
free(p);
return x;
}
) Obtiene el elemento superior de la pila
Tipo de datos stacktop(linkstack *s)
{
if(stackempty(s))
error( la pila está vacía );
return s >top >data
}
Cola
Definición básica y cálculo de cola
Cola Es una tabla lineal con operaciones limitadas. El final que permite la eliminación se llama cabecera de la cola y el final que permite la inserción se llama cola. La cola también se llama lista lineal de primero en entrar, primero en salir. . Tabla FIFO
Operaciones básicas de la cola
) initqueue(q) deja la cola vacía
) queueempty(q) juzga que la cola está vacía;
) queuefull(q) juzga que la cola está llena;
) enqueue(q p>
La estructura de almacenamiento secuencial de la cola se llama cola secuencial. El frente y Los punteros posteriores representan las posiciones de los elementos de cabeza y cola de la cola en el espacio vectorial. Existe un fenómeno de desbordamiento falso en la cola secuencial porque las operaciones de poner en cola y quitar la cola solo hacen que los punteros de cabeza y cola aumenten pero no. disminuye, el espacio del elemento eliminado no se puede utilizar. El puntero de cola excede el límite superior del espacio vectorial y no se puede agregar a la cola.
Para superar el fenómeno de desbordamiento falso, imagine el espacio vectorial como un bucle conectado de extremo a extremo.
La cola en la que se almacena el vector de anillo se llama cola circular i=(i+)%queuesize
Dado que front==rear no se puede utilizar para determinar si la cola está vacía o llena, el procesamiento de condiciones de límite de la cola circular se resuelve mediante
p>
) Configure otra variable booleana para distinguir entre colas vacías y llenas
) Utilice un elemento menos para probar si rear plus; front en un sentido de bucle es igual a front antes de agregarlo a la cola
) Utilice un contador para registrar el número total de elementos
Definición de tipo de cola circular
#define tamaño de cola
typedef char tipo de datos;
typedef struct{
int front
int rear; >
int count;
datos de tipo de datos[tamaño de cola];
p>}cirqueue
) Void initqueue(cirqueue *q)
{
q > frontal=q >trasero= ;
q >count=
}
) Cola vacío
Int queueempty(cirqueue * q)
{
return q >count==
}
) El equipo está lleno
Int queuefull(cirqueue *q)
{
return q >count==queuesize
) Ingrese a la cola
Void enqueue(cirqueue *q tipo de datos x)
{
if(queuefull(q) )
error( cola superflua );
q >count++
q >datos[q >trasero]=x
q >rear=(q >rear+ )%queuesize;
}
) sacar de cola
Tipo de datos sacar de cola(cirqueue *q)
{
tipo de datos temp;
if(queueempty(q))
error( desbordamiento de cola
temp=q >datos); [q >front];
q >count;
q >front=(q >front+ )%queuesize
return temp;
}
) Obtener elemento de encabezado de cola
Tipo de datos queuefront(cirqueue *q)
{
if(queueempty(q ))
error( la cola está vacía
return q >data[q >front]
}
Cola en cadena;
La estructura de almacenamiento en cadena de la cola se llama Cola en cadena. La cola en cadena consta de un puntero principal y un puntero final.
Determinado de forma única
Definición de cola en cadena
typedef struct queuenode
{
datatype data
struct queue; *siguiente;
}queuenode;
typedef struct
{
queuenode *frente
queuenode * rear;
}linkqueue;
) Crear cola vacía
Void initqueue(linkqueue *q)
{
q >front=q >rear=NULL;
}
) Cola vacía
Int queueempty(linkqueue *q)
{
return q >front==NULL&&q >rear==NULL
}
) Poner en cola
Vacío en cola (linkqueue; *q tipo de datos x)
{
nodo de cola *p=(nodo de cola *)malloc(sizeof(nodo de cola)); /p>
p >siguiente=NULL;
if(queueempty(q))
q frontal=q >trasero=p
else; {
q >trasero >siguiente=p
q >trasero=p
}
}
) Quitar de cola
Tipo de datos sacar de cola(linkqueue *q)
{
tipo de datos x
queuenode *p; >
if(queueempty(q))
error( la cola está desbordada
p=q >front; ;
q >frontal=p >siguiente;
if(q >trasero==p) q >trasero=NULL
libre( p);
return >
{
if(queueempty(q))
error( la cola está vacía
return q); >front >data;
}
Apéndice 2:
Capítulo 3 Apilar y poner en cola
******* ******** ******************************************* ********* *************************
La pila es una tabla lineal que solo limita la inserción y operaciones de eliminación en un extremo de la tabla. Esto se llama inserción y eliminación. Un extremo es la parte superior de la pila y el otro extremo se llama la parte inferior de la pila.
La pila está vacía cuando no hay elementos. La pila se modifica de acuerdo con el principio de último en entrar, primero en salir. También llamamos a la pila tabla LIFO (el último en entrar, primero en salir). pila y pila en cadena
**************************************** ************ *************************************