typedef int STDataType;//方便將來如果需要其他類型的數(shù)據(jù)，可以直接修改int的類型
typedef struct Stack
{
	STDataType*a;//棧底指針
	int top;//棧頂標號
	int capacity;//容量
}ST;

#include<assert.h>
#include<stdlib.h>//malloc函數(shù)頭文件
void StackInit(ST*ps)//棧初始化
{
	assert(ps);//防止傳過來的指針是空指針
	ps->a = (STDataType)malloc(sizeof(STDataType) * 4);//malloc開辟一塊空間出來，由STDataType類型進行管理
	//malloc，及后文出現(xiàn)的realloc、free函數(shù)詳情見筆者動態(tài)內存管理文章
	if (ps->a == NULL)
	{
		printf("realloc fail\n");
		exit(-1);//終止程序
	}
	ps->capacity=4;
	//這里以開辟4個數(shù)據(jù)容量大小的棧為例，你也可以寫其他數(shù)字
	//如果壓棧的時候內存不夠，可以在后面提到的壓棧函數(shù)里面進行擴容
	ps->top = 0;//剛開始棧里沒有值時，用top=0標記，后續(xù)每放入一個top++
	//關于top詳細用法請往下看1.3壓棧部分
}

#include<assert.h>//assert函數(shù)頭文件
#include<stdlib.h>//realloc函數(shù)頭文件
void StackPush(ST*ps, STDataType x)//棧頂插入數(shù)據(jù)（入棧）
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		STDataType*tmp = realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		//realloc是在原先開辟的空間上繼續(xù)往后開辟一塊空間，詳細見筆者動態(tài)內存文章
		//擴容一般擴2倍
		if (tmp == NULL)//擴容失?。ū热鐑却嬉呀?jīng)不夠你再開辟空間了）會返回空指針
		{
			printf("realloc fail\n");
			exit(-1);//終止程序
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
	ps->a[ps->top] = x;//a是一個指針，a[x]==*(a+x)
	ps->top++;
}

void StackPop(ST*ps)//棧頂刪除數(shù)據(jù)（出棧）
{
	assert(ps);
	assert(ps->top > 0);//?？樟?，調用Pop，直接中止程序報錯
	ps->top--;
}

STDataType StackTop(ST*ps)//取棧頂數(shù)據(jù)
{
	assert(ps);
	assert(ps->top > 0);//棧空了，調StackTop，直接中止程序報錯
	return ps->a[ps->top - 1];//top是棧頂元素下一個位置,top-1是棧頂元素
	//a[m]==*(a+m)
}

int StackSize(ST*ps)//棧的數(shù)據(jù)個數(shù)
{
	assert(ps);
	return ps->top;
}

int StackEmpty(ST*ps)//判斷棧是不是空
{
	assert(ps);
	return ps->top == 0;
}

typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode*next;
	QDataType data;
}QNode;//這里和單鏈表定義一樣，有需要的可以看一下筆者之前的單鏈表文章
typedef struct Queue//定義一個結構體存儲頭節(jié)點地址和尾節(jié)點地址，方便后面頭刪和尾插
{
	QNode*head;
	QNode*tail;
}Queue;

void QueueInit(Queue*pq)隊列初始化,pq是一個結構體指針
{
	assert(pq);//判斷pq是否是空指針
	pq->head  = NULL;
	pq->tail = NULL;
}

void QueuePush(Queue*pq, QDataType x)//入隊（隊尾入）
{
	assert(pq);
	QNode*newnode = (QNode*)malloc(sizeof(QNode));//開辟出一塊空間給newnode
	if (newnode == NULL)//有可能剩余內存不夠開辟空間，malloc開辟失敗會返回空指針
	{
		printf("開辟空間失敗\n");
		exit(-1);//退出程序
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)//原先隊列里沒有任何數(shù)據(jù)，頭和尾指針都指向NULL
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

    if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

void QueuePop(Queue*pq)//出隊（隊頭出）
{
	assert(pq);
	assert(pq->head);//要出隊，隊里也要有數(shù)據(jù)可以出	
	//原隊列只有1個數(shù)據(jù)
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	//原隊列有多個數(shù)據(jù)
	else
	{
		QNode*next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

QDataType QueueFront(Queue*pq)//取隊頭數(shù)據(jù)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}

QDataType QueueBack(Queue*pq)//取隊尾數(shù)據(jù)
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}

int QueueSize(Queue*pq)//隊內數(shù)據(jù)個數(shù)
{
	assert(pq);
	int size = 0;
	QNode*cur = pq->head;
	while (cur)//cur!=NULL進行循環(huán),NULL是遍歷完tail之后出現(xiàn)的
	{
		size++;
		cur = cur->next;
	}
	return size;
}

bool QueueEmpty(Queue*pq)
{
	assert(pq);
	return pq->head == NULL;
}

void QueueDestory(Queue*pq)//隊列銷毀
{
	assert(pq);
	QNode*cur = pq->head;
	while (cur)//cur!=NULL進行循環(huán),NULL是遍歷完tail之后出現(xiàn)的
	{
		QNode*next = cur->next;
		free(cur);//free是釋放指向的空間，指針還是在的
		cur = next;
	}
	pq->head = pq->tail = NULL;
}