typedef int STDataType; //對(duì)int類型重新起個(gè)名字叫DataType

//創(chuàng)建一個(gè)棧結(jié)構(gòu)體類型
struct Stack   
{
	STDataType* a; //數(shù)據(jù)的指針
	int top;    //棧頂
	int capacity; //記錄開辟空間的最大下標(biāo)處
};

//對(duì)順序表類型struct Stack類型重新起個(gè)名字叫SL
typedef struct Stack ST;  

//當(dāng)size 和 capacity相等時(shí)要進(jìn)行擴(kuò)容處理

//初始化變量st
void StackInit(ST* ps)
{
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

//棧的銷毀
void StackDestroy(ST* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

//入棧
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//內(nèi)存滿了要擴(kuò)容
	if (ps->capacity == ps->top)
	{
		ps->capacity = ps->capacity > 0 ? ps->capacity * 2 : 2;
		STDataType* tmp = 
		(STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity);
		if (tmp == NULL)
		{
			perror("erron ");
			exit(-1);
		}
		ps->a = tmp;
	}
	//沒有滿就直接在后面入棧
	ps->a[ps->top] = x;
	ps->top++;

}

//出棧，要注意棧不能為空
void StackPop(ST* ps)
{
	assert(ps);
	//棧為空就不能再出棧了
	assert(ps->top >= 1);

	ps->top--;
}

//返回棧頂?shù)脑?
STDataType StackTop(ST* ps)
{
	assert(ps);
	//棧不能為空
	assert(ps->top >= 1);
	return ps->a[ps->top - 1];

}

//獲取棧的元素個(gè)數(shù)
int StackSize(ST* ps)
{
	assert(ps);
	assert(ps->top >= 1);
	return ps->top - 1;
}

//判斷棧是否為空
bool StackEmpty(ST* ps)
{
	return ps->top == 0;
}

typedef int QDataType;

//創(chuàng)建一個(gè)結(jié)點(diǎn)型結(jié)構(gòu)體
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;

//創(chuàng)建一個(gè)隊(duì)列
typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;

//初始化隊(duì)列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}

//隊(duì)列銷毀
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur != NULL)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = NULL;
	pq->tail = NULL;
}

//入數(shù)據(jù)有兩種情況
void QueuePush(Queue* pq,QDataType x)
{
	assert(pq);
	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newNode == NULL)
	{
		perror("erron ");
		exit(-1);
	}
	newNode->next = NULL;
	newNode->data = x;
	//1.入隊(duì)列時(shí)隊(duì)列為空狀態(tài)
	if (pq->head == NULL)
	{
		pq->head = newNode;
		pq->tail = newNode;
	}
	//2.入隊(duì)列，隊(duì)列不為空，直接在尾指針后面鏈接即可
	else
	{
		pq->tail->next = newNode;
		pq->tail = newNode;
	}
}

//出數(shù)據(jù)，類似鏈表的頭刪
void QueuePop(Queue* pq)
{
	assert(pq);
	//要保證隊(duì)列不能為空
	assert(pq->head != NULL);
	QueueNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;

	//防止野指針出現(xiàn)，當(dāng)隊(duì)列為空時(shí)要把tail指針置為空
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
}

//取隊(duì)頭數(shù)據(jù)
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	//檢驗(yàn)隊(duì)列不能為空
	assert(pq->head != NULL);
	return pq->head->data;
}

//取隊(duì)尾數(shù)據(jù)
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	//同樣要檢驗(yàn)隊(duì)列不能為空
	assert(pq->head != NULL);
	return pq->tail->data;
}

//獲取隊(duì)列元素個(gè)數(shù)
int QueueSize(Queue* pq)
{
	assert(pq);
	int count = 0;
	QueueNode* cur = pq->head;
	while (cur != NULL)
	{
		count++;
		cur = cur->next;
	}
	return count;
}

//判斷隊(duì)列是否為空
bool QueueEmpty(Queue* pq)
{
	return pq->head == NULL;
}