栈和队列【详解】

墨蓝 2024-02-18 12:32 56阅读 0赞

**目录**

一、栈

1.栈的定义

2.栈的初始化

3.入栈

4.出栈

5.获取栈顶元素

6.获取栈元素的个数

7.判断栈是否为空

8.销毁栈

二、队列

1.队列的定义

2.入队

3.出队

4.获取队头元素

5.获取队尾元素

6.判断队列是否为空

7.获取队列的元素个数

8.销毁队列

--------------------

前言：

栈和队列也是一种常见的线性表

## 一、栈 ##

### 1.栈的定义 ###

栈：仅限在一端进行插入和删除元素操作。**数据插入删除的一端称为栈顶，而另一端称为栈底**。

**压栈：**数据的插入操作。**出栈：**数据的删除操作。

栈中的数据遵循**后进先出**(**Last In First Out**,简称LIFO)的原则。

如图：

![d2f2a84fa70547489e15eb2a778d43e1.png][]

**栈的存储定义** ：

这里采用的是顺序栈，以动态数组的形式进行存放栈的元素，当栈满时，可以动态的增加栈的容量。

定义一个指针负责指向动态数组，用top来表示栈底，还有就是栈的容量capacity。

**代码：**

typedef int STDataType;
    
    typedef struct StackNode 
    {
    	STDataType* a;
    	int top; //栈底
    	int capacity;  //栈的容量
    }Stack;

### 2.栈的初始化  ###

当栈的存储定义完成后，就开始对栈进行初始化。

**代码：**

//初始化栈
    /*这里采用动态数组来进行模拟栈*/
    void InitStack(Stack* ps) 
    {
    	assert(ps);
    	ps->a = NULL;
    	ps->capacity = 0;
    	ps->top = 0;  //指向栈顶的下一个元素
    }

注意：这里定义的top 是指当top == 0 时 指向栈顶的下一个元素，当然top也可以是-1。这里采用的是top = 0。

![8432b116c5c54a38938fc367c0cf221b.png][]

### **3.入栈**  ###

当元素入栈时，我们需要先考虑一下栈的容量的问题，例如：栈满或者初次使用栈的情况。

**代码：**

//入栈
    void PushStack(Stack* ps, STDataType x) 
    {
    	assert(ps);
    	//入栈前先检查一下栈的容量
    	if (ps->capacity == ps->top)
    	{
    		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
    		//使用realloc直接为动态数组分配空间
    		STDataType* tmp = (STDataType*)realloc(ps->a,newcapacity*sizeof(STDataType));
    		if (tmp == NULL) 
    		{
    			perror("PushStack->realloc");//出错时提示
    			return;
    		}
    		else 
    		{
    			ps->a = tmp;
    			ps->capacity = newcapacity;
    		}
    	}
    
    	//数据压栈
    	ps->a[ps->top] = x;
    	ps->top++;	//同时指向下个一个栈顶元素
    }

