技術共有

[OJ の質問を積み上げてキューに入れる]

2024-07-12

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

OJ の質問を積み重ねてキューに入れる

記事ディレクトリ

1. キューを使用してスタックを実装する

OJリンク:225. キューを使用してスタックを実装する - LeetCode

さて、タイトルから見てみましょう。

ここに画像の説明を挿入します

アイデア : 2 つのキューを使用し、1 つのキューを常に空にしておきます。データをスタックにプッシュする必要がある場合は、空ではないキューにデータを入れます (両方が空の場合は、いずれかのキューにデータをプッシュします)。ポップ操作が必要な場合、空でないキュー内のデータは空のキューにインポートされ、この時点でこのデータは 1 つだけ返されて削除されます。スタックが空かどうか、つまり 2 つのキューが同時に空かどうかを判断します。

たとえば、 1，2，3，4 スタックにプッシュするということは、実際にはキューの 1 つに入るということですq1 真ん中

ここに画像の説明を挿入します

スタックをポップアウトしたい場合は、次のようにする必要がありますか 4，3，2，1 順番に、私たちはそうします1，2，3 push 2番目の列へq2 で、そしてでq1 真ん中pop 4 スタックをポップするワンステップ操作を完了する

ここに画像の説明を挿入します

そうすれば、私たちはできる push q2 真ん中1，2 到着q1 、1つ残しておいても大丈夫です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);
}


  • 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. スタックを使用してキューを実装する

OJリンク:232. スタックを使用してキューを実装する - LeetCode

さて、タイトルから見てみましょう。

ここに画像の説明を挿入します

アイデア : 2 つのスタックを使用します。最初のスタックはデータ入力のみに使用され、2 番目のスタックはデータ出力のみに使用されます。データを出力する必要があるが、2 番目のスタックが空の場合は、最初のスタックのデータを 1 つずつ 2 番目のスタックにインポートし、その後 2 番目のスタックからデータを出力します。

たとえば、フォローしたい 1，2，3，4 の順番でキューに並びます1，2，3，4 順序に従ってデキューするには、まずスタックにデータを置き、次に最初のスタックのデータを 1 つずつ 2 番目のスタックにインポートし、次のように入力します。

ここに画像の説明を挿入します

コードの実装は次のとおりです。

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. 括弧の一致の問題

OJリンク: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;
}


  • 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. 循環キュー

OJリンク: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);
}

  • 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

個人プロフィール

彼は 30 年以上テクノロジーの研究に専念しており、Java、Linux、JavaScript、PHP、CSS などのさまざまな言語に堪能であり、オープンソース分野で多くの貢献を行っています。将来の参考のために技術開発におけるいくつかの問題を共有する開発者ドキュメント ステーション。

私の連絡先情報

郵便