目录

一、栈

1.1 栈的定义和结构

1.2 栈的函数实现

1.2.1 初始化

1.2.2 入栈

1.2.3 出栈

1.2.4 获取栈顶元素

 1.2.5 栈的长度

 1.2.6 栈的完整代码

二、队列的定义和结构

2.1 队列的定义和结构

2.2 队列的函数实现

2.2.1 队列的初始化

 2.2.2 入队

2.2.3 出队 

2.2.4 获取队顶元素

2.2.5 获取队尾元素

 2.2.6 队列的长度

2.2.7 队列的完整代码

---

一、栈

1.1 栈的定义和结构

栈：一种特殊的线性表。栈中的数据元素遵守先进后出的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

1.2 栈的函数实现

1.2.1 初始化

void StackInit(ST* st)

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;
void StackInit(ST* st)
{
	assert(st);
	st->a = NULL;
	st->top = st->capacity = 0;
}

1.2.2 入栈

void StackPush(ST* st, STDataType x)

void StackPush(ST* st, STDataType x)
{
	assert(st);
	if (st->top == st->capacity)
	{
		int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;
		STDataType* tmp = (STDataType)realloc(st->a,newcapacity*sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		st->a = tmp;
		st->capacity = newcapacity;
	}
	st->a[st->top] = x;
	st->top++;
}

1.2.3 出栈

void StackPop(ST* st)

bool StackEmpty(ST* st)//判断栈是否为空
{
	assert(st);
	return st->top == 0;

}
void StackPop(ST* st)
{
	assert(st);
	assert(!StackEmpty(st));
	st->top--;
}

1.2.4 获取栈顶元素

STDataType StackTop(ST* st)

STDataType StackTop(ST* st)
{
	assert(st);
	assert(!StackEmpty(st));
	return st->a[st->top - 1];
}

 1.2.5 栈的长度

int StackSize(ST* st)

int StackSize(ST* st)
{
	assert(st);
	return st->top;
}

 1.2.6 栈的完整代码

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;
void StackInit(ST* st)
{
	assert(st);
	st->a = NULL;
	st->top = st->capacity = 0;
}
void StackPush(ST* st, STDataType x)
{
	assert(st);
	if (st->top == st->capacity)
	{
		int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;
		STDataType* tmp = (STDataType)realloc(st->a,newcapacity*sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		st->a = tmp;
		st->capacity = newcapacity;
	}
	st->a[st->top] = x;
	st->top++;
}
void StackPrint(ST* st)
{
	assert(st);
	while (st->top >0)
	{
		st->top--;
		printf("%d ", st->a[st->top]);
	}
}
bool StackEmpty(ST* st)//判断栈是否为空
{
	assert(st);
	return st->top == 0;

}
void StackPop(ST* st)
{
	assert(st);
	assert(!StackEmpty(st));
	st->top--;
}
STDataType StackTop(ST* st)
{
	assert(st);
	assert(!StackEmpty(st));
	return st->a[st->top - 1];
}
int StackSize(ST* st)
{
	assert(st);
	return st->top;
}

二、队列的定义和结构

2.1 队列的定义和结构

队列：只允许在队尾进行插入数据操作，在队头进行删除数据操作的特殊线性表。队列具有先进先出的特点

2.2 队列的函数实现

2.2.1 队列的初始化

void QInit(Queue* q)

typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;

}Qnode;
typedef struct Queue
{
	Qnode* head;
	Qnode* tail;
	int size;
}Queue;
void QInit(Queue* q)
{
	assert(q);
	q->head = q->tail = NULL;
	q->size = 0;
}

 2.2.2 入队

void QPush(Queue* q, QDataType x)

oid QPush(Queue* q, QDataType x)
{
	assert(q);
	Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
	if(newnode==NULL)
    {
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
	if (q->tail == NULL)
		q->tail = q->head = newnode;
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
	q->size++;
}

2.2.3 出队 

void QPop(Queue* q)

bool QEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
}
void QPop(Queue* q)
{
	assert(q);
	assert(!QEmpty(q));
	if (q->head->next == NULL)
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else
	{
		Qnode* del = q->head;
		q->head = q->head->next;
		free(del);
		del= NULL;
		q->size--;
	}
}

2.2.4 获取队顶元素

QDataType QFront(Queue* q)

QDataType QFront(Queue* q)
{
	assert(q);
	assert(!QEmpty(q));
	return q->head->data;
}

2.2.5 获取队尾元素

QDataType QBack(Queue* q)

QDataType QBack(Queue* q)
{
	assert(q);
	assert(!QEmpty(q));
	return q->tail->data;
}

 2.2.6 队列的长度

size_t QSize(Queue* q)

size_t QSize(Queue* q)
{
	assert(q);
	return q->size;
}

2.2.7 队列的完整代码

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;

}Qnode;
typedef struct Queue
{
	Qnode* head;
	Qnode* tail;
	int size;
}Queue;
void QInit(Queue* q)
{
	assert(q);
	q->head = q->tail = NULL;
	q->size = 0;
}
void QPrint(Queue* q)
{
	assert(q);
	Qnode* cur = q->head;
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
}
void QPush(Queue* q, QDataType x)
{
	assert(q);
	Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
	if(newnode==NULL)
    {
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
	if (q->tail == NULL)
		q->tail = q->head = newnode;
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
	q->size++;
}
bool QEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
}
void QPop(Queue* q)
{
	assert(q);
	assert(!QEmpty(q));
	if (q->head->next == NULL)
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else
	{
		Qnode* del = q->head;
		q->head = q->head->next;
		free(del);
		del= NULL;
		q->size--;
	}
}
QDataType QFront(Queue* q)
{
	assert(q);
	assert(!QEmpty(q));
	return q->head->data;
}
QDataType QBack(Queue* q)
{
	assert(q);
	assert(!QEmpty(q));
	return q->tail->data;
}
size_t QSize(Queue* q)
{
	assert(q);
	return q->size;
}