(8) Sequence stack and chain stack

Order of the stack

Sequential stack refers to the stack realized by sequential storage structure , That is, a group of storage units with continuous addresses are used to store the data elements from the bottom of the stack to the top of the stack in turn , At the same time, there is a pointer top Indicates the position of the top element of the stack in the sequential stack ; Set another pointer base Indicates the position of the element at the bottom of the stack in the sequential stack . When top and base When the values of are equal , Empty stack .

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

#define MAXSIZE 20

typedef struct {
	int nData[MAXSIZE];
	int nTop;
}RkStack;

// Initialization stack 
bool InitStack(RkStack * Stack)
{
	Stack->nTop = -1;
	return true;
}

// Clean stack 
bool ClearStack(RkStack * Stack)
{
	Stack->nTop = -1;
	return true;
}

//  Judge whether the stack is empty 
bool StackEmpty(RkStack Stack)
{
	if (Stack.nTop == -1)
	{
		return true;
	}
	else
	{
		return false;
	}
}

// Or the length of the stack 
int StackLength(RkStack Stack)
{
	return Stack.nTop + 1;
}

// To the top of the stack 
int GetTop(RkStack Stack, int * nData)
{
	if (Stack.nTop == -1)
	{
		return false;
	}
	else
	{
		*nData = Stack.nData[Stack.nTop]; 
	}
}

//push
bool push(RkStack * Stack, int nData)
{
	if (Stack->nTop == MAXSIZE - 1)
	{
		return false;
	}
	else
	{
		Stack->nTop++;
		Stack->nData[Stack->nTop] = nData;
		return true;
	}
}
//pop
bool pop(RkStack * Stack, int *nData)
{
	if (Stack->nTop == -1)
	{
		return false;
	}
	else
	{
		*nData = Stack->nData[Stack->nTop];
		Stack->nTop--;
		return true;
	}
}

// Print data 
bool ShowStack(RkStack Stack)
{
	if (Stack.nTop == -1)
	{
		return false;
	}
	for (size_t i = 0; i < Stack.nTop; i++)
	{
		printf("Stack value = %d\n", Stack.nData[i]);
	}
	return true;
}
int main()
{
	RkStack rkStack;
	InitStack(&rkStack);
	for (size_t i = 0; i < 10; i++)
	{
		push(&rkStack, i);
	}
	ShowStack(rkStack);
	int nData = 0;
	pop(&rkStack, &nData);
	printf("pop value = %d\n", nData);
	//ShowStack(rkStack);
	GetTop(rkStack, &nData);
	printf("GetTop = %d\n", nData);
	int Size = StackLength(rkStack);
	printf("StackLength = %d\n", Size);
	ClearStack(&rkStack);
	bool nFlag = StackEmpty(rkStack);
	if (nFlag)
	{
		printf("Empty\n");
	}
	system("pause");
	return 0;
}

Chain stack

Chain stack refers to the stack realized by chain storage structure , Usually, the chain stack is represented by a single chain list .
No special requirements , Sequence stack is more practical than chain stack .

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


typedef struct _StackNode
{
	int nData;
	struct _StackNode *next;
}StackNode,*PStackNdoe;

typedef struct RkStack {
	PStackNdoe top;
	int count;
};

// Initialization stack 
bool InitStack(struct RkStack * Stack)
{
	Stack->top = (PStackNdoe)malloc(sizeof(StackNode));
	if (!Stack->top)
	{
		return false;
	}
	Stack->top = NULL;
	Stack->count = 0;
	return true;
}

// Clean stack 
bool ClearStack(struct RkStack * Stack)
{
	PStackNdoe TempNode1;
	PStackNdoe TempNode2;
	TempNode1 = Stack->top;
	while (TempNode1)
	{
		TempNode2 = TempNode1;
		TempNode1 = TempNode1->next;
		free(TempNode2);
	}
	Stack->count = 0;
}

//  Judge whether the stack is empty 
bool StackEmpty(struct RkStack Stack)
{
	if (Stack.count == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

// Or the length of the stack 
int StackLength(struct RkStack Stack)
{
	return Stack.count;
}

// To the top of the stack 
int GetTop(struct RkStack Stack, int * nData)
{
	if (Stack.top == NULL)
	{
		return false;
	}
	else
	{
		*nData = Stack.top->nData;
		return true;
	}
}

//push
bool push(struct RkStack * Stack, int nData)
{
	PStackNdoe mStackNode = (PStackNdoe)malloc(sizeof(StackNode));
	mStackNode->nData = nData;
	mStackNode->next = Stack->top;
	Stack->top = mStackNode;
	Stack->count++;
	return true;
}
//pop
bool pop(struct RkStack * Stack, int *nData)
{
	PStackNdoe mStackNode;
	if (StackEmpty(*Stack))
	{
		return false;
	}
	else
	{
		*nData = Stack->top->nData;
		mStackNode = Stack->top;
		Stack->top = Stack->top->next;
		free(mStackNode);
		Stack->count--;
		return true;
	}
}

// Print data 
bool ShowStack(struct RkStack Stack)
{
	PStackNdoe mStackNode;
	mStackNode = Stack.top;
	while (mStackNode)
	{
		printf("value = %d\n", mStackNode->nData);
		mStackNode = mStackNode->next;
	}
	return true;
}
int main()
{
	struct RkStack rkStack;
	int nData;
	InitStack(&rkStack);
	for (size_t i = 0; i < 10; i++)
	{
		push(&rkStack, i);
	}
	ShowStack(rkStack);

	pop(&rkStack, &nData);
	printf("pop value = %d\n", nData);
	ShowStack(rkStack);

	GetTop(rkStack, &nData);
	printf("Get top value = %d\n", nData);

	ClearStack(&rkStack);
	if (StackEmpty(rkStack))
	{
		printf("Empty!\n");
	}
	system("pause");
	return 0;
}

difference

The difference between sequence stack and chain stack is as follows ：

1. The storage structure is different , The sequence stack is statically allocated , The chain stack is dynamically allocated , Chain stack can use a lot of fragmented space , Variable capacity , Save a space , The sequence stack fixes the memory space , The capacity doesn't change .
2. In terms of use , Fast sequence stack query , Chain stack add delete data faster .