【数据结构与算法】栈和队列

栈和队列是两种常见的重要的数据结构

栈和队列是线性表的子集（是插入和删除位置受限的线性表）

一.栈

1.1定义

栈(Stack)： 一种特殊的线性表，只允许在栈顶进行插入和删除元素操作。栈中的数据元素遵守后进先出LIFO (Last In First Out)的原则。

• 栈顶Top：允许进行插入、删除操作的一端称为栈的栈顶(top)，也称为表尾。
• 栈底Base：固定不动的一端，称为栈底（bottom），也称为表头。
• 进栈PUSH(x)：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
• 出栈POP(y)：栈的删除操作叫做出栈/弹栈，出数据也在栈顶。

栈满时的处理方法：

1. 报错，返回操作系统
2. 分配更大的空间，作为栈的存储空间，将原栈的内容移入新栈。

*进栈出栈的变化形式

看完定义，就会有同学发出质疑：那么最先进栈的元素，是不是就只能是以后出栈呢？

答案是不一定，要看是哪一种情况。栈对线性表的插入和删除的位置进行了限制，并没有对元素进出的时间进行限制，也就是说，在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是栈顶元素就可以。

举例来说，如果现在我们有3个整形数字元素1，2，3依次进栈，会有哪些出栈顺序呢？

• 第一种：1、2、3进，再3、2、1出。这是最简单、最好理解的一种，出栈次序为321。
• 第二种：1进，1出，2进，2出，3进，3出。也就是进一个出一个，出栈顺序为123。
• 第三种：1进，2进，2出，1出，3进，3出。出栈顺序为213。
• 第四种：1进，1出，2进，3进，3出，2出。出栈顺序为132。
• 第五种：1进，2进，2出，3进，3出，1出。出站顺序是231。

有没有可能是312这样的次序出栈呢？答案是肯定不会。因为3先出栈也就意味着3曾经进过栈，那既然3都进栈了，就意味着1和2已经进栈了，此时，2一定是在1的上面，就是说更接近栈顶，那么出栈顺序只能是321，不然不满足123一次进栈的要求，所以此时不会发生1比2先出栈的情况。

顺序栈和链式栈

栈也分为顺序栈和链栈（类比顺序表和链表）采用顺序存储的栈称为顺序栈，用一段物理地址连续的存储单元依次存储数据元素，通常以数组的形式实现；采用链式存储的栈称为链栈。

1. 栈的顺序存储结构

既然栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，我我们简称为顺序栈。利用一组地址连续的存储单元一次存放自栈底到栈顶的数据元素。栈底一般在低地址端。线性表是用数组来实现的。

• 附设top指针，指示栈顶元素在顺序栈中的位置，但是为了方便操作，通常top指示真正的栈顶元素之上的下标地址（top指针永远指向空）。
• 另设base指针，指示栈底元素在顺序栈中的位置，即首地址或基地址。

我们定义一个top变量来指示栈顶元素在数组中的位置，这top就如同中学物理学过的游标卡尺的游标，如下图所示，他可以来回移动，意味着栈顶的top可以变大变小，但是无论如何游标不能超出尺的长度。同理，若存储栈的长度为StackSize（最大容量），则栈顶位置top必须小于StackSize。当栈存在一个元素时，top等于0（top等于的数值的地址下标），因此通常把空栈的判定条件定为top=-1；

栈的实现一般可以使用数组作为顺序栈存储或者链表实现，相对而言数组的结构实现更优一些，因为数组尾插尾删的效率更高：简单，方便，但易产生溢出（数组大小固定）。

上溢(overflow):栈已经满，又要压入元素

下溢(underflow):栈已经空，还要弹出元素

上溢是一种错误，使问题的处理无法进行；而下溢一般认为是一种结束条件，即问题处理结束。

2. 栈的链式存储结构

链式存储结构最大的好处就是没有空间的限制，可以通过指针指向将结点像以链式的形式把结点链接，我们熟悉的线性表就有链式存储结构。当然，栈同样有链式存储结构，栈的链式存储结构，简称链栈。

从图片可以看到，和单链表很像，拥有一个头指针top，又称作栈顶指针，所以此时就不再需要单链表里面的头结点了。故链栈是运算受限的单链表，只能在链表头部进行操作：因为给定链栈后，已知头结点的地址，在其后面插入一个新结点和删除首结点都十分方便，对应算法的时间复杂度均为O(1)。

