简单数据结构。队列，栈，链表

序

简单的数据结构往往是简单的，当然不仅仅是代码，它也是容易理解的。但往往不代表他们不能够被使用。它们的用处实际上非常巨大。

栈（stack）

一个数组，我们想象他是一个桶，我们可以将物体一个一个摞在里面。如果我们拿走其中的一个，只能拿走最上面的。我们记录桶中一共有top个元素，第top个元素就是最上面的元素。

删除

当我们想拿走最上面的元素我们只需要让top减一，上面的元素就不用管了。

void del()
{
	--top;//top减1
}

放入

当我们要在最上面放一个元素时，只需要让top加一，然后让第top个元素被赋值为新元素的值。

void ins(int a)//插入值为a的元素
{
	top=top+1;
	st[top]=a;
}

或者

void ins(int a)
{
	st[++top]=a;
}

查找

栈中只能查找堆顶，就是数组中第top个元素。

int fin()
{
	return st[top];//返回栈顶
}

队列（queue）

现在我们的数组不再是一个桶，而是一个管子，我们一个一个往上摞东西，我们可以从上面取走最后一个东西，也可以从下面取走第一个东西。最后一个东西在数组中的位置定义为tail，第一个定义为head。

删除队头

即删除第一个元素，我们用与栈类似的方法 ，只需要让head加一。

void delfirst()//删除队列中第一个元素
{
	++head;
}

放入队尾

即在队列最后放一个元素，我们只需要让tail加一，然后将第tail个元素赋值。

void inslast(int a)//插入值为a的元素
{
	tail=tail+1;
	que[tail]=a;
}

或

void inslast(int a)
{
	que[++tail]=a;
}

其他操作

其他操作实际是类似的，包括查找第一个元素，查找最后一个元素，在队头放一个元素，在队尾删除一个元素。其实栈就是队列的简化版。

void dellast()//删除队尾的一个元素
{
	--tail;
}
void insfirst(int a)//在队头放入一个值为a的元素
{
	que[--head]=a;
}//当然也可以这么写
/*
void insfirst(int a)
{
	head=head-1;
	que[head]=a;
}
*/
int finfirst()//查找队头的元素
{
	return que[head];
}
int inslast()//查找队尾的元素
{
	return que[tail];
}

通常我们只在队头删除在队尾放入，我们称这种队列为单项队列。如果我们两边即放入又删除，我们称此为双向队列。

链表

我们存一个一个数组表示标号为i的元素下一个元素是什么，再记录最后一个元素的标号，和第一个元素的标号。完了就这样。

单调队列

意思就是保证你最后加入元素在队列里，而且队列里的元素时单调的。
比如我们要求队列单调递减。
其实非常简单，我们加入值为a的元素的时候先把队列中比a小的都删掉，然后再加入。

void insert(int a)//加入一个值为a的元素
{
	while((head<=tail)&&(que[tail]<a)) --tail;//因为队列递减，所以比a小的元素时队列最后的一部分
	que[++tail]=a;
}