アルゴリズム学習1週目.スタック/キュー
37981 ワード
stack
先入後出(LIFO)
データ構造
jsでのスタックメソッド
追加データ:
push
データ消去:pop
接続リストを使用したスタックの実装
class Node {
constructor(data) {
this.data = data;
this.prev = null;
}
}
class Stack {
constructor() {
this.top = null;
this.length = 0;
}
push(data) {
const newNode = new Node(data);
if (this.length === 0) {
this.top = newNode;
} else {
const preNode = this.top;
this.top = newNode;
this.top.prev = preNode;
}
this.length++;
}
peek() {
this.length && console.log(this.top.data);
}
pop() {
if (this.length === 0) {
console.error("stack is empty");
} else {
this.top = this.top.prev;
}
this.length--;
}
}
const stack = new Stack();
stack.push(1);
stack.peek();
stack.push(2);
stack.peek();
stack.push(3);
stack.peek();
stack.pop();
stack.pop();
stack.pop();
stack.peek();
スタック使用率の例
プロセスとスタック
プロセス
実行中のプログラム
ねじ山
プロセスの実行単位
プロセスのメモリ領域は4つの部分に分かれています.
stackにより、各スレッドは独立してストリームを実行できます.
スレッド間のテキスト領域共有により、関数呼び出しが可能になります.
スレッド間のデータ,ヒップ領域共有によりメモリ空間を共有し,スレッド間の通信を可能にする.
queue
先入後出(FIFO)
最初に入力したデータが最初に出力されるデータ構造
jsでのqueueメソッド
追加データ:
push
データ消去:shift
接続リストを使用したキューの実装
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class Queue {
constructor() {
this.top = null;
this.bottom = null;
this.length = 0;
}
push(data) {
const newNode = new Node(data);
if (this.length === 0) {
this.top = newNode;
this.bottom = newNode;
} else {
const preNode = this.top;
this.top = newNode;
preNode.next = newNode;
}
this.length++;
}
peek() {
this.length > 0 && console.log(this.top.data);
}
shift() {
if (this.length === 0) {
console.error("stack is empty");
} else {
this.bottom = this.bottom.next;
}
this.length--;
}
}
const queue = new Queue();
queue.push(1);
queue.peek();
queue.push(2);
queue.peek();
queue.push(3);
queue.peek();
queue.shift();
queue.shift();
queue.shift();
queue.shift();
queue.peek();
キュー使用率の例
キューとプロセス
CPUはプロセスを管理し、各プロセスに適切なCPUを割り当てる.
複数のプロセスで限られたメモリを効率的に使用するには、スケジューリング・テクノロジーによって選択される次の実行時に実行できるプロセスを選択する必要があります.
質問する
https://programmers.co.kr/learn/courses/30/lessons/77485
に近づく
長方形の枠線の数字を分けて保存し、一番前の数字を後ろに送り、配列に入れればいいです.
問題を解く
1.行と列に適した配列を作成する
const arr = Array.from(Array(rows), (_,i) => Array.from(Array(columns),(_,j)=>i*columns+j+1))
2.query順に長方形の枠線値をスタックに保存
const stack = [];
for(let i=y1;i<y2;i++) stack.push(arr[x1][i]);
for(let i=x1;i<x2;i++) stack.push(arr[i][y2]);
for(let i=y2;i>y1;i--) stack.push(arr[x2][i]);
for(let i=x2;i>x1;i--) stack.push(arr[i][y1]);
3.ストレージスタックの最小値を結果にプッシュ
answer.push(Math.min(...stack))
4.スタックの前の値を最後に送信
stack.unshift(stack.pop())
5.アレイ内の長方形の枠線にスタック値を順次格納する
for(let i=y1;i<y2;i++) arr[x1][i] = stack.shift();
for(let i=x1;i<x2;i++) arr[i][y2] = stack.shift();
for(let i=y2;i>y1;i--) arr[x2][i] = stack.shift();
for(let i=x2;i>x1;i--) arr[i][y1] = stack.shift();
完全なコード
function solution(rows, columns, queries) {
const answer = []
const arr = Array.from(Array(rows), (_,i) => Array.from(Array(columns),(_,j)=>i*columns+j+1))
console.log(arr)
queries.map(query=>{
const [x1,y1,x2,y2] = [query[0]-1,query[1]-1,query[2]-1,query[3]-1]
const stack = [];
for(let i=y1;i<y2;i++) stack.push(arr[x1][i]);
for(let i=x1;i<x2;i++) stack.push(arr[i][y2]);
for(let i=y2;i>y1;i--) stack.push(arr[x2][i]);
for(let i=x2;i>x1;i--) stack.push(arr[i][y1]);
answer.push(Math.min(...stack))
stack.unshift(stack.pop())
for(let i=y1;i<y2;i++) arr[x1][i] = stack.shift();
for(let i=x1;i<x2;i++) arr[i][y2] = stack.shift();
for(let i=y2;i>y1;i--) arr[x2][i] = stack.shift();
for(let i=x2;i>x1;i--) arr[i][y1] = stack.shift();
})
return answer;
}
Reference
この問題について(アルゴリズム学習1週目.スタック/キュー), 我々は、より多くの情報をここで見つけました https://velog.io/@wkahd01/알고리즘-스터디-1주차.-스택큐テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol