[数据结构与算法]数据结构之栈和队列

数据结构之栈和队列

一、栈的定义

栈这种数据结构，就好像手枪弹夹的子弹一样，最先压进弹夹的子弹最后打出来，最后压进弹夹的子弹会最先打出来。所以这种像弹夹里的子弹一样，先进入，却是最后出来，最后进入的却最先出来的数据结构就是栈。总结一句话，就是先进后出。

栈（stack）是限定在表尾进行插入和删除操作的线性表

我们把允许插入和删除的一端叫做栈顶（top），另一端叫做栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构。

要注意的是，栈是一个线性表，即栈元素具有线性关系，有前驱和后继。只不过是一种特殊的线性表。其特殊支持就在于限制了线性表插入和删除的位置，无论插入和删除，都在栈顶出操作。这就造成了栈底是固定的，最先进栈的只能在栈底。

栈的插入操作，叫做进栈、也称压栈、入栈。类似子弹压入弹夹。

栈的删除操作，叫做出栈，有的也叫做弹栈。如同将弹夹中的子弹打出来。

来看一下栈的顺序结构定义：

typedef int SDataType;
typedef struct Stack
{
	SDataType* a;
	int top;
	int capacity;
} Stack;

top为栈顶指针（虽然叫他指针，但其实不是真的指针，只是因为叫的顺口），当栈为空时top为-1，不为空时，栈顶指针为栈顶元素下标。

栈的链式结构的定义：

typedef int SDataType;
typedef struct StackNode
{
    SElemType data;
    struct StackNode* next;
} StackNode;

typedef struct LinkStack
{
	StackNode* top;
	int capacity;
} LinkStack;
;

二、顺序栈的进栈与出栈

1.进栈操作

进栈操作只需要判断栈满的情况。然后更改top，再在对应位置入栈。

static void IsExpand(Stack* sp)
{
	if (sp->top + 1 == sp->capacity)
	{
		SDataType* temp = (SDataType*)realloc(sp->a, sizeof(SDataType) * sp->capacity * 2);
		if (temp == NULL)
		{
			printf("%s\n", strerror(errno));
			exit(-1);
		}
		sp->a = temp;
		sp->capacity *= 2;
		printf("扩容成功!\n");
	}
}

void StackPush(Stack* sp, SDataType x)
{
	assert(sp);
	IsExpand(sp);
	sp->top++;
	sp->a[sp->top] = x;
	printf("入栈成功!\n");
}

2.出栈操作

出栈操作只需要判断栈是否为空，然后更改top即可。

void StackPop(Stack* sp)
{
	assert(sp);
	if (sp->top == -1)
	{
		printf("栈为空！\n");
	}
	else
	{
		sp->top--;
	}
}

三、链栈的进栈与出栈

1.进栈

链栈的进栈操作只需要让新结点的next指向原top指针指向的结点，然后修改top指针的指向即可。

代码如下（示例）：

void StackPush(LinkStack* sp, SDataType x)
{
	assert(sp);
	newnode = (StackNode*)malloc(sizeof(StackNode));
	newnode->data = x;
	newnode->next = sp->top;
	sp->top = newnode;
	sp->capacity++;
}

2.出栈

代码如下（示例）：

void StackPop(Stack* sp)
{
	assert(sp);
	if (sp->capacity == 0)
	{
		printf("栈为空!\n");
	}
	else
	{
		StackNode* temp = sp->top;
		sp->top = sp->top->next;
		sp->capacity--;
		free(temp);
		temp = NULL;
	}
}

四、队列的定义

不知道大家在使用电脑时有没有这样的经历，有时候电脑会处于一种疑似死机的状态，鼠标点什么都没有反应。就当你失去耐心，打算重启电脑时，突然它像酒醒了一样，把你刚才点击的所有操作全部按顺序执行了一遍。这其实是因为操作系统中多个程序需要通过一个通道输出，而按照先后次序排队等待造成的。

这其实就是应用了一种数据结构来实现刚才提到的先进先出的排队功能，这就是队列。

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。而这也符合我们通常生活中的习惯，摆在第一个的优先出列，最后来的当然就拍到了队尾。再比如，用键盘进行各种字母或者数字的输入，到显示器上的输出，其实就是队列的典型应用。

