моя контактная информация
Почтамезофия@protonmail.com
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
ссылка на ОЖ:225. Используйте очереди для реализации стеков — LeetCode
Хорошо, давайте посмотрим на заголовок.
Идеи : используйте две очереди и всегда оставляйте одну очередь пустой. Когда нам нужно поместить данные в стек, поместите данные в непустую очередь (если обе пусты, поместите их в любую очередь). Когда требуется операция извлечения, данные из непустой очереди импортируются в пустую очередь, оставляя только одни данные. В это время эти данные можно вернуть и удалить.Определите, пуст ли стек, то есть пусты ли две очереди одновременно.
Например, мы будем 1，2，3，4 Занесение в стек на самом деле означает попадание в одну из очередейq1 середина
Если мы хотим вытащить стек, должны ли мы следовать 4，3，2，1 по порядку, мы будем1，2，3 push во вторую очередьq2 в, затем вq1 серединаpop 4 Завершите одноэтапную операцию извлечения стека.
Тогда мы сможем push q2 середина1，2 приезжатьq1 , поэтому вы можете оставить один3 существоватьq2 Затемpop q2 Вот и все3 Поп-операция
Этот цикл может завершить все операции извлечения стека.
Вот реализация кода:
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);
}
ссылка на ОЖ:232. Использование стека для реализации очереди — LeetCode
Хорошо, давайте посмотрим на заголовок.
Идеи : использовать два стека: первый стек используется только для ввода данных, а второй стек — только для вывода данных.Если данные необходимо вывести, но второй стек пуст, сначала импортируйте данные из первого стека во второй стек по одному, а затем выведите данные из второго стека.
Например, я хочу подписаться 1，2，3，4 в очередь в порядке1，2，3，4 Чтобы исключить заказ из очереди, мы можем сначала поместить его в стек, а затем импортировать данные из первого стека во второй по одному и просто ввести
Вот реализация кода:
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);
}
ссылка на ОЖ:20. Допустимые скобки — LeetCode
Хорошо, давайте посмотрим на заголовок.
Идеи: Этот вопрос представляет собой типичное применение стека, удовлетворяющее правилу «последним пришел — первым вышел» (Открывающая скобка, помещенная в стек последней, сначала будет соответствовать закрывающей скобке, появившейся первой. ). Пересеките строку и поместите ее прямо в стек, когда встретите открывающуюся скобку. При обнаружении задней скобки определите, соответствует ли задняя скобка передней скобке в верхней части стека (если в этот момент стек пуст, строка недопустима. Если она не совпадает, строка недействительна). он соответствует, удалите элемент из вершины стека и продолжайте обход строки символов, пока обход строки не будет завершен.При прохождении строки проверьте, пуст ли стек. Если он пуст, строка действительна. Если она не пуста, это означает, что передняя скобка не совпадает и строка недействительна.
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;
}
ссылка на ОЖ:622. Проектирование круговой очереди - LeetCode
Хорошо, давайте посмотрим на заголовок.
Идеи : В циклической очереди, когда очередь пуста, начало и конец очереди указывают на одну и ту же позицию. Когда очередь не пуста, начало очереди указывает на первые вставленные данные, а хвост очереди указывает на позицию, следующую за последними данными. Когда Tail+1 равен Front, это означает, что кольцевая очередь заполнена.
Уведомление : хвост циклической очереди не может указывать на последние данные, как хвост обычной очереди. В этом случае мы не сможем определить, является ли статус циклической очереди пустым или полным, потому что в это время. и начало, и конец очереди указывают на одну и ту же позицию. Это означает, что мы должны оставить пространство, в котором нельзя хранить данные, чтобы мы могли хорошо различать, является ли состояние кольцевой очереди пустым или полным.
Код реализации следующий:
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);
}
Он посвятил себя исследованию технологий более 30 лет и владеет различными языками, такими как Java, Linux, Javascript, php, css и т. д. Он внес большой вклад в область открытого исходного кода. Станция документации для разработчиков, где можно поделиться некоторыми проблемами в разработке технологий для дальнейшего использования. Все ознакомьтесь.
Почтамезофия@protonmail.com