数据结构06-栈

栈和队列是两种我们应用非常广的数据机构，这两个都是线性表的一种，今天我们主要来谈谈栈。
栈的主要代码：

#include
using namespace std;
#define MaxSize 10

//初始化，压栈，入栈
typedef struct Stack {
	int top;
	int data[MaxSize];
}Stack;

Stack* Stack_Init()
{
	Stack* temp = new Stack;
	if (!temp)
	{
		cout << "申请内存失败" << endl;
		return NULL;
	}
	temp->top = -1;
	return temp;
}

void PrintStack(Stack* temp)
{
	int index = temp->top;
	while (index>= 0)
	{
		cout << temp->data[index] << " ";
		index--;
	}
	cout << endl;
}

void push(Stack* temp,int data)
{
	if (temp->top + 1 == MaxSize)
	{
		cout << "栈满" << endl;
		return;
	}
	temp->data[++temp->top] = data;
}

int pop(Stack* temp)
{
	if (temp->top < 0)
	{
		cout << "栈空" << endl;
		return -1;
	}
	temp->top--;
	return temp->data[temp->top + 1];
}

void Stacktest()
{
	Stack* temp = Stack_Init();
	push(temp, 10);
	push(temp, 11);
	push(temp, 12);
	push(temp, 13);
	push(temp, 14);
	PrintStack(temp);
	pop(temp);
	pop(temp);
	PrintStack(temp);
}
int main()
{
	Stacktest();
	return 0;
}

我们知道，栈是一种先进后出（FILO）的数据结构，如此以来，我们的操作只涉及到栈顶元素，所以我们需要一个指向栈顶元素的指针——top（这里我们使用的数组下标）。正因为我们只涉及到栈顶元素，所以栈的操作只有两个：压栈和出栈。压栈——顾名思义，就是把元素压入栈中（栈中空间足够的情况下）。所以我们只需要将新数据记录到栈中，并且将指向栈顶元素的指针指向新纳入的元素即可。至于出栈，由于我的栈是由数组作为基本元素构造而成的，所以此时我们只需要将top指针往下移动一位就可以了，如果是指针实现的，还需要释放之前的栈顶元素。