数据结构（三）：栈和队列

左手的ㄟ右手 2021-09-07 14:58 525阅读 0赞

### 文章目录 ###

*  一、栈
 *   *  1.栈的概念和结构
     *  2.栈的实现
     *   *  （1）栈的结构
         *  （2）栈的初始化和销毁
         *  （3）数据入栈
         *  （4）数据出栈
         *  （5）取栈顶的元素
         *  （6）判断栈是否为空
 *  二、队列
 *   *  1.队列的概念和结构
     *  2.队列的实现
     *   *  （1）队列的结构
         *  （2）队列的初始化和销毁
         *  （3）数据入队
         *  （4）数据出队
         *  （5）得到队头队尾的数据
         *  （6）判断队列是否为空
 *  感谢阅读，如有错误请批评指正

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

# 一、栈 #

## 1.栈的概念和结构 ##

栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素的操作。进行数据插入和删除操作的一端成为栈顶，另一端称为栈底。栈中的元素遵循后进先出（LIFO, Last In First Out）原则。

压栈/入栈/进栈：向栈顶插入一个元素。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MTk4MzYwNA_size_16_color_FFFFFF_t_70_pic_center]

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

出栈：在栈顶删除一个元素。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MTk4MzYwNA_size_16_color_FFFFFF_t_70_pic_center 1]

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

## 2.栈的实现 ##

栈的实现可以使用数组实现，也可以使用链表。  
但是相对而言数组的结构实现更优一些。由于栈的操作都是在栈底（数组尾部或链表尾部），使用数组只需O(1)即可访问，而用链表则需要O(N)才能访问，本文选择使用数组来实现。

（注：如果想用链表实现栈，把栈顶放在链表的头部即可在O(1)内访问）

### （1）栈的结构 ###

由于栈的访问都是在尾上，所以此处用一个top来标记尾。

代码如下（示例）：

// 支持动态增长的栈，本文以动态增长的栈为例
    typedef int STDataType;
    typedef struct Stack
    { 
    	STDataType* a;//存储数据的数组
    	int top; //栈顶的位置
    	int capacity; //栈能存储的最大容量
    }stack;
    
    //静态的栈
    typedef int STDataType;
    #define N 10
    typedef struct Stack
    { 
    	STDataType a[N];
    	int top; // 栈顶
    }Stack;

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

### （2）栈的初始化和销毁 ###

代码如下（示例）：

//栈的初始化
    void StackInit(stack* st)
    { 
    	assert(st);
    
    	//这里给栈的初始大小为4个整型变量的大小
    	st->a = (STDataType*)malloc(sizeof(stack)* 4);
    	st->top = 0;//给栈顶一个初始值也可设置为其他值
    	st->capacity = 4;//给一个初始大小，也可设置为其他值
    }
    
    //栈的销毁
    void StackDestroy(stack* st)
    { 
    	assert(st);
    	free(st->a);
    	st->a = NULL;
    	st->capacity = 0;
    	st->top = 0;
    	free(st);
    }

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

### （3）数据入栈 ###

代码如下（示例）：

void StackPush(stack* st, STDataType x)
    { 
    	assert(st);
    	
    	if (st->top == st->capacity)//如果栈满则扩容
    	{ 
    		STDataType* tmp = (STDataType*)realloc(st->a, sizeof(stack)* st->capacity * 2);
    
    		if (tmp == NULL)
    		{ 
    			exit(-1);//结束整个程序
    		}
    		st->capacity *= 2;
    		st->a = tmp;
    	}
    
    	//在top位置插入数据后，top++表示栈顶向后移一个位置
    	st->a[st->top++] = x;
    }

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

### （4）数据出栈 ###

代码如下（示例）：

void StackPop(stack* st)
    { 
    	assert(st);
    	assert(!StackEmpty(st));//判断栈非空，若空则不进行删除操作
    
    	st->top--;//top--即可，下一次数据入栈会直接覆盖top位置的值
    }

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

### （5）取栈顶的元素 ###

代码如下（示例）：

STDataType StackTop(stack* st)
    { 
    	assert(st);
    	assert(!StackEmpty(st));
    
    	return st->a[st->top - 1];
    }

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

### （6）判断栈是否为空 ###

代码如下（示例）：

//判断栈是否为空
    bool StackEmpty(stack* st)
    { 
    	assert(st);
    	return (st->top == 0);//若top为0，说明栈中没有元素，为空
    }
    
    //得到栈的数据个数
    int StackSize(stack* st)
    { 
    	assert(st);
    	return st->top;
    }

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

