悩んでいる人
C言語のスタックを教えて！
こういった悩みにお答えします．
本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Assembler (x64，ARM)．
- 東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
- 2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
- 最近は自然言語処理AIとイーサリアムに関する有益な情報発信に従事．
- （AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
- （スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
こういった私から学べます．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
目次
スタック
スタックとは，データを後入れ先出し（LIFO：Last In First Out）で保持するデータ構造です．
スタックには，2つの基本操作のプッシュ（push）とポップ（pop）があります．
pushは指定されたデータをスタックの先頭に追加し，既存のデータはその下にそのまま保持します．
これに対して，popはスタックの現在の先頭のデータを削除し，そのデータを返します．
スタックの利用例は以下になります．
- 関数の呼び出し前に仮引数の格納
- 関数の呼び出し後に呼び出し元のレジスタの退避や復帰
他のデータ構造を知りたいあなたはこちらからどうぞ．
C言語のスタック
C言語によるスタックのコードは以下になります．
スタックの動作がわかります．
|
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 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #define STACK_SIZE 128 struct stack { int data[STACK_SIZE]; size_t num; }; void init(struct stack *s) { size_t i; for (i = 0; i < STACK_SIZE; i++) { s->data[i] = 0; } s->num = 0; } void print(struct stack *s) { size_t i; printf("print(): "); if (s->num == 0) { printf("EMPTY"); } else { for (i = 0; i < s->num; i++) { printf("%d ", s->data[i]); } } printf("\n"); } int push(struct stack *s, int data) { if (s->num >= STACK_SIZE) { fprintf(stderr, "Error: cannot push data to stack.\n"); return 1; } s->data[s->num++] = data; return 0; } int pop(struct stack *s, int *data) { if (s->num == 0) { fprintf(stderr, "Error: cannot pop data from stack.\n"); return 1; } *data = s->data[--s->num]; return 0; } void clear(struct stack *s) { int data; while (s->num > 0) { pop(s, &data); } init(s); } int main(void) { struct stack stack; int i; int data; init(&stack); for (i = 1; i <= 5; i++) { printf("push %d\n", i); push(&stack, i); print(&stack); } for (i = 1; i <= 2; i++) { if (pop(&stack, &data) == 0) { printf("pop %d\n", data); } print(&stack); } for (i = 10; i <= 13; i++) { printf("push %d\n", i); push(&stack, i); print(&stack); } for (i = 1; i <= 3; i++) { if (pop(&stack, &data) == 0) { printf("pop %d\n", data); } print(&stack); } clear(&stack); return 0; } |
実行結果は以下になります．
スタックは後入れ先出しでデータを操作していることがわかります．
|
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 |
$ gcc stack.c $ a.out push 1 print(): 1 push 2 print(): 1 2 push 3 print(): 1 2 3 push 4 print(): 1 2 3 4 push 5 print(): 1 2 3 4 5 pop 5 print(): 1 2 3 4 pop 4 print(): 1 2 3 push 10 print(): 1 2 3 10 push 11 print(): 1 2 3 10 11 push 12 print(): 1 2 3 10 11 12 push 13 print(): 1 2 3 10 11 12 13 pop 13 print(): 1 2 3 10 11 12 pop 12 print(): 1 2 3 10 11 pop 11 print(): 1 2 3 10 |
x86-64の命令セットアーキテクチャでスタックを操作するpush/pop命令
x86-64の命令セットアーキテクチャでは，スタックのpush/pop操作を行うpush/pop命令があります．
C言語からアセンブリ言語のファイルを出力する場合，GCCでは-Sオプションを利用します．
C言語のstack.cファイルからアセンブリ言語のstack.sファイルを作成し，catコマンドでstack.sの中身を表示する方法は以下になります．
例えば，5～31行目のinit関数では，9行目にpushq命令（push命令の64ビット版），28行目にpopq命令（pop命令の64ビット版）を実行していることがわかります．
|
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 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 |
$ gcc stack.c -S $ cat stack.s .file "stack.c" .text .globl init .type init, @function init: .LFB0: .cfi_startproc endbr64 pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset 6, -16 movq %rsp, %rbp .cfi_def_cfa_register 6 movq %rdi, -24(%rbp) movq $0, -8(%rbp) jmp .L2 .L3: movq -24(%rbp), %rax movq -8(%rbp), %rdx movl $0, (%rax,%rdx,4) addq $1, -8(%rbp) .L2: cmpq $127, -8(%rbp) jbe .L3 movq -24(%rbp), %rax movq $0, 512(%rax) nop popq %rbp .cfi_def_cfa 7, 8 ret .cfi_endproc .LFE0: .size init, .-init .section .rodata .LC0: .string "print(): " .LC1: .string "EMPTY" .LC2: .string "%d " .text .globl print .type print, @function print: .LFB1: .cfi_startproc endbr64 pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset 6, -16 movq %rsp, %rbp .cfi_def_cfa_register 6 subq $32, %rsp movq %rdi, -24(%rbp) leaq .LC0(%rip), %rax movq %rax, %rdi movl $0, %eax call printf@PLT movq -24(%rbp), %rax movq 512(%rax), %rax testq %rax, %rax jne .L5 leaq .LC1(%rip), %rax movq %rax, %rdi movl $0, %eax call printf@PLT jmp .L6 .L5: movq $0, -8(%rbp) jmp .L7 .L8: movq -24(%rbp), %rax movq -8(%rbp), %rdx movl (%rax,%rdx,4), %eax movl %eax, %esi leaq .LC2(%rip), %rax movq %rax, %rdi movl $0, %eax call printf@PLT addq $1, -8(%rbp) .L7: movq -24(%rbp), %rax movq 512(%rax), %rax cmpq %rax, -8(%rbp) jb .L8 .L6: movl $10, %edi call putchar@PLT nop leave .cfi_def_cfa 7, 8 ret .cfi_endproc .LFE1: .size print, .-print .section .rodata .align 8 .LC3: .string "Error: cannot push data to stack.\n" .text .globl push .type push, @function push: .LFB2: .cfi_startproc endbr64 pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset 6, -16 movq %rsp, %rbp .cfi_def_cfa_register 6 subq $16, %rsp movq %rdi, -8(%rbp) movl %esi, -12(%rbp) movq -8(%rbp), %rax movq 512(%rax), %rax cmpq $127, %rax jbe .L10 movq stderr(%rip), %rax movq %rax, %rcx movl $34, %edx movl $1, %esi leaq .LC3(%rip), %rax movq %rax, %rdi call fwrite@PLT movl $1, %eax jmp .L11 .L10: movq -8(%rbp), %rax movq 512(%rax), %rax leaq 1(%rax), %rcx movq -8(%rbp), %rdx movq %rcx, 512(%rdx) movq -8(%rbp), %rdx movl -12(%rbp), %ecx movl %ecx, (%rdx,%rax,4) movl $0, %eax .L11: leave .cfi_def_cfa 7, 8 ret .cfi_endproc .LFE2: .size push, .-push .section .rodata .align 8 .LC4: .string "Error: cannot pop data from stack.\n" .text .globl pop .type pop, @function pop: .LFB3: .cfi_startproc endbr64 pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset 6, -16 movq %rsp, %rbp .cfi_def_cfa_register 6 subq $16, %rsp movq %rdi, -8(%rbp) movq %rsi, -16(%rbp) movq -8(%rbp), %rax movq 512(%rax), %rax testq %rax, %rax jne .L13 movq stderr(%rip), %rax movq %rax, %rcx movl $35, %edx movl $1, %esi leaq .LC4(%rip), %rax movq %rax, %rdi call fwrite@PLT movl $1, %eax jmp .L14 .L13: movq -8(%rbp), %rax movq 512(%rax), %rax leaq -1(%rax), %rdx movq -8(%rbp), %rax movq %rdx, 512(%rax) movq -8(%rbp), %rax movq 512(%rax), %rdx movq -8(%rbp), %rax movl (%rax,%rdx,4), %edx movq -16(%rbp), %rax movl %edx, (%rax) movl $0, %eax .L14: leave .cfi_def_cfa 7, 8 ret .cfi_endproc .LFE3: .size pop, .-pop .globl clear .type clear, @function clear: .LFB4: .cfi_startproc endbr64 pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset 6, -16 movq %rsp, %rbp .cfi_def_cfa_register 6 subq $32, %rsp movq %rdi, -24(%rbp) movq %fs:40, %rax movq %rax, -8(%rbp) xorl %eax, %eax jmp .L16 .L17: leaq -12(%rbp), %rdx movq -24(%rbp), %rax movq %rdx, %rsi movq %rax, %rdi call pop .L16: movq -24(%rbp), %rax movq 512(%rax), %rax testq %rax, %rax jne .L17 movq -24(%rbp), %rax movq %rax, %rdi call init nop movq -8(%rbp), %rax subq %fs:40, %rax je .L18 call __stack_chk_fail@PLT .L18: leave .cfi_def_cfa 7, 8 ret .cfi_endproc .LFE4: .size clear, .-clear .section .rodata .LC5: .string "push %d\n" .LC6: .string "pop %d\n" .text .globl main .type main, @function main: .LFB5: .cfi_startproc endbr64 pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset 6, -16 movq %rsp, %rbp .cfi_def_cfa_register 6 subq $544, %rsp movq %fs:40, %rax movq %rax, -8(%rbp) xorl %eax, %eax leaq -528(%rbp), %rax movq %rax, %rdi call init movl $1, -532(%rbp) jmp .L20 .L21: movl -532(%rbp), %eax movl %eax, %esi leaq .LC5(%rip), %rax movq %rax, %rdi movl $0, %eax call printf@PLT movl -532(%rbp), %edx leaq -528(%rbp), %rax movl %edx, %esi movq %rax, %rdi call push leaq -528(%rbp), %rax movq %rax, %rdi call print addl $1, -532(%rbp) .L20: cmpl $5, -532(%rbp) jle .L21 movl $1, -532(%rbp) jmp .L22 .L24: leaq -536(%rbp), %rdx leaq -528(%rbp), %rax movq %rdx, %rsi movq %rax, %rdi call pop testl %eax, %eax jne .L23 movl -536(%rbp), %eax movl %eax, %esi leaq .LC6(%rip), %rax movq %rax, %rdi movl $0, %eax call printf@PLT .L23: leaq -528(%rbp), %rax movq %rax, %rdi call print addl $1, -532(%rbp) .L22: cmpl $2, -532(%rbp) jle .L24 movl $10, -532(%rbp) jmp .L25 .L26: movl -532(%rbp), %eax movl %eax, %esi leaq .LC5(%rip), %rax movq %rax, %rdi movl $0, %eax call printf@PLT movl -532(%rbp), %edx leaq -528(%rbp), %rax movl %edx, %esi movq %rax, %rdi call push leaq -528(%rbp), %rax movq %rax, %rdi call print addl $1, -532(%rbp) .L25: cmpl $13, -532(%rbp) jle .L26 movl $1, -532(%rbp) jmp .L27 .L29: leaq -536(%rbp), %rdx leaq -528(%rbp), %rax movq %rdx, %rsi movq %rax, %rdi call pop testl %eax, %eax jne .L28 movl -536(%rbp), %eax movl %eax, %esi leaq .LC6(%rip), %rax movq %rax, %rdi movl $0, %eax call printf@PLT .L28: leaq -528(%rbp), %rax movq %rax, %rdi call print addl $1, -532(%rbp) .L27: cmpl $3, -532(%rbp) jle .L29 leaq -528(%rbp), %rax movq %rax, %rdi call clear movl $0, %eax movq -8(%rbp), %rdx subq %fs:40, %rdx je .L31 call __stack_chk_fail@PLT .L31: leave .cfi_def_cfa 7, 8 ret .cfi_endproc .LFE5: .size main, .-main .ident "GCC: (Ubuntu 11.2.0-19ubuntu1) 11.2.0" .section .note.GNU-stack,"",@progbits .section .note.gnu.property,"a" .align 8 .long 1f - 0f .long 4f - 1f .long 5 0: .string "GNU" 1: .align 8 .long 0xc0000002 .long 3f - 2f 2: .long 0x3 3: .align 8 4: |
まとめ
C言語のスタックを紹介しました．
具体的には，C言語のスタックと，x86-64のアセンブリ言語におけるpush/pop命令の実例を解説しました．
スタックは，主に関数の呼び出しの時に利用されるので覚えておきましょう！
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
