C/C++【数据结构笔记】(栈和队列)(超详细总结和细节)

• 栈和队列
• • 1.栈stack
  • • 1.1栈的概念及结构
    • 1.2栈实现
    • 1.3栈头文件
    • 1.4栈源文件
    • 1.5主函数实现
  • 2.队列
  • 2.1队列的概念及结构
  • 2.2队列的实现
  • • 2.3队列头文件
    • 2.4队列源文件
    • 2.5主函数实现
    • 2.6环形队列
  • 栈和队列区别与联系

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

LIFO是栈的特点，栈接口函数数据插入和删除操作都是在栈顶实现：

栈先进后出的特点决定其可以使用数组或者链表来实现，相对而言，数组结构会更优一些，单向链表实现栈时，入栈和出栈都需要遍历（O(N)的时间复杂度）；即使是带有尾指针的单向链表，出栈任然需要遍历（O(N)）；双向链表很完美，但占用空间显然大于数组。综上所述，数组性能更优。如下：

栈实现简述：实际上就是用顺序表，通过改变函数接口，达到后进先出的效果。静态顺序表就是实现静态栈，动态顺序表实现的则是动态栈。我们一般用动态栈。

#pragma once
#include
#include
using namespace std;
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;  
	int top;        //栈顶
	int capacity;   //容量
}Stack;
//初始化栈
void StackInit(Stack* ps);
//销毁栈
void StackDestory(Stack* ps);
//入栈
void StackPush(Stack* ps, STDataType x);
//出栈
void StackPop(Stack* ps);
//获取栈顶元素
STDataType StackTop(Stack* ps);
//获取栈中有效的元素个数
int StackSize(Stack* ps);
//判断栈是否为空，空则返回非零，不为空则返回0
bool StackEmpty(Stack* ps); 

#include"Stack.h"
void StackInit(Stack* ps)//初始化
{
	assert(ps);//断言判断是否为空
	//凡是传进来指针，就断言判断。凡是申请指针空间，就要判断是否成功！
	ps->a = (STDataType*)malloc(4 * sizeof(STDataType));
	if (ps->a == NULL)
	{
		cout << "malloc failed" << endl;
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0; 
}

void StackDestory(Stack* ps)//销毁栈
{
	assert(ps);//断言判断是否为空
	free(ps->a);
	ps->a = NULL;//释放完指针要置空，否则就是野指针
	ps->top = ps->capacity=0;
}

void StackPush(Stack* ps, STDataType x)//入栈
{
	assert(ps);//断言判断是否为空
	if (ps->top == ps->capacity)
	{
		STDataType* tmp =(STDataType*)realloc(ps->a,2 * ps->capacity * sizeof(STDataType));
		//凡是传进来指针，就断言判断。凡是申请指针空间，就要判断是否成功！
		if (tmp == NULL)
		{
			cout << "realloc failed" << endl;
			exit(-1);//exit(0)表示正常退出，exit(x)x非零表示非正常退出
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}

void StackPop(Stack* ps)//出栈
{
	assert(ps);//断言判断是否为空
	assert(ps->top);//栈空
	//ps->a[ps->top]=0;是不可取的！
	ps->top--;
}

STDataType StackTop(Stack* ps)//获取栈顶元素
{
	assert(ps);//断言判断是否为空
	assert(ps->top > 0);//栈空
	return ps->a[ps->top - 1];
}

//获取栈中有效的元素个数
int StackSize(Stack* ps)
{
	assert(ps);//断言判断是否为空
	return ps->top;
}

bool StackEmpty(Stack* ps) //判断栈是否为空，空则返回1，不为空则返回0
{
	assert(ps);
	return ps->top == 0;//代码简洁
}

#include"Stack.h"
void Stacktest()
{
	Stack st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);
	while (!StackEmpty(&st))
	{
		cout << StackTop(&st) << ' ';
		StackPop(&st);
	}   //符合栈的性质，相对而言的后进先出（相对于栈里的数据）
	StackDestory(&st);
}
int main()
{
	Stacktest();
}

入栈顺序：12345，出栈顺序：54321

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列中数据遵守先进先出FIFO（First In First Out）原则。入队列：进行插入操作的一端称为队尾，出队列：进行删除操作的一端称为队头

数组和链表都能实现队列。但FIFO的特点使得数组实现效率很低，内存浪费。而链表的结构更加优秀。用两个指针分别指向队列的队头和队尾（初始状态如图a）入队出队的过程其实就是无头单向链表的实现（头插和尾删），具体请看：（99条消息) C/C++【数据结构笔记】(顺序表&链表)(超详细总结和细节)_Answer-2296的博客-CSDN博客）

#pragma once
#include
#include
using namespace std;
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;//无头单向链表的结点

struct Queue 
{
	//用这个结构体来代表队列
	QNode* head;//指向队列的头
	QNode* tail;//指向队列的尾
};
//队列初始化
void QueueInit(Queue* qp);
//销毁队列
void QueueDestory(Queue* qp);
//入队(队尾入队)
void QueuePush(Queue* qp,QDataType x);
//出队(队头出队)
void QueuePop(Queue* qp);
// 获取队列头部元素
QDataType QueueFront(Queue* qp);
// 获取队列队尾元素
QDataType QueueBack(Queue* qp); 
// 获取队列中有效元素个数
int QueueSize(Queue* qp);
// 检测队列是否为空，如果为空返回1，如果非空返回0
bool QueueEmpty(Queue* qp);

#pragma once
#include"Queue.h"

void QueueInit(Queue* qp)//队列初始化
{
	assert(qp);
	qp->head = qp->tail = NULL;//初始化都置成空！
}

void QueueDestory(Queue* qp)//销毁队列
{
	assert(qp);
	QNode* cur = qp->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}//逐个销毁
	qp->head = qp->tail = NULL;//没用的指针都置成空，避免野指针
}

