Mi informacion de contacto
Correo[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Enlace del DO:225. Utilice colas para implementar pilas - LeetCode
Bien, echemos un vistazo al título. El título dice esto.
Ideas : Utilice dos colas y mantenga siempre una cola vacía. Cuando necesitemos enviar datos a la pila, colóquelos en una cola que no esté vacía (si ambas están vacías, envíelos a cualquier cola). Cuando se requiere una operación emergente, los datos de la cola no vacía se importan a la cola vacía, dejando solo un dato. En este momento, estos datos se pueden devolver y eliminar.Determine si la pila está vacía, es decir, si las dos colas están vacías al mismo tiempo
Por ejemplo, lo haremos 1，2，3，4 Entrar en la pila en realidad significa ingresar a una de las colas.q1 medio
Si queremos sacar la pila, ¿deberíamos seguir? 4，3，2，1 en orden, lo haremos1，2，3 push a la segunda colaq2 en, luego enq1 mediopop 4 Complete la operación de un solo paso para hacer estallar la pila
Entonces podemos push q2 medio1，2 llegarq1 , así que puedes dejar uno3 existirq2 Entoncespop q2 Eso es todo3 La operación pop
Este bucle puede completar todas las operaciones de extracción de la pila.
Aquí está la implementación del código:
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
void QueueInit(Queue* pq)
{
assert(pq);
pq->size = 0;
pq->head = pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* del = cur;
cur = cur->next;
free(del);
}
pq->size = 0;
pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc failn");
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
bool QueueEmpty(Queue* pq)
{
return pq->tail == NULL && pq->head == NULL;
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(!(QueueEmpty(pq)));
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* del = pq->head;
pq->head = pq->head->next;
free(del);
del = NULL;
}
pq->size--;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!(QueueEmpty(pq)));
return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!(QueueEmpty(pq)));
return pq->tail->data;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&obj->q1);
QueueInit(&obj->q2);
return obj;
}
void myStackPush(MyStack* obj, int x) {
if (!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1, x);
}
else
{
QueuePush(&obj->q2, x);
}
}
int myStackPop(MyStack* obj) {
Queue* empty = &obj->q1;
Queue* noEmpty = &obj->q2;
if (!QueueEmpty(&obj->q1))
{
empty = &obj->q2;
noEmpty = &obj->q1;
}
while (QueueSize(noEmpty) > 1)
{
QueuePush(empty, QueueFront(noEmpty));
QueuePop(noEmpty);
}
int top = QueueFront(noEmpty);
QueuePop(noEmpty);
return top;
}
int myStackTop(MyStack* obj) {
if (!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
QueueDestory(&obj->q1);
QueueDestory(&obj->q2);
free(obj);
}
Enlace del DO:232. Utilice la pila para implementar la cola - LeetCode
Bien, echemos un vistazo al título. El título dice esto.
Ideas : Utilice dos pilas, la primera pila solo se usa para la entrada de datos y la segunda pila solo se usa para la salida de datos.Cuando es necesario generar datos pero la segunda pila está vacía, primero importe los datos de la primera pila a la segunda pila uno por uno y luego envíe los datos de la segunda pila.
Por ejemplo, quiero seguir 1，2，3，4 en la cola en el orden de1，2，3，4 Para quitar la cola en el orden, primero podemos colocarlos en una pila y luego importar los datos de la primera pila a la segunda pila uno por uno, y simplemente ingresar
Aquí está la implementación del código:
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->_top == 0;
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->_top;
}
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->_a[ps->_top - 1];
}
void StackInit(Stack* ps)
{
assert(ps);
ps->_a = NULL;
ps->_capacity = ps->_top = 0;
}
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
if (ps->_top == ps->_capacity)
{
int newCapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->_a, newCapacity * sizeof(STDataType));
if (NULL == tmp)
{
perror("malloc fail");
exit(-1);
}
ps->_a = tmp;
ps->_capacity = newCapacity;
}
ps->_a[ps->_top] = data;
ps->_top++;
}
void StackPop(Stack* ps)
{
assert(ps);
ps->_top--;
}
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_capacity = ps->_top = 0;
}
typedef struct {
Stack pushST;
Stack popST;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
StackInit(&obj->pushST);
StackInit(&obj->popST);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->pushST, x);
}
void PushSTToPopST(MyQueue* obj)
{
if (StackEmpty(&obj->popST))
{
while (!StackEmpty(&obj->pushST))
{
StackPush(&obj->popST, StackTop(&obj->pushST));
StackPop(&obj->pushST);
}
}
}
int myQueuePop(MyQueue* obj) {
PushSTToPopST(obj);
int front = StackTop(&obj->popST);
StackPop(&obj->popST);
return front;
}
int myQueuePeek(MyQueue* obj) {
PushSTToPopST(obj);
int front = StackTop(&obj->popST);
return front;
}
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->popST) && StackEmpty(&obj->pushST);
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->pushST);
StackDestroy(&obj->popST);
free(obj);
}
Enlace del DO:20. Paréntesis válidos - LeetCode
Bien, echemos un vistazo al título. El título dice esto.
Ideas: Esta pregunta es una aplicación típica de la pila, que satisface la regla de último en entrar, primero en salir (El paréntesis de apertura que se inserta en último lugar en la pila coincidirá primero con el paréntesis final que aparece primero. ). Atraviese la cuerda y empújela directamente sobre la pila cuando encuentre el paréntesis de apertura. Cuando se encuentra un corchete posterior, determine si el corchete posterior coincide con el corchete frontal en la parte superior de la pila (si la pila está vacía en este momento, la cadena no es válida), si no coincide, la cadena no es válida; coincide, elimine el elemento en la parte superior de la pila y continúe atravesando la cadena de caracteres hasta que se complete el recorrido de la cadena.Cuando se recorre la cadena, verifique si la pila está vacía. Si está vacía, la cadena es válida. Si no está vacía, significa que el corchete frontal no coincide y la cadena no es válida.
typedef char STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->_top == 0;
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->_top;
}
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->_a[ps->_top - 1];
}
void StackInit(Stack* ps)
{
assert(ps);
ps->_a = NULL;
ps->_capacity = ps->_top = 0;
}
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
if (ps->_top == ps->_capacity)
{
int newCapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->_a, newCapacity * sizeof(STDataType));
if (NULL == tmp)
{
perror("malloc fail");
exit(-1);
}
ps->_a = tmp;
ps->_capacity = newCapacity;
}
ps->_a[ps->_top] = data;
ps->_top++;
}
void StackPop(Stack* ps)
{
assert(ps);
ps->_top--;
}
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_capacity = ps->_top = 0;
}
bool isValid(char * s){
Stack st;
StackInit(&st);
while(*s)
{
if(*s == '(' || *s == '[' || *s == '{')
{
StackPush(&st, *s);
}
else
{
if(StackEmpty(&st))
{
StackDestroy(&st);
return false;
}
else
{
if((*s == ')' && StackTop(&st) != '(')
|| (*s == ']' && StackTop(&st) != '[')
|| (*s == '}' && StackTop(&st) != '{'))
{
StackDestroy(&st);
return false;
}
StackPop(&st);
}
}
++s;
}
if(!StackEmpty(&st))
{
StackDestroy(&st);
return false;
}
return true;
}
Enlace del DO:622. Diseñar cola circular - LeetCode
Bien, echemos un vistazo al título. El título dice esto.
Ideas : En una cola circular, cuando la cola está vacía, el principio y el final de la cola apuntan a la misma posición. Cuando la cola no está vacía, el encabezado de la cola apunta a los primeros datos insertados y el final de la cola apunta a la posición junto a los últimos datos. Cuando tail+1 es igual a front, significa que la cola del anillo está llena.
Aviso : La cola de la cola circular no puede apuntar a los últimos datos como la cola de la cola normal. Si este es el caso, no podremos distinguir si el estado de la cola circular está vacío o lleno, porque en este momento. tanto la cabeza como la cola de la cola apuntan a la misma posición. Esto significa que debemos dejar un espacio que no pueda almacenar datos, para que podamos distinguir bien si el estado de la cola del anillo está vacío o lleno.
El código de implementación es el siguiente:
typedef struct {
int* a;
int head;
int tail;
int size;
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->head == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->tail + 1) % obj->size == obj->head;
}
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a = (int*)malloc(sizeof(int) * (k+1));
obj->head = obj->tail = 0;
obj->size = k + 1;
return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
{
return false;
}
else
{
obj->a[obj->tail] = value;
obj->tail++;
obj->tail %= obj->size;
return true;
}
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return false;
}
else
{
obj->head++;
obj->head %= obj->size;
return true;
}
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->a[obj->head];
}
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->a[(obj->tail - 1 + obj->size) % obj->size];
}
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
Se ha dedicado a la investigación de tecnología durante más de 30 años y domina varios lenguajes como java, linux, javascript, php, css, etc. Ha realizado muchas contribuciones en el campo del código abierto. Estación de documentación para desarrolladores para compartir algunos problemas en el desarrollo de tecnología para referencia futura.
Correo[email protected]