登录 注册

摸一摸数据结构（栈与队列）

本贴最后更新于 1176 天前，其中的信息可能已经事过景迁

栈与队列是两种重要的线性结构。从数据结构角度来看，栈和队也是线性表，其特殊性在于其操作受限，是限定性的数据结构。但从数据类型上看，它是和线性表大为不同的抽象数据类型。

栈与队列的定义和概念

栈

定义

栈（stack）是限定在表尾巴进行插入或删除操作的线性表；栈是一种后进先出的线性表（LFIO 结构），比如货仓里的货物。

栈顶

栈顶（top）是线性表运行进行插入删除的那一端。

栈底

栈底（bottom）是固定的，不允许进行插入与删除的另一端。

卡特兰数

卡特兰数（catalan）是对栈的一种数学描述。n 个不同元素进栈，出栈元素不同排列个数为 \frac{1}{n+1}C^{n}_{2n}

性质

栈是一种后进先出的线性表（LFIO 结构），比如货仓里的货物。

队列

定义

队列（queue）是一种先进先出（FIFO）的线性表，只允许在一端插入，而在另一端删除。

队尾

队尾（rear）是允许插入的一端。

队首

队首（front）是允许删除的一端。

栈与队列的实现

注：这里栈实现的是顺序栈，队是链队。此外如链队，循环队等等后补（咕咕咕）；并且在实现后的测试均只测试部分。

栈

顺序栈的数据结构
#include <stdio.h>
#include <stdlib.h>
#include "Status.h"
//顺序栈相关操作
#define stackinitsize 100
#define stackincrement 10
//在迷宫 表达式 二叉树二叉链表 孩子兄弟树中次类型要重新定义
typedef int selemtype_sq;
typedef struct{
	selemtype_sq *base;//在栈构造之前和销毁后，base值为null
	selemtype_sq *top;//栈顶指针
	int stacksize;//栈规模
}sqstack;
初始化
Status initstacksq(sqstack *S){
	(*S).base=(selemtype_sq*)malloc(stackinitsize*sizeof(selemtype_sq));
	if(!(*S).base) exit(OVERFLOW);
	(*S).top=(*S).base;
	(*S).stacksize=stackinitsize;
	return OK;
};

和顺序表的初始化类比，都是一样的思路。

出入值是指针类型，指向 sqtack 结构量 S；我们对数据元素 base 进行空间分配（后判断是否分配成功）。然后将栈顶也指向栈底指向的空间（这样栈的长度就为 0 了）；将栈的最大规模赋值为栈的初始化规模。

销毁
Status destorystacksq(sqstack *S){
	free((*S).base);
	(*S).base=NULL;
	(*S).top=NULL;
	(*S).stacksize=0;
	return OK;
};

和顺序表类比。

我们需要对初始化中申请的空间进行释放（free），是否之后我们要将指针指向空（不然这个指针就是一个没有指向的野指针），最后对栈规模清 0.

清空与栈长栈空
Status clearstacksq(sqstack S){
	(*S).top=(*S).base;
	return OK;
};
int stacklensq(sqstack S){
	return S.top-S.base;
};
Status stackemptysq(sqstack S)
{
	if(S.top==S.base)
		return TRUE;
	else
		return FALSE;
}

略

返回栈顶元素
Status gettopsq(sqstack S,selemtype_sq *e){
	if(S.top==S.base) return ERROR;
	*e=*(S.top-1);
	return OK;
};

传入值是栈 S 和指针 e（保存栈顶元素）。对栈长度进行判断，若长度为 0，则后续操作没有意义了。

我们可以直接访问栈顶元素（也就是 S.top）。

为什么这里的栈顶元素是（S.top-1）呢？

我的理解是这里 S.top 是一个没有元素值的栈顶，也就是说仅仅是为了栈结构而存在的栈顶（有了栈顶就方便进行定义中的限定操作），这样做可以保护数据。

进栈和出栈
Status pushsq(sqstack *S,selemtype_sq e){
	if((*S.top-(*S).base)+1>=(*S).stacksize){
		(*S).base=(selemtype_sq*)realloc((*S).base,((*S).stack+stackincrement));
		if(!(*S).base) exit(OVERFLOW);
		(*S).top=(*S).base+(*S).stacksize;
		(*S).stacksize+=stackincrement;
	}

	*(S->top)=e;
	(S->top)++;

	return OK;
};


Statsu popsq(sqstack *S,selemtype_sq *e){
	if((*S).top==(*S).base) return ERROR;

	(*S).top--;
	*e=*((*S).top);
	return OK;
};

进栈传入指针类 S（指向栈，因为我们需要对栈元素进行改变）和元素 e。

判断元素进栈后长度是否超过规模，若超过，需要重新分配空间。之后进行元素的入栈，我们将元素 e 填充到栈顶的位置，然后栈顶加一

出栈类似，栈顶减一，将栈顶的元素取出。

