データ構造の復習がてらに、スタックを実装してみます。

スポンサーリンク

スタックの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]

スポンサーリンク