void QueuePush(Queue* qp, QDataType x)//入队(队尾入队)
{
	assert(qp);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (!newnode)
	{
		cout << "malloc failed";
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;//构建好数据结点
	if (qp->tail == NULL)
	{
		qp->head = qp->tail = newnode;
		//如果是空队列，队尾队头都要变
	}
	else
	{
		qp->tail->next = newnode;
		qp->tail = newnode;//重新改变队尾
	}
}

void QueuePop(Queue* qp)//出队(队头出队)
{
	assert(qp);
	assert(qp->head);//队列非空才能出队
	if (qp->head->next == NULL)
	{
		free(qp->head);
		qp->head = qp->tail = NULL;
	}//队列只有一个结点，则置空队列（qp->tail=NULL）如果没单独考虑，qp->tail会成为野指针。
	else
	{
		QNode* next = qp->head->next;
		free(qp->head);
		qp->head = next;
	}
}

QDataType QueueFront(Queue* qp)// 获取队列头部元素
{
	assert(qp);
	assert(qp->head);
	return qp->head->data;
}

QDataType QueueBack(Queue* qp)// 获取队列队尾元素
{
	assert(qp);
	assert(qp->head);
	return qp->tail->data;
}

int QueueSize(Queue* qp)// 获取队列中有效元素个数
{
	assert(qp);
	int size = 0;
	QNode* cur = qp->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

bool QueueEmpty(Queue* qp)// 检测队列是否为空，如果为空返回1，如果非空返回0
{
	assert(qp);
	return qp->head == NULL;//简洁！
}

#include"Queue.h"
void Queuetest()
{
	Queue  q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);
	while (!QueueEmpty(&q))
	{
		cout << QueueFront(&q) << " ";
		QueuePop(&q);//输出完删除，模拟栈出过程
	}
}
int main()
{
	Queuetest();
}

队列入队顺序12345，出队顺序12345

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组，实现，也可以使用链表实现。

栈中的数据元素遵守后进先出***LIFO（Last In First Out）***的原则。并且是相对而言，多为后进先出是指，栈现有的数据是后进先出，所以可以出现先进栈的数据比后进栈的数据先出（比如数据进栈立马出栈，这时它就比后面数据先出来，所以说栈的后进先出是相对而言的）

队列中数据遵守先进先出FIFO（First In First Out）原则。并且是绝对而言，只要是先进队列的一定是先出来的。