遍历
Status stacktravesq(sqstack S,void(Visit)(selemtype_sq)){
	selemtype_sq *p=S.base;

	while(p<S.top) Visit(*p++);
	return OK;
};

略

栈测试
#include <stdio.h>
#include "sequncestack.h"

void printelem(selemtype_sq e){
	printf("%d ",e);
};

int main(){
	sqstack S;
	int i=0;
	selemtype_sq e=0;

	printf("init测试...\n");
	{
		printf("初始化顺序栈S...\n");
		initstacksq(&S);
		printf("\n");
	}
	PressEnter;
	printf("stackempty测试...\n");
	{
		stackemptysq(S)?printf("S 为空\n") : printf("S 不为空\n");
		printf("\n");
	}
	PressEnter;
	printf("push测试\n");
	{
		for(i=1;i<=6;i++){
			printf("将%2d压入栈S",2*i);
			pushsq(&S,2*i);
			printf("（累计第 %d 个元素）...\n", S.top-S.base);
		}
		printf("\n");
	}
	PressEnter;
	printf("stacktravesq 测试...\n");
	{
		printf(" S 中的元素为：S = ");						 
		stacktravesq(S, printelem);
		printf("\n\n");
	}
	PressEnter;

	printf("pop 测试...\n");			
	{
		popsq(&S, &e);
		printf("栈顶元素 \"%d\" 出栈...\n", e);
		printf(" S 中的元素为：S = ");						 
		stacktravesq(S, printelem);
		printf("\n\n");
	}
	PressEnter;

	printf("stacklensq 测试...\n");
	{
		i = stacklensq(S);
		printf(" S 的长度为 %d \n", i);
		printf("\n");
	}
	PressEnter;

	printf("gettop 测试...\n");	
	{
		gettopsq(S, &e);
		printf("栈顶元素的值为 \"%d\" \n", e);
		printf("\n");
	}
	PressEnter;

}

image.png

队列

链队数据结构
#include <stdio.h>
#include <stdlib.h>
#include "Status.h"
//链队相关操作，在模拟银行排队二叉树三叉链表算法需重新定义
typedef int qelemtype_l;
typedef struct qnode{
	qelemtype_l data;
	struct qnode *next;
}qnode;
typedef qnode* queueptr;
typedef struct{
	queueptr front;
	queueptr rear;
}linkqueue;

注意这里 typedef struct qnode 和过去的结构定义不太一样，对语法来说我们不需要在 struct 后面跟类型名，但是这里我们在结构体内设置了数据元素 struct qnode；可能是因为程序自上而下进行，如果不 typedef struct qnode 这么用，程序无法识别这个数据元素是什么。

初始化
Status initqueuel(linkqueue *Q){
	(*Q).front = (*Q).rear = (queueptr)malloc(sizeof(qnode));
	if(!(*Q).front)
		exit(OVERFLOW);

	(*Q).front->next = NULL;

	return OK;
};

传入的是链类型指针 Q，对链头和链尾进行空间分配，判断分配成功后对这两个指针赋值 NULL ，不要让他们成为野指针。

清空
void clearqueuel(linkqueue *Q){
	(*Q).rear = (*Q).front->next;

	while((*Q).rear)
	{
		(*Q).front->next = (*Q).rear->next;
		free((*Q).rear);
		(*Q).rear = (*Q).front->next;
	}

	(*Q).rear = (*Q).front;

};

链式存储与顺序存储是不同的，注意链之间的关系，注意勾链的逻辑，一般是先右后左。

看看链队的勾链把，首先链尾设置为链头的后一位，现在将链头的下一个指向链尾的下一个，释放链尾，链尾重新指向为链头的下一个；这样我们就释放了一个结点，一直循环到没有链尾（结点）。

这时为了保证队链结构的完整性，我们讲队尾指向队首。

销毁
void destoryqueuel(linkqueue *Q){
	while((*Q).front)
	{
		(*Q).rear = (*Q).front->next;
		free((*Q).front);
		(*Q).front = (*Q).rear;
	}
};

销毁只需要将整个空间释放就行了，将首尾相指，释放空间，重新定向，如此循环，直到最后一个结点被释放。

判空和队长
Status queueemptyl(linkqueue Q){
	if(Q.front==Q.rear)
		return TRUE;
	else
		return FALSE;
};
int queuelenl(linkqueue Q){
	int count = 0;
	queueptr p = Q.front;

	while(p!=Q.rear)
	{
		count++;
		p = p->next;
	}

	return count;
};

略

得到队首元素
Status getheadl(linkqueue Q,qelemtype_l *e){
	queueptr p;

	if(Q.front==Q.rear)
		return ERROR;

	p = Q.front->next;
	*e = p->data;

	return OK;
};

类似于栈，我们首先要判断长度，如果长度为 0 程序也没有进行下去的必要了。同样这里我们默认为链头结点是不存放数据的，取出第一个元素数据是链头的后一个。

