数据结构~07.栈和队列的基本概念

川长思鸟来 2023-03-01 12:43 12阅读 0赞

# 数据结构~07.栈和队列的基本概念 #

## [本文是上一篇文章的后续,详情点击该链接~][Link 1] ##

## 栈的定义: ##

栈是一种只能在一端进行插入或删除的线性表。其中,允许插入或删除的一端为栈顶(TOP)。栈顶由一个称为栈顶指针的位置指示器来指示。它是动态变化的。表的另一端为栈底,栈底固定不变。栈的插入和删除操作一般称为入栈和出栈。由栈的定义可以看出,栈的主要特点就是先进后出。

### 栈的存储结构: ###

栈可以用顺序表和链表来存储。也称顺序栈和链栈。在栈的定义中已经说明,栈就好像是一种稍加限制之后的线性表。

#define MAXSIZE 100
    //顺序栈的定义
    typedef struct { 
    	int data[MAXSIZE];		//存放栈中元素,MAXSIZE是已经定义的常量
    	int top;				//栈顶指针
    }SqStack;					//顺序栈结点定义
    
    //链栈结点定义
    typedef struct LNode { 
    	int data;					//数据域
    	struct LNode *next;			//指针域
    }LNode;							//链栈结点的定义

##### 链栈 #####

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

## 队列的定义 ##

队列简称队,它也是一种操作受限的线性表。其限制为仅允许在表的一端插入，在表的另一端删除。可进行插入的一端为队尾,可进行删除的一端为队头。向队列插入新元素称为进队,从队列中删除元素称为出队。队列的特点概括起来就是：先进先出。

### 队列的存储结构 ###

队列可以用顺序表和链表来存储队列。称为顺序队和链队两种。

#define MAXSIZE 100
    //顺序队的定义
    typedef struct { 
    	int data[MAXSIZE];
    	int front;				//队首指针
    	int rear;				//队尾指针
    }SqQueue;					//顺序队结点类型定义
    
    //=====================================================
    
    //链队定义
    //队结点类型
    typedef struct QNode { 
    	int data;				//数据域
    	struct QNode* next;		//指针域
    }QNode;						//队结点类型定义
    //链队类型定义
    typedef struct { 
    	QNode* front;			//队头指针
    	QNode* rear;			//队尾指针
    }LiQueue;					//链队类型定义

##### 链队 #####

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

[Link 1]: https://blog.csdn.net/qq_41424688/article/details/107549602
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDI0Njg4_size_16_color_FFFFFF_t_70]: /images/20230208/d3ad2d1ab059409cb50044c68dba1a00.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDI0Njg4_size_16_color_FFFFFF_t_70 1]: /images/20230208/2c0158a185314b3bad270e4835217243.png