データ構造の復習がてらに、スタックを実装してみます。
スタックのC言語のサンプルコード
スタックをint型の配列で定義し、スタックの位置をtail変数で管理します。
初期化時のtail変数は-1としました。
push関数、pop関数を実装しています。
push,pop毎にスタックの中身がわかるように、printStack関数を実装して、pushとpop時に呼び出しています。
$ cat stack.c
#include <stdio.h>
#define SIZE 3
typedef struct{
int data[SIZE];
int tail;
}stack_t;
//スタックの中身をprint出力
void printStack(stack_t* pStack){
int i;
for(i = 0; i <= SIZE - 1; i++){
printf("%d ", pStack->data[i]);
}
printf("\n");
}
//スタックの初期化
void initStack(stack_t* pStack){
int i;
for(i = 0; i <= SIZE - 1; i++){
pStack->data[i] = 0;
}
pStack->tail = -1;
printStack(pStack);
}
//push関数
void push(stack_t* pStack, int value){
if(pStack->tail >= SIZE - 1){
printf("Full\n");
}else{
pStack->tail++;
pStack->data[pStack->tail] = value;
}
printStack(pStack);
}
//pop関数
void pop(stack_t* pStack){
if(pStack->tail <= -1){
printf("Empty\n");
}else{
pStack->data[pStack->tail] = 0;
pStack->tail--;
}
printStack(pStack);
}
int main(){
stack_t stack;
stack_t* pStack = &stack;
initStack(pStack);
pop(pStack);
push(pStack, 1);
push(pStack, 2);
push(pStack, 3);
push(pStack, 4);
pop(pStack);
pop(pStack);
pop(pStack);
pop(pStack);
push(pStack, 1);
push(pStack, 2);
push(pStack, 3);
push(pStack, 4);
return 0;
}
下記のコードについて、いくつかご質問を頂いていたので、
この場で回答させて頂きます。
stack_t stack;
stack_t* pStack = &stack;
stack_t* pStack の部分はあくまでも、ポインタを宣言しているだけです。
このポインタの先を参照しても実体がありません。
そこで、stack_t stack;で実体を宣言して、stack_t* pStack = &stack; とすることで、実体のあるデータ領域の先頭アドレスがポインタに格納されます。
&stackはstack変数のメモリ領域の先頭アドレスを返します。
c言語はポインタの扱いが慣れないと難しいですよね。
ご質問頂きありがとうございました。
それでは、下記が、実行結果になります。
スタックのサイズを３としているので、４つ目をpushするとFullとなっています。
また、スタックが空になると、popをしてもEmptyとなっているのが確認できます。
$ gcc stack.c -o stack $ ./stack 0 0 0 Empty 0 0 0 1 0 0 1 2 0 1 2 3 Full 1 2 3 1 2 0 1 0 0 0 0 0 Empty 0 0 0 1 0 0 1 2 0 1 2 3 Full 1 2 3
スタックのPythonのサンプルコード
Pythonでも同じように実装してみます。
スタッククラスを定義して、pushとpopのメソッドを定義しています。
$ cat stack.py
#!/usr/bin/env python3
# coding: UTF-8
class stack:
#スタックの初期化
def __init__(self, size):
self.size = size
#スタックの中身を0埋め
self.data = [0] * size
#初期化時は空なのでtailは-1とする
self.tail = -1
print(self.data)
#push関数
def push(self, value):
#スタックがFullの処理
if self.tail >= self.size - 1:
print("Full")
#スタックがFullでなければ、push操作
else:
self.tail += 1
self.data[self.tail] = value
print(self.data)
#pop関数
def pop(self):
#スタックがEmptyの処理
if self.tail <= -1:
print("Empty")
#スタックがEmptyでなければ、pop操作
else:
self.data[self.tail] = 0
self.tail -=1
print(self.data)
def __del__(self):
del self.size
if __name__ == '__main__':
data = stack(size = 3)
data.pop()
data.push(1)
data.push(2)
data.push(3)
data.push(4)
data.pop()
data.pop()
data.pop()
data.pop()
del data
下記が実行結果になります。
C言語の実装と動きは同じです。
$ ./stack.py [0, 0, 0] Empty [0, 0, 0] [1, 0, 0] [1, 2, 0] [1, 2, 3] Full [1, 2, 3] [1, 2, 0] [1, 0, 0] [0, 0, 0] Empty [0, 0, 0]