入队
Status enqueuel(linkqueue *Q,qelemtype_l e){
	queueptr p;

	p = (queueptr)malloc(sizeof(qnode));
	if(!p)
		exit(OVERFLOW);

	p->data = e;
	p->next = NULL;

	(*Q).rear->next = p;
	(*Q).rear=p;

	return OK;
};

对于链式结构来说，增添新元素就是添加一个结点，所有我们要为这个结点分配空间（这个结构 qnode 内有指针，我们要弄清楚什么时候需要去分配，弄清楚 malloc 服务的对象）。分配成功后对结点赋值。队是限制性操作的线性表，我们直接在队尾前插入就行。

注意这里是怎么插入的，这里是先右，(*Q).rer->next=p 后左 (*Q).rear=p ；尾结点的下一个指向（是）p，这是将结点 p 入链；后更新尾指针为 p，这时候队尾指针就是指向结点 p 的。

在写下这段话后，我们感觉到了指针与实体结点的疏离感，其实我本身会混淆指针与结点之间的关系，认为指针就是结点，猫猫愚钝。

出队
Status dequeuel(linkqueue *Q,qelemtype_l *e){
	queueptr p;

	if((*Q).front==(*Q).rear)
		return ERROR;

	p = (*Q).front->next;
	*e = p->data;

	(*Q).front->next = p->next;
	if((*Q).rear==p)
		(*Q).rear = (*Q).front;

	free(p);

	return OK;
};

略 注意勾链的步骤。

遍历
void queuetravell(linkqueue Q,void(Visit)(queuetype_l)){
	queueptr p;

	p = Q.front->next;

	while(p)
	{
		Visit(p->data);
		p = p->next;
	}
};

通过一个指针不断向后移动完成遍历

链队测试
#include <stdio.h>
#include "linkqueue.h"

void printelem(qelemtype_l e){
	printf("%d ",e);
}

int main(){
	linkqueue Q;
	int i=0;
	qelemtype_l e=0;

	printf("initqueuel 测试...\n");
	{
		printf("初始化链队 Q ...\n");					 
		initqueuel(&Q);
		printf("\n");
	} 
	PressEnter;

	printf("queueemptyl 测试...\n");
	{
		queueemptyl(Q) ? printf(" Q 为空！！\n") : printf(" Q 不为空！\n");
		printf("\n");
	} 
	PressEnter;

	printf("enqueuel 测试...\n");
	{
		for(i=1; i<=6; i++)							
		{
			printf("元素 \"%2d\" 入队，", 2*i);
			enqueuel(&Q, 2*i);
			printf("（累计第 %d 个元素）...\n", queuelenl(Q));
		}
		printf("\n");
	} 
	PressEnter;

	printf("queuetravell 测试...\n");
	{
		printf(" Q 中的元素为：Q = ");						 
		queuetravell(Q, printelem);
		printf("\n\n");
	} 
	PressEnter;

	printf("dequeuel 测试...\n");
	{
		dequeuel(&Q, &e);
		printf("队头元素 \"%d\" 出队...\n", e);
		printf(" Q 中的元素为：Q = ");						 
		queuetravell(Q, printelem);
		printf("\n\n");
	} 
	PressEnter;

	printf("queuelengthl 测试...\n");
	{
		i = queuelenl(Q);
		printf(" Q 的长度为 %d \n", i);
		printf("\n");
	} 
	PressEnter;

	printf("getheadl 测试...\n");
	{
		getheadl(Q, &e);
		printf("队头元素的值为 \"%d\" \n", e);
		printf("\n");
	} 
	PressEnter;
}

image.png

栈与队列的应用

栈与队列的应用十分广泛，光书上的就有数制转换，括号匹配，行程序编辑，迷宫，表达式求值，汉诺塔等等，有时间补（鸽了！）

思考

  1. 栈和队列的主要区别
  2. 3 个不同元素依次进栈，能有几种不同的出栈序列

这里顺便把上节的问题回答了

  1. 存储密度大，方便访问
  2. 随机，注意这里是存储结构，意思是我们能够通过下标任意的访问第 i 号元素的数值。与之相反的链式存储，你想想，链表的每个结点都有一个指向后继的指针，所以我们要访问链表的结点必须从第一个开始访问，真能说是随机的吗？
    但另一方面，我们称顺序表的顺序存储结构，指的是逻辑结构上是紧紧挨着的。
    所以 线性表的顺序存储结构是一种随机存取的存储结构。哈哈怎么样晕了吗。

ps: 摸一摸数据结构(目录)

85 4 8 9 11 5 48

相关帖子

回帖
摸一摸数据结构（栈与队列）

欢迎来到这里！

我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。

注册 关于
请输入回帖内容 ...
stillwarter
啥也不会
回帖
17
 帖子
21
 积分
4453