# 二、队列 #

## 1.队列的概念和结构 ##

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)。

入队：进行插入操作的一端称为队尾。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MTk4MzYwNA_size_16_color_FFFFFF_t_70_pic_center 2]

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

出队：进行删除操作的一端称为队头。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MTk4MzYwNA_size_16_color_FFFFFF_t_70_pic_center 3]

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

## 2.队列的实现 ##

### （1）队列的结构 ###

队列需要同时在队头和队尾进行操作，这里使用链表实现。  
但由于链表访问队尾时效率较低，所以用tail结构体指针指向链表的末尾。

代码如下（示例）：

typedef int QNDataType;
    typedef struct QueueNode//对列结点的结构体
    { 
    	struct QueueNode* next;
    	QNDataType val;
    }QueueNode;
    
    //队列
    typedef struct Queue
    { 
    	QueueNode* head;//指向队头结点
    	QueueNode* tail;//指向队尾结点
    }Queue;

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

### （2）队列的初始化和销毁 ###

代码如下（示例）：

//队列的初始化
    void QueueInit(Queue* pq)
    { 
    	pq->head = NULL;
    	pq->tail = NULL;
    }
    
    //队列的销毁
    void QueueDestroy(Queue* pq)
    { 
    	assert(pq);
    
    	//遍历把每一个队列结点都free掉
    	QueueNode* cur = pq->head;
    	while (cur)
    	{ 
    		//free前保留下一个结点
    		QueueNode* next = cur->next;
    		free(cur);
    		cur = next;
    	}
    	pq->head = NULL;
    	pq->tail = NULL;
    	free(pq);
    }

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

### （3）数据入队 ###

代码如下（示例）：

void QueuePush(Queue* pq, QNDataType x)
    { 
    	assert(pq);
    
    	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    	if (newnode == NULL)
    	{ 
    		exit(-1);//创建新结点失败，直接退出
    	}
    	newnode->val = x;
    	newnode->next = NULL;
    	
    	//队列中一个结点都没有
    	if (pq->tail == NULL)
    	{ 
    		//新结点即使队头也是队尾
    		pq->head = newnode;
    		pq->tail = newnode;
    	}
    	else
    	{ 
    		//队列中优有结点，在队尾插入新结点
    		pq->tail->next = newnode;
    		pq->tail = newnode;
    	}
    }

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

### （4）数据出队 ###

代码如下（示例）：

void QueuePop(Queue* pq)
    { 
    	assert(pq);
    	assert(!QueueEmpty(pq));//没有结点不进行删除操作
    	
    	//只有一个结点，删除该结点后将head，tail置空
    	if (pq->head->next == NULL)
    	{ 
    		free(pq->head);
    		pq->head = NULL;
    		pq->tail = NULL; 
    	}
    	//多个结点
    	else
    	{ 
    		//保留头结点的下一个结点，下一个结点为新的头
    		QueueNode* next = pq->head->next;
    		free(pq->head);
    		pq->head = next;
    	}
    }

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

### （5）得到队头队尾的数据 ###

代码如下（示例）：

//得到队头的数据
    QNDataType QueueFront(Queue* pq)
    { 
    	assert(pq);
    	assert(!QueueEmpty(pq));
    
    	return pq->head->val;
    }
    
    //得到队头尾的数据
    QNDataType QueueBack(Queue* pq)
    { 
    	assert(pq);
    	assert(!QueueEmpty(pq));
    
    	return pq->tail->val;
    }

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

### （6）判断队列是否为空 ###

代码如下（示例）：

//判断队列是否为空
    bool QueueEmpty(Queue* pq)
    { 
    	assert(pq);
    	//头结点为空则队列为空
    	return (pq->head == NULL);
    }
    
    //得到队列的结点个数
    int QueueSize(Queue* pq)
    { 
    	int size = 0;
    	QueueNode* cur = pq->head;
    
    	while (cur)
    	{ 
    		size++;
    		cur = cur->next;
    	}
    
    	return size;
    }

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

# 感谢阅读，如有错误请批评指正 #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MTk4MzYwNA_size_16_color_FFFFFF_t_70_pic_center]: /images/20210813/1bea93761dac49fe867c46aafa3569c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MTk4MzYwNA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210813/646b19e28c7e48e292def790906176d6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MTk4MzYwNA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20210813/56b9d0ae0a6a47b78ad994d508217e78.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MTk4MzYwNA_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20210813/5a23cc924e474e7688c38908bf5eb853.png