data-structures
スタック
サーチ…
スタックイントロ
スタックはLIFO（ラスト・イン・ファースト・アウト）のデータ構造です。つまり、スタックに追加された最新の（または最後の）要素が最初に削除された要素です。
ボックス内の本の例を考えてみましょう。一度に1つのブックのみをボックスから追加または削除することができます。また、追加または削除することができます。
今、最初の2冊の本の箱は次のようになります：
|--------| | book 2 | ◀──── top of box |--------| | book 1 | ◀──── bottom of box |--------|
本3を追加すると、それが一番上に表示されます。書籍3の前に追加された残りの書籍は、その下に残ります。
|--------| | book 3 | ◀──── top of box |--------| | book 2 | |--------| | book 1 | ◀──── bottom of box |--------|
ボックスはスタックのようで、ブックはデータ要素です。ボックスに本を追加することはプッシュ操作であり、ボックスの上部からブックを削除/取得することはポップ操作である。ポップ操作を実行すると、ブック3が表示され、ブック3をプッシュする前の状態に戻ります。つまり、最後に挿入した要素（または最新の要素）が最初の要素です出た（LIFO）。本1を入手するには、2つのポップをもう1つ実行する必要があります.1つは本2を削除し、もう1つは本1を取得することです。
配列を使用したスタックの実装。このためには、最上位の場所（tos）を指すインデックスが必要です。要素がスタックにプッシュされるたびに、tosは1ずつインクリメントされ、pop操作が実行されるたびに、スタックの先頭を指すインデックス（tos）が1だけデクリメントされます。
押す：
PUSH操作の前
tos
|
|
|-----|-----|-----|-----|-----|
| i1 | i2 | i3 | i4 | |
|-----|-----|-----|-----|-----|
void push(dataElment item){
stack[top]=item; //item = i4
top++;
}
プッシュ操作の後スタックにはスタックの先頭へのポインタがあります。プッシュ操作が呼び出されるたびに、値が一番上に置かれ、値が更新されます。
tos -- Top of the stack
tos
|
|
|-----|-----|-----|-----|
| i1 | i2 | i3 | |
|-----|-----|-----|-----|
POP： pop操作はスタックの先頭からコンテンツを削除し、tosの値を1ずつ減らして更新します
ポップアップ操作の前に：
tos
|
|
|-----|-----|-----|-----|-----|
| i1 | i2 | i3 | i4 | |
|-----|-----|-----|-----|-----|
dataElment pop(){
dataElment value = stack[tos--];
return value;
}
ポップアップ操作の後：
tos
|
|
|-----|-----|-----|-----|
| i1 | i2 | i3 | i4 |
|-----|-----|-----|-----|
When a push operation is performed it overwrites i4.
スタックを使用してパリンドロームを見つける
回文は「カヤック」のように両方の方法で読むことができる単語です。
この例では、特定の単語がPython3を使用して回文であるかどうかを調べる方法を示します。
まず、文字列をスタックに変換する必要があります（スタックをスタックとして使用します）。
str = "string"
stk = [c for c in str] #this makes an array: ["s", "t", "r", "i", "n", "g"]
stk.append("s") #adds a letter to the array
stk.pop() #pops the last element
今、私たちはその言葉を逆転させなければなりません。
def invert(str):
stk = [c for c in str]
stk2 = []
while len(stk) > 0:
stk2.append(stk.pop())
#now, let's turn stk2 into a string
str2 = ""
for c in stk2:
str2 += c
return str2
今、単語とその逆の形を比較することができます。
def palindrome(str):
return str == invert(str)
配列とリンクリストを使用したスタック実装
配列の実装
#include<stdio.h>
#define MAX 100000 //Global variables
int top = -1;
int a[MAX];
void push(int x){
if(top == MAX-1){ // Check whether stack is full
printf("Stack Overflow\n");
return;
}
a[++top] = x; // Otherwise increment top and insert x
}
void pop(){
if(top == -1){ // if top = -1, empty stack
printf("Empty stack\n");
return;
}
top--;
}
void print(){ //printing stack values
for(int i=0;i <= top;i++){
printf("%d ",a[i]);
}
printf("\n");
}
void topValue(){ // Method can print the top value of a stack
printf("%d",a[top]);
}
int main(){
push(5);
push(20);
push(15);
print();
pop();
print();
push(35);
print();
topValue();
}
リンクリストの実装
#include<stdio.h>
#include<malloc.h>
struct node{
int data;
node* link;
};
node* top = NULL;
void push(int data){
node* temp = (struct node*)malloc(sizeof(struct node*));
temp->data = data;
temp->link = top;
top = temp;
}
void pop(){
if(top == NULL) return;
node* temp = top;
top = top->link;
free(temp);
}
void print(){
node* t = top;
while(t != NULL){
printf("%d ",t->data);
t=t->link;
}
printf("\n");
}
void topValue(){
printf("%d ",top->data);
}
int main(){
push(5);
push(20);
push(15);
print();
pop();
print();
push(35);
print();
topValue();
}
バランスの取れたかっこのチェック
括弧は、 ( 、 ) 、 { 、 } 、 [ 、または]いずれかの文字と見なされます。
2つの角かっこは、まったく同じ型の開き角括弧（すなわち、 ( 、 [ 、 { ）が閉じ括弧（すなわち) 、 ] 、または}の左に現れた場合）、一致したペアとみなされます。角括弧には、 [] 、 {} 、 () 3つのタイプがあります。
一致する括弧のペアは、それが囲む括弧のセットが一致しない場合、釣り合わない。例えば、 {[(])}の間でコンテンツがのでバランスされていない{と}バランスありません。角括弧の対は、単一の、不平衡開口ブラケットを包囲( 、および括弧の対は、単一の、不平衡閉鎖四角ブラケットを包囲します] 。
この論理によって、次の条件が満たされている場合、一連の括弧が平衡しているとみなされます。
それには匹敵しない括弧は含まれていません。
一致した括弧の範囲内に囲まれた括弧のサブセットも、一致した括弧のペアです。
アルゴリズム：
- （たとえば、スタックを宣言
stack）。 - 文字列入力をトラバースします。
- 現在の文字が開始ブラケット（すなわち、ある場合A）
(又は{または[）、スタックにプッシュ。 - B）現在の文字が閉じ括弧の場合（すなわち、
)または}または]）をスタックからポップします。ポップされた文字が一致する開始括弧であれば、else else括弧はnot balanced。 - c）現在の文字が閉じ括弧（すなわち
)または}または]あり、スタックが空の場合、かっこはnot balancedてnot balanced。
- スタックに残っていくつかの開始ブラケットがある場合は、完全横断した後、その文字列がある
not balanced私たちが持っている他のbalanced文字列を。