数据结构-03-栈与队列

发表于 更新于 分类于 / 阅读次数： 本文字数： 1k 阅读时长 ≈ 3 分钟

本博文基于C语言数据结构，解释队列存储结构与增删改查思路。

代码:点击查阅

栈（LIFO）

栈（stack）是限定仅在表尾进行插入或删除操作的线性表。因此对栈来说，表尾端称为栈顶（top），表头端称为栈底（bottom）。不含元素的空表称为空栈。

类似于链表，无节点（头节点除外）时称为空链表。

每当新元素插入时，存入栈顶，也称压栈。退栈的第一个元素也应为栈顶元素，其逻辑为先进后出（Last In First Out）原则，简称LIFO。因此，栈本质上是一种操作固定的特殊顺序表。

image can't load. 静态栈存储结构

顺序栈与链式栈

栈类似于线性表，因此其存储结构也类似，比如静态/动态分配固定大小的顺序栈（元素在物理地址上连续）以及动态分配节点地址的链式栈（节点在物理地址上不连续）。

参阅顺序表一文：数据结构-02-线性表 | Young’s Blog

image can't load. 静态栈存储结构

代码定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
typedef int ElemType;

/* 创建Stack类型 */
typedef struct stack
{
#if STACK == 0		/* 动态分配data大小 */
	ElemType* data;
	int top;
#elif STACK == 1	/* 仅分配单个元素大小 */
	ElemType data;
	struct stack* next;
#endif
}Stack;

/* @brief 初始化栈 */
Stack* initStack(void)
{
	Stack* s = (Stack*)malloc(sizeof(Stack));	/* 动态分配栈变量内存 */
	if (s == NULL)
	{
		return NULL;
	}
#if STACK == 0 /* 动态分配栈地址，内部数据地址 */
	s->data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
	if (s->data == NULL)
	{
		return NULL;
	}
	s->top = -1;	/* 栈顶元素设置为-1 */
#elif STACK == 1 
	s->data = 0;	/* 链式栈头 */
	s->next = NULL;
#endif
	return s;
}

空栈判断与栈顶取值

栈的增删操作为压栈、出栈，改查与顺序表/链表基本一致。

如果栈非链式栈，则压栈操作需要判断栈是否满（满时报告异常提示）。而对于几种类型，出栈均需要判断栈是否为空（空时报告异常）。

  • 空栈

    通过判断Top索引值是否为预设负值，或者next是否为NULL。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* @brief 检验是否为空栈 
   @param 判断stack中top值是否为初始值 
   @retval 1，空栈；0，非空*/
int isEmpty(Stack* s)
{
	assert(s);
#if STACK == 0
	if (s->top == -1)
#elif STACK == 1
	if (s->next == NULL)
#endif 
	{
		printf("Empty Stack.\n");
		return 1;
	}
	else
	{
		return 0;
	}
}

  • 栈顶取值

    对于非空静态栈，直接取出data数据区内top索引处的数据；

    对于链式栈，则直接取头指针的next数据（LIFO特性导致栈顶元素一定在前）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* @brief 获取栈顶元素
   @param s，指针，指向待操作栈地址；
		  e，指针，指向待出栈元素；
   @retval 1，获取栈顶元素；0，空栈*/
int getTop(Stack* s, ElemType* e)
{
	assert(s);
	int result = isEmpty(s);
	if (result == 1)
	{
		return 0;
	}
#if STACK == 0
	*e = s->next[s->top];
#elif STACK == 1
	*e = s->next->data;
#endif
	return 1;
}

压栈出栈

  • 压栈

    当存储新数据时：

    1. 对于顺序表结构的栈示意图，向Top索引处填充，并增加Top索引值；
    2. 对于链式表结构的栈，创建节点并使用头插法插在头节点之后（当然尾插法也可以，但需要保证操作一致性。头插法的优势是栈顶在前，时间复杂度O(1)，而尾插法为O(n)。
image can't load. 静态栈存储结构

  • 出栈

    当弹出新数据时：

    1. 对于顺序表结构的栈示意图，提取Top索引处值，再减小Top索引值；
    2. 对于链式表结构的栈，提取hdr->next处元素值，修改链表结构，再释放该节点；

队列（FIFO）

队列（Queue）是先进先出（First In First Out）线性表，只允许再表的一端进行插入，在另一端删除。队列中允许插入的队尾端为rear，允许删除的队头为front。

————————— 暂时断更 —————————

————————— End —————————

近水楼台先得月，向阳花木易为春。–《断句》