对于链栈来说，基本不存在栈满的情况，除非计算机内存已经没有了可使用的空间，如果真的存在，那么计算机系统面临着即将死机崩溃的情况，而不是这个链栈是否溢出的问题了。

对于【空栈】来说，链表的定义是头指针指向NULL，而链栈是top=NULL。(top指向的结点S就是首元结点)

1.2基本操作

【顺序栈算法设计四要素】

1.栈空的条件：s->top==-1

2.栈满的条件：s->top==MaxSize-1(data数组的最大下标)

3.元素e进栈的操作：先将栈顶指针top增1，然后将元素e放在栈顶指针处

4.出栈的操作：先将栈顶指针top处的元素取出放在e中，然后将栈顶指针减1

【链栈算法设计四要素】

1.栈空的条件:s->next==NULL。

2.栈满的条件:由于只有内存溢出时才出现栈满,通常不考虑这样的情况,所以在链栈中可以看成不存在栈满。

3.元素e进栈的操作:新建一个结点存放元素e(由p指向它),将结点p插入头结点之后。

4.出栈的操作:取出首结点的data值并将其删除。

1.2.1表示

• 顺序栈的表示

动态分配利用指针来操作数组元素，静态分配利用下标来操作数组元素

//顺序栈的动态分配
typedef struct SqStack{ElemType* base;//栈底指针ElemType* top;//栈顶指针int stacksize;//栈可用最大容量
}SqStack;
//顺序栈的静态分配
typedef struct SqStack{ElemType data[Maxsize];//定长数组int top;//栈顶下标int stacksize;//栈可用最大容量
}SqStack;

/*栈的链式存储结构*/
/*构造节点*/
typedef struct StackNode{ElemType data;struct StackNode *next;
}StackNode, *LinkStackPrt;
/*构造链栈*/
typedef struct LinkStack{LinkStackPrt top;//构造链表int count;//栈可用最大容量
}LinkStack;

1.2.2初始化

【指针的偏移】两个指针相减的真正差值是要除以类型长度的，指针之间可以相减但不可以相加：两个同一类型的指针变量是可以相减的，同志们的意义表示两个指针指向的内存位置之间相隔多少个元素（注意是元素，不是字节数）。例如对于int类型指针p和p1,p1-p的意义表示它们之间相隔多少个int类型的元素。

栈的初始化是空栈，而顺序栈空栈的条件是top＝=base=-1，链栈空栈的条件是s->nex=NULL;

void InitStack(SqStack *&s)   //初始化顺序栈
{s=(SqStack *)malloc(sizeof(SqStack)); //分配一个顺序栈空间，首地址存放在s中s->top=-1;//或者是s->top=s->base       //栈顶指针置为1
} 

void InitStack(LinkStNode *&s)	//初始化链栈
{s=(LinkStNode *)malloc(sizeof(LinkStNode));s->next=NULL;
}

【判断栈是否为空】

bool StackEmpty(SqStack *s)		//判断顺序栈空否
{return(s->top==-1);
}
//也可以这样写
Status StackEmpty(SqStack S){if(S->top==S->base)return TRUE;elsereturn FALSE;
}

bool StackEmpty(LinkStNode *s)	//判断栈空否
{return(s->next==NULL);
}

【求顺序栈的长度】

int StackLength(SqStack S){return S->top-S->base;
}

1.2.3清空

清空栈中的数据元素，栈还保留着(如同判断是否是空栈)

Status ClearStack(SqStack S){//清空顺序栈if(S->base)//如果base存在S->top=S->base;return OK;
}

1.2.4销毁

Status DestroyStack(SqStack &S){//销毁顺序栈，直接把结构回归内存if(S->base){delete S->base;S->stacksize=0;s->base=S->top=NULL;}return TRUE;
}//更简单点写
void DestroyStack(SqStack *&s) //销毁顺序栈
{free(s);
}

void DestroyStack(LinkStNode *&s)	//销毁链栈
{LinkStNode *pre=s,*p=s->next;   //pre指向头结点，p指向首结点while (p!=NULL)                 //循环到p为空{	                            free(pre);                  //释放p结点pre=p;                      //pre，p同步后移p=pre->next;}free(pre);	//pre指向尾节点,释放其空间
}

