Berbagi teknologi

[Tumpuk dan antri pertanyaan OJ]

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Tumpuk dan antri pertanyaan OJ

Direktori artikel

1. Gunakan antrian untuk mengimplementasikan tumpukan

Tautan OJ:225. Gunakan antrian untuk mengimplementasikan tumpukan - LeetCode

Oke, mari kita lihat judulnya

Masukkan deskripsi gambar di sini

Ide ide : Gunakan dua antrian dan selalu kosongkan satu antrian. Saat kita perlu memasukkan data ke dalam tumpukan, masukkan data ke dalam antrian yang tidak kosong (jika keduanya kosong, masukkan ke dalam antrian mana saja). Ketika operasi pop diperlukan, data dalam antrian yang tidak kosong diimpor ke dalam antrian yang kosong, hanya menyisakan satu data. Saat ini, data tersebut dapat dikembalikan dan dihapus.Tentukan apakah tumpukan tersebut kosong, yaitu apakah kedua antrian tersebut kosong pada saat yang bersamaan

Misalnya, kami akan melakukannya 1，2，3，4 Mendorong ke dalam tumpukan sebenarnya berarti memasuki salah satu antrianq1 tengah

Masukkan deskripsi gambar di sini

Jika kita ingin mengeluarkan tumpukan tersebut, sebaiknya kita ikuti 4，3，2，1 secara berurutan, kami akan melakukannya1，2，3 push ke antrian keduaq2 masuk, lalu masukq1 tengahpop 4 Selesaikan operasi satu langkah untuk mengeluarkan tumpukan

Masukkan deskripsi gambar di sini

Lalu kita bisa push q2 tengah1，2 tibaq1 , jadi kamu bisa menyisakan satu3 adaq2 Kemudianpop q2 Itu dia3 Operasi pop

Masukkan deskripsi gambar di sini

Loop ini dapat menyelesaikan semua operasi popping tumpukan.

Masukkan deskripsi gambar di sini

Berikut implementasi kodenya:

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);
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193

2. Gunakan tumpukan untuk mengimplementasikan antrian

Tautan OJ:232. Gunakan tumpukan untuk mengimplementasikan antrian - LeetCode

Oke, mari kita lihat judulnya

Masukkan deskripsi gambar di sini

Ide ide : Gunakan dua tumpukan, tumpukan pertama hanya digunakan untuk input data, dan tumpukan kedua hanya digunakan untuk keluaran data.Jika data perlu dikeluarkan tetapi tumpukan kedua kosong, pertama-tama impor data di tumpukan pertama ke tumpukan kedua satu per satu, lalu keluarkan data dari tumpukan kedua.

Misalnya saya ingin mengikuti 1，2，3，4 ke dalam antrian secara berurutan1，2，3，4 Untuk melakukan dequeue pada urutannya, pertama-tama kita dapat memasukkannya ke dalam tumpukan, lalu mengimpor data di tumpukan pertama ke tumpukan kedua satu per satu, dan tinggal memasukkan

Masukkan deskripsi gambar di sini

Berikut implementasi kodenya:

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);
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145

3. Masalah pencocokan braket

Tautan OJ:20. Tanda kurung yang valid - LeetCode

Oke, mari kita lihat judulnya

Masukkan deskripsi gambar di sini

Ide ide: Pertanyaan ini adalah tipikal penerapan tumpukan, yang memenuhi aturan masuk terakhir keluar pertama (Tanda kurung pembuka yang dimasukkan ke dalam tumpukan terakhir akan terlebih dahulu cocok dengan tanda kurung akhir yang muncul pertama kali. ). Lintasi string dan dorong langsung ke tumpukan saat menemukan tanda kurung buka. Ketika braket belakang ditemukan, tentukan apakah braket belakang cocok dengan braket depan di bagian atas tumpukan (jika tumpukan saat ini kosong, string tidak valid). cocok, hapus elemen di bagian atas tumpukan dan lanjutkan melintasi karakter hingga penjelajahan string selesai.Saat string dilintasi, periksa apakah tumpukannya kosong. Jika kosong, string tersebut valid. Jika tidak kosong, berarti braket depan tidak cocok dan string tersebut tidak valid.

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;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129

4. Antrian Melingkar

Tautan OJ:622. Desain antrian melingkar - LeetCode

Oke, mari kita lihat judulnya

Masukkan deskripsi gambar di sini

Ide ide : Pada antrian melingkar, ketika antrian kosong, kepala dan ekor antrian menunjuk pada posisi yang sama. Jika antrian tidak kosong, kepala antrian menunjuk ke data pertama yang dimasukkan, dan ekor antrian menunjuk ke posisi di sebelah data terakhir. Jika tail+1 sama dengan front, berarti antrian ring sudah penuh.
Melihat : Ekor antrian melingkar tidak dapat menunjuk ke data terakhir seperti ekor antrian biasa. Jika demikian, kita tidak akan bisa membedakan status antrian melingkar kosong atau penuh, karena saat ini. baik kepala maupun ekor antrian mengarah ke posisi yang sama. Artinya kita harus menyisakan ruang yang tidak bisa menyimpan data, agar kita bisa membedakan dengan baik status antrian deringnya kosong atau penuh.
Masukkan deskripsi gambar di sini

Kode implementasinya adalah sebagai berikut:

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);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78

Profil pribadi

Ia telah mengabdikan dirinya untuk meneliti teknologi selama lebih dari 30 tahun, dan mahir dalam berbagai bahasa seperti java, linux, javascript, php, css, dll. Saya telah memberikan banyak kontribusi di bidang dokumentasi pengembang open source untuk berbagi beberapa masalah dalam pengembangan teknologi untuk referensi di masa mendatang.

informasi kontak saya

Surat