那好，我们假设一个队列有n个元素，则顺序存储的队列需要建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即是队头。所谓的入队操作，其实就是在队尾增加一个元素，不需要移动任何元素。

而与栈不同的是，队列元素的出队操作是在队头，也即下标为零的位置。那就意味着，队列中剩余的元素都得要向前移动，以保证队头在0的位置。就如同现实中的排队那样。但是仔细想一想，为什么出队时要移动全部元素呢？如果不去限制队头的下表是不是更好呢？那这样问题也就来了，如果不限制队头，那队列的长度不是越来越短了嘛。为了应对这种情况，我们考虑让队列成为一个首尾相连的循环。而这种头尾相连的顺序存储结构称为循环队列。

这时我们引入两个指针，一个队头指针front指向队头元素的下标，一个队尾指针rear指向队尾的后一个元素。那如何判断队满和队空呢？

当front和rear指向相同下标时，队为空。但是我们会发现，当队满的时候front和rear依然相等。其实，我们可以空出一个元素空间，也就是说当队满时，数组中还有一个空间。假设队列的尺寸是QueueSize，那么队满的条件就是（rear + 1）% QueueSize == front。队空的条件就是rear == front。

判断队列长度分为两种情况：

1. front比rear小，这时直接用rear - front就可以得出队长。
2. front比rear大，这时我们要用QueueSize - front + rear。
3. 综合一下两个式子可以得出队长的计算公式（rear - front + QueueSize）% QueueSize。

接下来请看循环队列的顺序存储结构：

typedef int QDataType;
typedef struct
{
    QDataType data[MAX_SIZE];
    int front;
    int rear;
} SqQueue;

下面是循环队列的链式存储结构：

typedef int QDataType;

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

typedef struct LinkQueue
{
	QueueNode* front;
	QueueNode* rear;
} LinkQueue;
;

五、顺序存储队列的入队与出队

1.入队

出队操作很想简单，首先判断队满，接着让让入队元素插入队尾指针所指向的下标，再让队尾指针下标后移即可。

void EnQueue(SqQueue* Q, QDataType e)
{
    if ((Q->rear + 1) % MAX_SIZE == Q->front)
    {
        return -1;   //队满，返回
    }

    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAX_SIZE;

}

2.出队

出队操作也很简单，首先要判断队列是否为空，若不为空则让队头指针后移即可。

void DeQueue(SqQueue* Q, QDataType e)
{
    if (Q->front == Q->rear)
    {
        return -1;
    }
    Q->front = (Q->front + 1) % MAX_SIZE;

}

六、链式存储队列的入队与出队

1.入队

入队只需将新结点链接到队尾即可。

void EnQueue(LinkQueue* Q, QDataType x)
{
	assert(Q);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		printf("%s\n", strerror(errno));
	}
	newnode->data = x;
	newnode->next = NULL;
	if (Q->front == NULL)
	{
		Q->front = newnode;
		Q->rear = newnode;
	}
	else
	{
		Q->rear->next = newnode;
		Q->rear = Q->rear->next;
	}
}

2.出队

出队操作首先要判断队列是否为空，接着释放队头指针所指向的结点，再将队头指针后移。

void QueuePop(LinkQueue* Q)
{
	assert(Q != NULL && Q->front != NULL);
	QueueNode* temp = Q->front;
	Q->front = Q->front->next;
	free(temp);
	if (Q->front == NULL)
	{
		Q->rear = NULL;
	}
}

总结

栈：限定在表尾进行插入和删除的线性表
队列：只允许在一端进行插入操作，而在另一端进行删除操作的线性表

它们均可以用线性表的顺序存储结构来实现。对于栈来说，如果两个数据类型形同，则可以用数组两端作为栈底的方法来让两个栈共享数据空间。

对于队列来说，为了避免插入和删除时需要移动元素，于是引入了循环队列，使得队头和队尾可以在数组中循环变化，解决了移动数据的消耗。