1.2.5入栈

• 顺序栈入栈算法思路：1.判断是否栈满，若满则出错（上溢）2.元素e压入栈顶；3.栈顶指针加1

注意：每次入栈前，都需要判断栈是否已满

/*插入元素e为新的栈顶元素*/
bool Status Push(SqStack *S, ElemType e){//满栈if(S->top == MAXSIZE-1){return ERROR;}S->top++;   //栈顶指针增加一S->data[S->top] = e;    //将新插入元素赋值给栈顶空间//*S->top=e;    对top所指的空间进行操作return true;
}

• 链栈入栈算法思路：对于链栈的进栈push操作，不带头结点的头插，假设元素值为e的新节点是s，top为栈顶指针，S为栈顶。示意图如下：

【不带头结点的头插】因为不需要向下遍历访问，所以不要头节点更简单。不头插导致，存入顺序是3，2，1。尾插导致存入顺序是1，2，3.最终头指针都指向1.头插和尾插，他们处理的对象，有严格的逻辑先后关系，比如1，2，3。头指针要永远指向1。但是现在是栈，stack。它处理的对象只有进入的先后关系，没有逻辑先后。头插法的链表来实现栈；尾插法的链表来实现队列。

/*插入元素e为新的栈顶元素*/
bool Status Push(LinkStack *S, ElemType e){LinkStackPrt p = (LinkStackPrt)malloc(sizeof(StackNode));//生成新结点pp->data = e;       //将新结点数据域设置为ep->next = S->top;    //将新结点插入栈顶(原来栈的结点作为它的后继)S->top = p; //修改栈顶指针：将新的结点s赋值给栈顶指针S->count++;return true;
}

1.2.6出栈

• 顺序栈出栈算法思路：1.判断是否栈空，若满则出错（下溢）2.获取栈顶元素e；3.栈顶指针减1

bool Pop(SqStack *&s,ElemType &e)	 //出栈
{if (s->top==-1)		//栈为空的情况，即栈下溢出return false;e=s->data[s->top];  //取栈顶元素//e=*S->top;s->top--;           //栈顶指针增1return true;
} 

• 链栈出栈算法思路：链栈的出栈pop操作，也是很简单的三句操作。假设变量p用来存储要删除的栈顶结点（在移动top之前需要一个指针来指向被删除结点，删除但不能让他丢失 所以用p存储），将栈顶指针下移一位，最后释放p即可，如下图所示：
  

