数据结构（C语言实现）-栈和队列

栈

栈是一种先入后出的线性表，数据只能在表尾进行插入和删除。栈的表尾称为栈顶，表头称为栈底。

栈这种数据结构可以类比弹夹，子弹一个一个压入弹夹中，最后压入的子弹最先被发射出去，装弹和退弹都只能从弹夹顶部自上而下进行。

栈是一种特殊的线性表，栈的操作也只是线性表操作的特例，故他们的实现具有相似性。这里只实现栈的顺序表示。

#include"head.h"

#define STACK_INIT_SIZE 100  // 栈初始容量（可存储数据个数）
#define STACK_INCREMENT 10  // 栈的分配增量

typedef int Elemtype;

typedef struct{
	Elemtype *base;  // base是栈基址（同时为栈底指针），它始终指向栈底元素
	Elemtype *top;  // top是栈顶指针，初始指向base，每压入一个元素，top+1
	int stacksize;  // 当前已分配存储空间（可存储元素个数）
}SqStack;


//初始化，创建一个空栈
int InitStack(SqStack &S)
{
	S.base = (Elemtype *)malloc(STACK_INIT_SIZE*sizeof(Elemtype));
	if(!S.base)  exit(OVERFLOW);  // 若空间分配失败
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
	return OK;
}


// 获取栈顶元素，用变量e返回
int GetTop(SqStack &S,Elemtype *e)
{
	if(S.top == S.base)  return ERROR;
	*e = *(S.top - 1)；
	return OK;
}


//入栈（压栈）
int Push(SqStack &S,Elemtype e)
{
	if(S.top-S.base  >= S.stacksize)  // 栈满，需要追加存储空间
	{
		S.base = (Elemtype *)realloc(S.base , (S.stacksize + STACK_INCREMENT )*sizeof(Elemtype))
		if(!S.base)  exit(OVERFLOW);  // 如果分配失败
		S.top = S.base + S.stacksize;
		S.stacksize += STACK_INCREMERNT;
	}
	*(S.top++) = e;
	return OK;
}


//出栈（弹栈）,将元素装入变量e
int Pop(SqStack &S,Elemtype &e)
{
	if(S.top == S.base)  return ERROR;
	e = *(--S.top);
	return OK;
}

队列

队列是一种先进先出的线性表，新加入的数据只能排在队尾，需要删除数据则只能从队头开始删。

队列这种数据结构好比 在超市里排队结账，后来的人只能排在队尾，想要离开只能等前面的人都走了，自己排到队头。

队列的链式表示称为链队列，队列的顺序表示称为循环队列。链队列较易实现，这里只实现循环队列。
队列的顺序表示中，当队尾占据数组最后的位置，而队头以前又因为出队存在空闲空间时，会出现无法入队却又有空闲空间的现象，此时进行数组再分配，扩大存储空间是不合理的。
处理方法就是把数组想象成环形，当队尾在数组中的位置（下标）比队头在数组中的位置小1时，认为存储空间已满。这也是循环队列名称由来。

由队列（只能在头出尾入）的特性可知，无法通过动态分配空间实现循环队列，故使用循环队列时，必须知道最大队列长度，分配后无法通过再分配更改。

#include"head.h"
#define MAXSIZE 10
typedef char Elemtype;

typedef struct{
	Elemtype *base;  // 数组基址
	int front;  // 用来标记队头元素的下标
	int rear;  // 用来标记队尾元素的下一个位置
}SqQueue;


//初始化队列
int InitQueue(SqQueue &q)
{
	Q.base = (Elemtype *)malloc(MAXSIZE * sizeof(Elemtype));
	if(!Q.base)  exit(OVERFLOW);
	Q.front = Q.rear = 0;  // 初始时，队头队尾指针均指向数组0号位置
	return OK;
}


//元素入队
int EnQueue(SqQueue &Q , Elemtype e)
{
	if((Q.rear + 1) % MAXSIZE ==Q.front)  return ERROR;  // 队列满
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear +1) % MAXSIZE;
	return OK;
}


//元素出队,装入变量e
int DeQueue(SqQueue &Q，Elemtype *e)
{
	if(Q.front == Q.rear)  return ERROR;
	*e = Q.base[Q.front];
	Q.front = (Q.front +1) % MAXSIZE;
	return OK;
}