カクビンに従ってデータ構造を学ぶ(05)——スタック

まず、スタックとスタックの違いが分かります.

# include <stdio.h>
# include <malloc.h>


void f(int k)
{
	int m;


	double * q = (double *)malloc(200);
}


int main(void)
{
	int i = 10;
	int * p = (int *)malloc(100);


	return 0;
}

以上のプログラムでは、m、q、i、pはスタックに割り当てられたメモリで保存され、動的に割り当てられた200と100とバイトはヒープに割り当てられたメモリで保存されます.
スタックとスタックの主な違いは、メモリの割り当て方式が違って、スタックはスタックの方式によってメモリを割り当てて、先進的な後出のデータ構造を実現することです.ヒープはヒープ順序という方法でメモリを割り当てます.
スタックは、静的なスタック「カーネルは配列で保存されている」と動的なスタック「カーネルはチェーンで保存されている」に分けられます.

# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>

typedef struct Node
{
	int data;
	struct Node * pNext;
}NODE, * PNODE;

typedef struct Stack
{
	PNODE pTop;
	PNODE pBottom;
}STACK, * PSTACK;  //PSTACK     struct STACK *

void init(PSTACK);
void push(PSTACK, int );
void traverse(PSTACK);
bool pop(PSTACK, int *);
void clear(PSTACK pS);

int main(void)
{
	STACK S;  //STACK     struct Stack
	int val;

	init(&S);  //         
	push(&S, 1); //  
	push(&S, 2);
	push(&S, 3);
	push(&S, 4);
	push(&S, 5);
	push(&S, 6);
	traverse(&S); //    
	
	clear(&S);
	//traverse(&S); //    

	if ( pop(&S, &val) )
	{
		printf("    ，      %d
", val);
	}
	else
	{
		printf("    !
");
	}

	traverse(&S); //    

	return 0;
}

void init(PSTACK pS)
{
	pS->pTop = (PNODE)malloc(sizeof(NODE));
	if (NULL == pS->pTop)
	{
		printf("        !
");
		exit(-1);
	}
	else
	{
		pS->pBottom = pS->pTop;
		pS->pTop->pNext = NULL; //pS->pBottom->pNext = NULL;
	}
}

void push(PSTACK pS, int val)
{
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	
	pNew->data = val;
	pNew->pNext = pS->pTop; //pS->Top    pS->Bottom
	pS->pTop = pNew;

	return;
}

void traverse(PSTACK pS)
{
	PNODE p = pS->pTop;

	while (p != pS->pBottom)
	{
		printf("%d  ", p->data);
		p = p->pNext;
	}
	printf("
");

	return;
}

bool empty(PSTACK pS)
{
	if (pS->pTop == pS->pBottom)
		return true;
	else
		return false;
}

// pS         ，         pVal         ，      ，  false,    true
bool pop(PSTACK pS, int * pVal)
{
	if ( empty(pS) ) //pS       S   
	{
		return false;
	}
	else
	{
		PNODE r = pS->pTop;
		*pVal = r->data;
		pS->pTop = r->pNext;
		free(r);
		r = NULL;

		return true;
	}
}

//clear  
void clear(PSTACK pS)
{
	if (empty(pS))
	{
		return;
	}
	else
	{
		PNODE p = pS->pTop;
		PNODE q = NULL;

		while (p != pS->pBottom)
		{
			q = p->pNext;
			free(p);
			p = q;
		}
		pS->pTop = pS->pBottom;
	}
}

スタックのアプリケーション:関数呼び出し、中断、表現の求め、メモリ割り当て、バッファ処理、ダンジョン