bool Status Pop(LinkStack *S, ElemType &e){LinkStackPtr p;if(s->next==NULL){//栈空的情况return ERROR;}e = S->top->data;//提取首结点的值p = S->top; //p指向首结点：将栈顶结点赋值给pS->top = S->top->next;  //删除首结点：使得栈顶指针下移一位，指向后一结点free(p);    //释放被删除结点的存储空间S->count--;return true;
}

1.2.7取栈顶

顺序栈取栈顶

bool GetTop(SqStack *s,ElemType &e)	 //取栈顶元素
{if (s->top==-1) 		//栈为空的情况，即栈下溢出return false;*e=s->data[s->top];      //记录栈顶元素return true;
}

链栈取栈顶算法思路:头指针本来就指向栈顶元素，直接将data域的值输出

bool GetTop(LinkStNode *s,ElemType &e)	//取栈顶元素
{	if (s->next==NULL)		//栈空的情况return false;e=s->next->data;       //提取首结点的值return true;
}

1.3共享栈

1.3.1定义

利用栈底位置相对不变的特征，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，如下图所示：

两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=MaxSize时1号栈为空；仅当两个栈顶指针相邻（top0+1=top1）时，判断为栈满。当0号栈进栈时top0先加1再赋值，1号栈进栈时top1先减一再赋值出栈时则刚好相反。

共享栈的空间结构

/*两栈共享空间结构*/
#define MAXSIZE 50  //定义栈中元素的最大个数
typedef int ElemType;   //ElemType的类型根据实际情况而定，这里假定为int
/*两栈共享空间结构*/
typedef struct{ElemType data[MAXSIZE];int top0;	//栈0栈顶指针int top1;	//栈1栈顶指针
}SqDoubleStack;

1.3.2进栈出栈

• 共享栈进栈

对于两栈共享空间的push方法，我们除了要插入元素值参数外，还需要有一个判断是栈0还是栈1的栈号参数stackNumber。

/*插入元素e为新的栈顶元素*/
Status Push(SqDoubleStack *S, Elemtype e, int stackNumber){if(S->top0+1 == S->top1){   //栈满return ERROR;}if(stackNumber == 0){   //栈0有元素进栈S->data[++S->top0] = e; //若栈0则先top0+1后给数组元素赋值}else if(satckNumber == 1){ //栈1有元素进栈S->data[--S->top1] = e; //若栈1则先top1-1后给数组元素赋值}return OK;
}

• 共享栈出栈

/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
Status Pop(SqDoubleStack *S, ElemType *e, int stackNumber){if(stackNumber == 0){if(S->top0 == -1){return ERROR;   //说明栈0已经是空栈，溢出}*e = S->data[S->top0--]; //将栈0的栈顶元素出栈，随后栈顶指针减1}else if(stackNumber == 1){if(S->top1 == MAXSIZE){return ERROR;   //说明栈1是空栈，溢出}*e = S->data[S->top1++];    //将栈1的栈顶元素出栈，随后栈顶指针加1}return OK;
}

二.队列

2.1定义

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)的特点。
就像人们排队一样，讲究先来后到，先排队的人享受完服务，先离开。

• 队头：进行删除操作的一端。
• 队尾：进行插入操作的一端。
• 入队列：队列的插入操作，入数据在队尾。
• 出队列：队列的删除操作，出数据在队头。

顺序队列和链式队列

队列也可以用数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列是数组头删，效率会比较低。

队列也分为非循环队列和循环队列，可以用数组或链表实现。下面主要介绍用链表实现的普通的非循环队列。

1. 队列的顺序存储结构

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：

队头指针 front：指向队头元素；

队尾指针 rear： 指向队尾元素的下一个位置。

队列的顺序存储类型可描述为:

//静态分配存储空间
#define MAXSIZE 50	//定义队列中元素的最大个数
typedef struct{ElemType data[MAXSIZE];	//存放队列元素int front,rear;    //队头和队尾指针
}SqQueue;
//动态分配存储空间
#define MAXSIZE 50	//定义队列中元素的最大个数
typedef struct{QElemType* base;	//存放队列元素int front,rear;    //队头和队尾指针
}SqQueue;

溢出：当rear=MAXQSIZE时，发生溢出；若front=0,rear=MAXQSIZE时，再入队是真溢出；若front不等于0，rear=MAXQSIZE是再入队是假溢出。

2. 队列的链式存储结构

在这样的链队中只允许在单链表的表头进行删除操作(出队)和在单链表的表尾进行插入操作(进队)，因此需要使用队头指针front和队尾指针rear 两个指针，用 front 指向队首结点，用rear指向队尾结点。和链栈一样，链队中也不存在队满上溢出的情况。链队的存储结构如图所示：

#define MAXSIZE 50	//定义队列中元素的最大个数
typedef struct Qnode{//链式存储队列结点QElemType data;//存放元素stuct Qnode* next;//下一个结点指针
}QNode;//链队数据结点的类型
typedef struct* QuenePtr;typedef struct {//链式队列QuenePtr front;//队头指针QuenePtr reaR;//队尾指针
}LinkQueue;

?为什么同样都需要在头部操作，链栈不需头结点，链队和单链表需要头结点

链式队列，你的头结点是要不断出队的，也就是说你的头结点是不断变化的。而单链表是需要通过头结点来访问的，所以必须有头

那我们思考下： 队列的实现使用顺序结构还是链式结构好？
其实， 选择哪种方式取决于具体的需求：

• 顺序结构（数组）：优点是访问元素的时间复杂度为O(1)，适合队列的插入和删除操作通常在队列的一端进行（即“先进先出”FIFO）。然而，当队列满时，添加新元素需要移动所有后续元素，空间效率较低，且不适合动态扩容。
• 链式结构（链表）：链表则更灵活，能够动态地增加或减少容量，无需预先设定大小。对于频繁的插入和删除操作（尤其是中间位置），链表表现更好，因为只需要修改相邻节点的指针。但是，访问任意位置的元素时间复杂度为O(n)。

总的来说，如果队列的长度变化不大，且经常从队列前端进行操作，顺序结构可能是更好的选择；如果队列长度可能会增长并且有频繁的随机访问需求，或者频繁在队列中部插入和删除，那么链式结构会更有优势。

循环队列

循环队列是一种特殊的线性表数据结构，它在队列的一端添加元素，在另一端删除元素。与普通的队列（先进先出，FIFO）不同的是，循环队列的最后一个位置之后紧跟着第一个位置，形成了一个首尾相连的闭环。当试图从队列尾部删除元素而队列为空时，不会引发错误，而是会自动跳转到队列头部开始。相反，当试图从队列头部添加元素而队列已满时，也不会溢出，而是会替换掉队尾的第一个元素。

• 环形队列首尾相连后，当队尾指针rear=MaxSize-1后，再前进一个位置就到达0，于是就可以使用另一端的空位置存放队列元素了。实际上存储器中的地址总是连续编号的，为此采用数学上的求余运算（％）来实现：(定义和顺序队列一样)

队头指针front循环增1：front=(front+1)%MaxSize
队尾指针rear循环增1：rear=(rear+1)%MaxSize

循环队列的优势在于它能够有效地利用有限的空间，避免了普通数组在队列满时需要动态扩容的问题。但是，由于其内部逻辑相对复杂，可能会增加一些额外的操作开销，如判断队列是否满或空、元素移动等。

2.2基本操作

【顺序队列的四个要素】

• 队空的条件:q->front==q->rear。
• 队满的条件：q－>rear＝＝MaxSize－1(data数组的最大下标)。
• 元素e进队的操作：先将 rear增1，然后将元素e 放在 data数组的rear位置。
• 出队的操作：先将 front增1，然后取出 data 数组中front位置的元素。(先处理再移动指针)

【链表队列的四个要素】

• 队空的条件:q->rear == NULL(也可以为q->front==NULL)。
• 队满的条件：不考虑。
• 元素e进队的操作：新建一个结点存放元素e(由p指向它)，将结点 p插入作为尾结点。
• 出队的操作：取出队首结点的 data 值并将其删除。

【循环队列的四个要素】

• 队空条件：q->rear=q->front
• 队满条件：(q->rear+1)%MaxSize=q->front
• 进队操作：队尾循环进1
• 出队操作：队头循环进1

2.2.1初始化

void InitQueue(SqQueue &q)//顺序队列初始化
{	q=(SqQueue *)malloc (sizeof(SqQueue));q->front=q->rear=-1;
}

• 链式队列初始化

void InitQueue(LinkQueue *Q){//链式队列初始化Q->front = Q->rear = (LinkNode)malloc(sizeof(LinkNode));	//建立头结点Q->front->next = NULL;	//初始为空
}

bool InitQueue(SqQueue &q)		//循环初始化队列q
{	q=(SqQueue *)malloc (sizeof(SqQueue));if(!Q.base)exit(OVERFLOW);//存储分配失败q->front=q->rear=0;//头指针尾指针置为0，队列为空return true;
}

2.2.2判空

bool QueueEmpty(SqQueue *q)				
{return(q->front==q->rear);
}

• 链式队列的判空

链式队列有头结点，所以判空如下：

bool QueueEmpty(LinkQuNode *q)//链式队列判空	
{return(q->rear==NULL);//
}

• 循环队列

区别队空和队满的其他解决方案：

1. 另外设一个标志以区别队空，队满
2. 另设一个变量，记录元素个数
3. 少用一个元素空间
   

bool QueueEmpty(SqQueue *q)	//判断队q是否空
{return(q->front==q->rear);
}

2.2.3求队列长度

• 顺序队列

int QueueLength(SqQueue Q){return((Q->rear-Q->front)%MAXQSIZE);
}

• 循环队列：Q->rear-Q->front相减会出现负数，所以Q->rear-Q->front+MAXQSIZE

int QueueLength(SqQueue Q){return((Q->rear-Q->front+MAXQSIZE)%MAXQSIZE);
}

2.2.4取队头元素

• 循环队列

SElemType GetHead(SqQuere Q){if(Q->front!=Q->rear)//队列不为空return Q->base[Q->front];//返回队头指针元素的值，队头指针不变
}

• 链式队列

链式队列取头结点的下一个结点中的元素。

bool Status GetHead(LinkQueue Q,QElemType &e){if(Q->front==Q->rear)return ERROR;e=Q->front->next->data;return true;
}

2.2.5销毁

void DestroyQueue(SqQueue *&q)			
{free(q);
}

• 链式队列的销毁

算法思想：从队头结点开始，依次释放所有结点

void DestroyQueue(LinkQuNode *&q)	//销毁队列q
{DataNode *pre=q->front,*p;      //p指向队首结点if (pre!=NULL)			{	p=pre->next;                //p指向pre结点的后继结点while (p!=NULL)             //p不空时循环{	free(pre);              //释放pre结点pre=p;p=p->next;        //p，pre同步后移}free(pre);                  //释放最后一个数据结点}free(q);				        //释放链队结点占用空间
}

void DestroyQueue(SqQueue *&q)	//循环队列
{free(q);
}

2.2.6进队

bool enQueue(SqQueue *&q,ElemType e)	//进队
{	if (q->rear==MaxSize-1)				//队满上溢出return false;					//返回假q->rear++;							//队尾增1q->data[q->rear]=e;					//rear位置插入元素ereturn true;						//返回真
}

• 链式队列进队

Status EnQueue(LinkQueue *Q, ElemType e){LinkNode s = (LinkNode)malloc(sizeof(LinkNode));s->data = e;//在data域存放要插入的值s->next = NULL;Q->rear->next = s;	//把拥有元素e新结点s赋值给原队尾结点的后继Q->rear = s;	//把当前的s设置为新的队尾结点return OK;
}

bool enQueue(SqQueue *&q,ElemType e)	//进队
{	if ((q->rear+1)%MaxSize==q->front)	//队满上溢出return false;q->data[q->rear]=e;//新元素加入队尾q->rear=(q->rear+1)%MaxSize;//队尾指针+1return true;
}

2.2.7出队

bool deQueue(SqQueue *&q,ElemType &e)	//出队
{	if (q->front==q->rear)				//队空下溢出return false;q->front++;e=q->data[q->front];return true;
}

• 链式队列出队

出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点。

/*若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR*/
Status DeQueue(LinkQueue *Q, Elemtype *e){LinkNode p;if(Q->front == Q->rear){//判空return ERROR;}p = Q->front->next;	//将欲删除的队头结点（头结点的下溢结点）暂存给p*e = p->data;	//将欲删除的队头结点的值赋值给eQ->front->next = p->next;	//将原队头结点的后继赋值给头结点后继//若删除的队头是队尾，则删除后将rear指向头结点if(Q->rear == p){	//如果要删除的是尾结点Q->rear = Q->front;}free(p);return OK;
}

bool deQueue(SqQueue *&q,ElemType &e)	//循环队列出队
{	if (q->front==q->rear)		//队空下溢出return false;e=q->data[q->front];q->front=(q->front+1)%MaxSize;return true;
}

2.3双端队列

1、定义
双端队列是指允许两端都可以进行入队和出队操作的队列，如下图所示。其元素的逻辑结构仍是线性结构。将队列的两端分别称为前端和后端，两端都可以入队和出队。

在双端队列进队时，前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列中前端进的元素的后面
2、特殊的双端队列
在实际使用中，根据使用场景的不同，存在某些特殊的双端队列。

输出受限的双端队列：允许在一端进行插入和删除， 但在另一端只允许插入的双端队列称为输出受限的双端队列，如下图所示。

输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列称为输入受限的双端队列，如下图所示。若限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻接的栈。

总结

栈和队列都是一种特殊的线性表。

• 栈的特点：后进先出，只能在表尾进行插入和删除。
• 队列的特点：先进先出，只能在表头删除，在表尾插入。

它们都可以用顺序存储和链式存储的方式。

栈常用顺序存储结构即数组的方式，因为数组的尾插尾删效率高，但可能会存在频繁开辟内存空间和内存空间浪费的问题。而栈的链式存储结构，解决了空间浪费的问题，但每个节点都存放一个指针域，也会存在一定的内存开销，并且在每次申请和释放节点的过程中也存在一定的时间开销。

队列常用链式存储结构即链表的方式，比链表多定义一个尾指针，解决尾插效率低的问题，并且不存在空间浪费。 而队列的顺序存储结构，由于插入需要挪动数据，效率低下，但循环队列可以解决这个问题，时间复杂度从O(N)变成了O(1)，但仍存在内存空间浪费的问题。