【数据结构】栈和队列

1.1 栈的概念

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

1.2 栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

// 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈  
typedef int STDataType;  
#define N 10  
typedef struct Stack  
{
          
     
STDataType _a[N];  
int _top; // 栈顶  
}Stack;  
// 支持动态增长的栈  
typedef int STDataType;  
typedef struct Stack  
{
          
     
STDataType* _a;  
int _top; // 栈顶  
int _capacity; // 容量  
}Stack;  
// 初始化栈  
void StackInit(Stack* ps);  
// 入栈  
void StackPush(Stack* ps, STDataType data);  
// 出栈  
void StackPop(Stack* ps);  
// 获取栈顶元素  
STDataType StackTop(Stack* ps);  
// 获取栈中有效元素个数  
int StackSize(Stack* ps);  
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0  
int StackEmpty(Stack* ps);  
// 销毁栈  
void StackDestroy(Stack* ps)

1.3栈的代码实现（链表结构）

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDataType;//便于之后更改数据类型
typedef struct QueueNode 
{
          
   
	struct QueueNode* next;
	QDataType data;
}QNode;//重命名为“QNode”

typedef struct Queue
{
          
   
	QNode* tail;
	QNode* head;
}Queue;

void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq); 
void QueuePush(Queue* pq,QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);//取队头的数据
QDataType QueueBack(Queue* pq);//取队尾的数据
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);

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

}


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


void QueuePush(Queue* pq, QDataType x)
{
          
   
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
          
   
		printf("malloc fail" );
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)//初始化需要注意
	{
          
   
		pq->head = pq->tail = newnode;
	}
	else
	{
          
   
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}


void QueuePop(Queue* pq)
{
          
   
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)//避免野指针
	{
          
   
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
          
   
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}


QDataType QueueFront(Queue* pq)//取队头的数据
{
          
   
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}


QDataType QueueBack(Queue* pq)//取队尾的数据
{
          
   
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}


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


int QueueSize(Queue* pq)
{
          
   
	assert(pq);
	QNode* cur = pq->head;
	int size = 0;
	while (cur)
	{
          
   
		++size;
		cur = cur->next;
	}
	return size;
}