栈和队列

• 栈
• • 栈的概念
  • 栈的实现
  • • 结构体的创建
    • 初始化
    • 打印
    • 销毁
    • 入栈
    • 出栈
    • 获取栈顶数据
    • 获取栈的元素个数
    • 检查栈是否为空
• 队列
• • 队列的概念
  • 队列的实现
  • • 结构体的创建
    • 初始化
    • 队尾入数据
    • 队头删数据
    • 获取队列的有效元素
    • 打印
    • 获取队尾元素
    • 获取队头元素
    • 判断是否为空
    • 销毁

栈

栈的概念

栈：一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵循后进先出的原则（Last In First Out）
压栈：栈的插入操作叫做进栈/压栈/入栈，在栈顶入数据。
出栈：栈的删除操作叫做出栈，出数据也在栈顶。

出数据是把栈顶的元素去掉

栈的实现

结构体的创建

typedef int	STDataType;

typedef struct Stack
{
	STDataType* data;
	int top;			//栈顶	
	int capacity;		//容量
}Stack;

初始化

void StackInit(Stack* s)
{
	assert(s);
	s->data = NULL;
	s->capacity = s->top = 0;
}

打印

void StackPrint(Stack* s)
{
	assert(s);
	int i = 0;
	for (; i < s->top; i++)
	{
		printf("%d->", s->data[i]);
	}
	printf("NULL\n");
}

销毁

void StackDestroy(Stack* s)
{
	assert(s);
	free(s->data);
	s->data = NULL;
	s->capacity = s->top = 0;
}

入栈

void StackPush(Stack* s, STDataType x)
{
	assert(s);

	if (s->capacity == s->top)
	{
		STDataType NewCapacity = s->capacity == 0 ? 4 : s->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(s->data, sizeof(STDataType) * NewCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		s->data = tmp;
		free(tmp);
		s->data[(s->top)++] = x;
		s->capacity = NewCapacity;
	}
	else
	{
		s->data[(s->top)++] = x;
	}
}

出栈

void StackPop(Stack* s)
{
	assert(s);
	assert(s->top > 0);

	s->top--;
}

获取栈顶数据

STDataType StackTop(Stack* s)
{
	assert(s);
	assert(s->top > 0);
	return s->data[s->top-1];
}

获取栈的元素个数

int StackSize(Stack* s)
{
	assert(s);

	return s->top;
}

检查栈是否为空

//.c文件，要引用#include <stdbool.h>这个头文件
bool StackEmpty(Stack* s)
{
	assert(s);

	if (s->top == 0)
		return false;
	else
		return true;
}

队列

队列的概念

队列：只运行在一端进行插入数据操作，在另外一端进行删除数据操作的特殊线性表。
队列具有先进先出原则（First In First Out）
入队列：在队尾插入数据
出队列：在对头删除数据

队列的实现

使用链表实现效率更高，用数组出数据效率低，所以更多用链表

结构体的创建

typedef int QDataType;

typedef struct ListNode
{
	QDataType data;
	struct ListNode* next;
}ListNode;

typedef struct Queue
{
	ListNode* head;		//队头
	ListNode* tail;		//队尾
}Queue;

初始化

void QueueInit(Queue* q)
{
	assert(q);
	q->head = NULL;
	q->tail = NULL;
}

队尾入数据

void QueuePushBack(Queue* q, QDataType x)
{
	assert(q);
	ListNode* NewNode = BuyListNode(x);
	if (q->head == NULL)
	{
		q->head = q->tail = NewNode;
	}
	else
	{
		q->tail->next = NewNode;
		q->tail = NewNode;
	}
}

队头删数据

void QueuePopFront(Queue* q)
{
	assert(q);
	if (q->head == NULL)
	{
		q->tail = NULL;
	}
	else
	{
		ListNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
}

获取队列的有效元素

int QueueSize(Queue* q)
{
	assert(q);
	int size = 0;
	ListNode* NewHead = q->head;
	while (NewHead)
	{
		size++;
		NewHead = NewHead->next;
	}
	return size;
}

打印

void QueuePrint(Queue* q)
{
	assert(q);
	ListNode* NewHead = q->head;
	while (NewHead)
	{
		printf("%d->", NewHead->data);
		NewHead = NewHead->next;
	}
	printf("NULL\n");
}

获取队尾元素

QDataType QueueBack(Queue* q)
{
	assert(q);

	return q->tail->data;
}

获取队头元素

QDataType QueueFront(Queue* q)
{
	assert(q);
	return q->head->data;
}

判断是否为空

bool QueueEmpty(Queue* q)
{
	assert(q);
	if (q->head == NULL)
		return true;
	else
		return false;
}

销毁

void QueueDestroy(Queue* q)
{
	assert(q);
	ListNode* cur = q->head;
	while (cur)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->head = q->tail = NULL;
}