*  这里当初次入栈时，使用realloc进行动态分配空间，初次使用realloc 时,说明ps->a == NULL，那么这里就相当于malloc进行分配空间。
 *  栈满时，不是初次入栈就让原来的栈的容量增加二倍 (2 \* ps->capacity）。
 *  栈没有满时，就直接入栈，同时top指向下一个栈顶元素。

这里多说一下，如果对于realloc不是很理解，可以转到 [realloc详细解析][realloc]

***注意**：还有就是作者刚学realloc时，总是忘记对realloc使用sizeof(),直接给出元素个数，却忘记给出其元素的大小了。* 所以不要忘记sizeof()

### 4.出栈 ###

出栈需要注意的就是：当栈空了，就不能进行出栈了，这里采用断言assert来避免

**代码：**

//出栈
    void PopStack(Stack* ps) 
    {
    	assert(ps);
    	assert(ps->top > 0);
    	ps->top--;    //栈顶减一即可
    }

###  5.获取栈顶元素 ###

这里也要注意栈为空的情况

**代码：**

//获取栈顶元素
    STDataType TopStack(Stack* ps) 
    {
    	assert(ps);
    	assert(ps->top > 0);
    	return ps->a[ps->top - 1];
    }

如图：

![236370fe03b94a81b15ae9354399a935.png][]

### 6.获取栈元素的个数 ###

因为top是从0开始的，下标：0 到 top-1，就相当于有top个元素。

**代码：**

//获取栈元素的个数
    int SizeStack(Stack* ps) 
    {
    	assert(ps);
    	return ps->top;
    }

![7ee5278cabfe414c8b7a363e3b5151b7.png][]

###  **7.判断栈是否为空** ###

这里采用bool 返回类型，如果为空就返回的是true ，不为空就返回false。

//判断栈是否为空,空返回true,非空返回false
    bool EmptyStack(Stack* ps) 
    {
    	assert(ps);
    	return ps->top == 0;
    }

### 8.销毁栈 ###

为避免内存泄漏，我们应该养成及时释放内存的好习惯。

**代码：**

//销毁栈
    void DestroyStack(Stack* ps) 
    {
    	assert(ps);
    	free(ps->a);   //释放指向的动态数组
    	ps->a = NULL;
    	ps->capacity = 0;
    	ps->top = 0;
    }

## 二、队列 ##

### 1.队列的定义 ###

队列：**只允许一端进行插入元素(队尾)，另一端机进行删除元素(队头)的线性表**。

**进队：**数据的插入操作  **出队：**数据的删除操作

队列中的数据遵循**先进先出**(**First In First Out**,简称FIFO)的原则。

如图：

![7ca4e4cce39e4377ab4d322512689a0a.png][]

**队列的存储定义：** 这里是通过单链表的形式来进行模拟队列。同时定义两个指针来进行控制，一个指向队头，另一个指向队尾。这样就可以避免再从头开始遍历链表来找尾了。

**代码：**

typedef int QDataType;
    
    //通过单链表来模拟队列
    typedef struct QueueNode 
    {
    	QDataType val;
    	struct QueueNode* next; //记录下一个结点的地址
    }QueueNode;
    
    typedef struct Queue 
    {
    	QueueNode* phead;	//指向队头的指针
    	QueueNode* tail;	//指向队尾的指针
    	int size;	//同时记录栈元素的个数
    }Queue;

### 2.入队 ###

元素入队，通过***单链表进行尾插***来模拟队列的入队。

在入队的操作中，采取使用malloc动态内存函数来开辟内存空间存放元素。因为是尾插，所以这里我们就要提前判断一下是否为第一次入队(尾插)，当然这里也可以不用判断(前提就是要有头结点)。 因为这里没有用头结点，所以需要判断一下。

![10c14afa61d34aa1bde245f7abffef80.png][]

**代码：**

//入队
    void PushQueue(Queue* pq, QDataType x) 
    {
    	assert(pq);
    	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    	if (newnode == NULL )
    	{
    		perror("PushQueue->malloc");
    		return;
    	}
    	newnode->val = x;
    	newnode->next = NULL;
    	//判断是否为第一次进行入队
    	if (pq->phead == NULL) 
    	{
    		//第一次入队
    		pq->phead = pq->tail = newnode;
    	}
    	else 
    	{
    		//不是第一次入队直接进行尾插
    		pq->tail->next = newnode;
    	}
    	pq->size++;//队列元素加一
    }

### **3.出队** ###

元素出队，这里通过***单链表的头删***进行模拟出队。出队需要注意的是队列不能为空那个，所以这里使用assert来断言进行避免

![8c8446009f1d45f59069d5afa2ad38ea.png][]

**代码：**

//出队
    void PopQueue(Queue* pq) 
    {
    	assert(pq);
    	assert(pq->phead);
    	QueueNode* next = pq->phead->next;
    	free(pq->phead);
    	pq->phead = next;
    	//当出队最后一个元素时
    	//出完队后，headz指向空，而tail却变成了访问野指了
    	//所以这里要对删的是最后一个元素进行单独处理
    	if (pq->phead == NULL)
    	{
    		pq->tail = NULL;
    	}
    	pq->size--;
    }

### 4.获取队头元素 ###

需要注意的是：队为空的情况。使用assert断言来避免

**代码：**

//获取队头元素
    QDataType TopQueue(Queue* pq) 
    {
    	assert(pq);
    	assert(pq->phead);
    	return pq->phead->val;
    }

### 5.获取队尾元素 ###

当然这里也要避免队尾为空的情况

**代码：**

//获取队尾元素
    QDataType TailQueue(Queue* pq) 
    {
    	assert(pq);
    	assert(pq->tail);
    	return pq->tail->val;
    }

### 6.判断队列是否为空 ###

队列为空就返回true,否则返回false

**代码：**

//判断队列是否为空
    bool EmptyQueue(Queue* pq) 
    {
    	assert(pq);
    	return pq->phead == NULL;
    }

###  7.获取队列的元素个数 ###

返回size

**代码：**

//获取队列元素的个数
    int SizeQueue(Queue* pq)
    {
    	assert(pq);
    	return pq->size;
    }

### 8.销毁队列 ###

**代码：**

//销毁队列
    void DestroyQueue(Queue* pq) 
    {
    	assert(pq);
    	QueueNode* cur = pq->phead;
    	while (cur)
    	{
    		QueueNode* next = cur->next; //记录下一个结点
    		free(cur);
    		cur = next;
    	}
    	pq->phead = pq->tail = 0;
    	pq->size = 0;
    }

![cb41774f60e649eead50b94e4b1df045.png][]

[d2f2a84fa70547489e15eb2a778d43e1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/88bd1ab6e4324b4bb5e957bb25b71d81.png
[8432b116c5c54a38938fc367c0cf221b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/d4b27abc22db494fbdb6a33ffb218bf0.png
[realloc]: https://blog.csdn.net/qq_72505850/article/details/133418367
[236370fe03b94a81b15ae9354399a935.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/bb42512e14ca41eaa93644477444e017.png
[7ee5278cabfe414c8b7a363e3b5151b7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/59da8eefaaef4c52ab0fed7842397487.png
[7ca4e4cce39e4377ab4d322512689a0a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/162d4f80eaa2447f8abd29d97df72575.png
[10c14afa61d34aa1bde245f7abffef80.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/dea82f269ff9425281dfc55336a8cdae.png
[8c8446009f1d45f59069d5afa2ad38ea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/01239ee479394991a19cf249dfad9c09.png
[cb41774f60e649eead50b94e4b1df045.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/647ee04879a74cc1af5c376d2db8007a.png