数据结构入门-栈和队列

发布日期: 2022-09-10

更新日期: 2022-09-12

文章字数: 6.8k

阅读时长: 26 分

阅读次数:

栈

**后进先出（Last In First Out，LIFO）**的线性序列，称为“栈”。栈也是一种线性表，只不过它是操作受限的线性表，只能在一端进出操作。

进出的一端称为栈顶（top），另一端称为栈底（base）。栈可以用顺序存储，也可以用链式存储，分别称为顺序栈和链栈。

顺序栈：

顺序栈需要两个指针，base 指向栈底，top 指向栈顶。栈定义好了之后，还要先定义一个最大的分配空间，顺序结构都是如此，需要预先分配
空间。

注意：栈只能在一端操作，后进先出，是人为规定的，也就是说不允许在中间查找、取值、插入、删除等操作。

顺序栈本身是顺序存储的，有人就想：我偏要从中间取一个元素，不行吗？那肯定可以，但是这样做，就不是栈了。

初始化：

初始化一个空栈，动态分配 Maxsize 大小的空间，用 S.top 和 S.base 指向该空间的基地址
注意判断空间分配是否成功

#include<iostream>
using namespace std;

#define Maxsize 100  //预先分配空间，这个数值根据实际需要预估确定；

typedef struct SqStack {
	int *base; //栈底指针
	int *top; //栈顶指针
}SqStack;
bool InitStack(SqStack &S) //构造一个空栈S
{
	S.base=new int[Maxsize];//为顺序栈分配一个最大容量为Maxsize的空间
	if(!S.base)    //空间分配失败
		return false;
	S.top=S.base;  //top初始为base，空栈
	return true;
}

入栈：

入栈前要判断是否栈满，如果栈已满，则入栈失败；否则将元素放入栈顶，栈顶指针向上移动一个位置（top++）。

bool Push(SqStack &S,int e) // 插入元素e为新的栈顶元素
{
	if(S.top-S.base==Maxsize) //栈满
		return false;
	*(S.top++)=e; //元素e压入栈顶，然后栈顶指针加1，等价于*S.top=e; S.top++;
	return true;
}

出栈：

出栈前要判断是否栈空，如果栈是空的，则出栈失败；否则将栈顶元素暂存给一个变量，栈顶指针向下移动一个位置（top−−）。

栈顶元素所在的位置实际上是 S.top −1，因此把该元素取出来，暂存在变量 e 中，然后 S.top 指针向下移动一个位置。
因此可以先移动一个位置，即− −S.top，然后再取元素。

因为顺序存储删除一个元素时，并没有销毁该空间，所以 4 其实还在那个位置，只不过下次再有元素进栈时，就把它覆盖了。

相当于该元素已出栈，因为栈的内容是 S.base 到 S.top−1。

bool Pop(SqStack &S,int &e) //删除S的栈顶元素，暂存在变量e中
{
	if(S.base==S.top) //栈空
		return false;
	e=*(--S.top); //栈顶指针减1，将栈顶元素赋给e
	return true;
}

取栈顶元素：

取栈顶元素和出栈不同。取栈顶元素只是把栈顶元素复制一份，栈顶指针未移动，栈内元素个数未变。

而出栈是指栈顶指针向下移动一个位置，栈内不再包含这个元素。

int GetTop(SqStack S) //返回S的栈顶元素，栈顶指针不变
{
	if(S.top!=S.base)  //栈非空
		return *(S.top-1); //返回栈顶元素的值，栈顶指针不变
    else
        return -1;
}

链栈：

链栈每个节点的地址是不连续的，只需要一个栈顶指针即可。

链栈的每个节点都包含两个域：数据域和指针域。是不是和单链表一模一样？可以把链栈看作一个不带头节点的单链表，但只能在头部进行插入、删除、取值等操作，不可以在中间和尾部操作。

初始化：

初始化一个空的链栈是不需要头节点的，因此只需要让栈顶指针为空即可。

#include<iostream>
using namespace std;

typedef struct Snode{
	int data; //数据域
	struct Snode *next; //指针域
}Snode,*LinkStack;

bool InitStack(LinkStack &S)//构造一个空栈S
{
	S=NULL;
	return true;
}

入栈：

入栈是将新元素节点压入栈顶。因为链栈中第一个节点为栈顶，因此将新元素节点插到第一个节点的前面，然后修改栈顶指针指向新节点即可。

生成新节点。入栈前要创建一个新节点，将元素 e 存入该节点的数据域。
将新元素节点插到第一个节点的前面，然后修改栈顶指针指向新节点。
- p->next=S：将 S 的地址赋值给 p 的指针域，即新节点 p 的 next 指针指向 S。
- S=p：修改新的栈顶指针为 p。

bool Push(LinkStack &S,int e) //在栈顶插入元素e
{
	LinkStack p;
	p=new Snode; //生成新结点
	p->data=e; //将e放在新结点数据域
	p->next=S; //将新结点的指针域指向S，即将S的地址赋值给新结点的指针域
	S=p;    //修改栈顶指针为p
	return true;
}

出栈：

出栈就是把栈顶元素删除，让栈顶指针指向下一个节点，然后释放该节点空间。

p=S：将 S 的地址赋值给 p，即 p 指向栈顶元素节点。
S=S->next：将 S 的后继节点的地址赋值给 S，即 S 指向它的后继节点。
delete p：最后释放 p 指向的节点空间，即 delete p。

bool Pop(LinkStack &S,int &e) //删除S的栈顶元素，用e保存其值
{
	LinkStack p;
	if(S==NULL) //栈空
		return false;
	e=S->data;  //将栈顶元素赋给e
	p=S;  //用p保存栈顶元素地址，以备释放
	S=S->next;  //修改栈顶指针，指向下一个结点
	delete p;  //释放原栈顶元素的空间
	return true;
}

取栈顶元素：

取栈顶元素和出栈不同，取栈顶元素只是把栈顶元素复制一份，栈顶指针并没有改变。而出栈是指删除栈顶元素，栈顶指针指向了下一个元素。

int GetTop(LinkStack S) //返回S的栈顶元素，不修改栈顶指针
{
	if(S!=NULL) //栈非空
		return S->data; //返回栈顶元素的值，栈顶指针不变
    else
        return -1;
}

顺序栈和链栈的所有基本操作都只需要常数时间，所以在时间效率上难分伯仲。

在空间效率方面，顺序栈需要预先分配固定长度的空间，有可能造成空间浪费或溢出；链栈每次只分配一个节点，除非没有内存，否则不会出现溢出，但是每个节点需要一个指针域，结构性开销增加。

因此，如果元素个数变化较大，可以采用链栈；反之，可以采用顺序栈。在实际应用中，顺序栈比链栈应用更广泛。

队列

这种**先进先出（First In First Out，FIFO）**的线性序列，称为“队列”。队列也是一种线性表，只不过它是操作受限的线性表，只能在两端操作：一端进，一端出。

进的一端称为队尾（rear），出的一端称为队头（front）。

顺序队列：

队列的顺序存储采用一段连续的空间存储数据元素，并用两个整型变量记录队头和队尾元素的下标。顺序队列定义好了之后，还要先定义一个最大的分配空间，顺序结构都是如此，需要预先分配空间。

注意：队列只能在一端进、一端出，不允许在中间查找、取值、插入、删除等操作，先进先出是人为规定的，如果破坏此规则，就不是队列了。

入队和出队操作：

开始时为空队，Q.front = Q.rear:
元素进队，放入队尾 Q.rear 的位置，然后 Q.rear 后移一位：

元素出队，队头 Q.front 后移一位：
若此时队尾 Q.rear 已经超过了数组的最大下标，无法再进队，但是前面有空间却出现了队满的情况，这种情况称为“假溢出”：
为了解决“假溢出”，此时已经超过了数组的最大下标，即 Q.rear+1=Maxsize（最大空间数 6），那么如果前面有空闲，Q.rear 可以转向前面下标为 0 的位置：
当队列空间存满时，出现一个问题Q.front=Q.rear，这和队空的条件一模一样，无法区分到底是队空，还是队满。有两种解决方法：
- 一种办法是设置一个标志，标记队空和队满。
- 另一种办法是浪费一个空间，当队尾 Q.rear 的下一个位置 Q.front 时，就认为是队满。

上述到达尾部又向前存储的队列称为循环队列，为了避免“假溢出”，顺序队列通常采用循环队列。

循环队列：

队空：

无论队头和队尾在什么位置，只要 Q.rear 和 Q.front 指向同一个位置，就认为是队空。

Q.front == Q.rear

队满：

在此采用浪费一个空间的方法，当队尾 Q.rear 的下一个位置 Q.front 时，就认为是队满。

临界状态：

但是 Q.rear 向后移动一个位置（Q.rear+1）后，很有可能超出了数组的最大下标，这时它的下一个位置应该为 0:

队列的最大空间为 Maxsize，当 Q.rear=Maxsize−1 时，Q.rear+1=Maxsize。而根据循环队列的规则，Q.rear 的下一个位置为 0 才对，怎么才能变成 0 呢？

可以考虑取余运算，即(Q.rear+1)%Maxsize=0。而此时 Q.front=0，即(Q.rear+1)%Maxsize=Q.front，此时为队满的临界状态。

一般状态：

假如最大空间数 Maxsize=100，当 Q.rear=1 时，Q.rear+1=2。取余后，(Q.rear+1)%Maxsize=2，而此时 Q.front=2，即(Q.rear+1)%Maxsize=Q.front。

队满的一般状态也可以采用此公式判断队满。因为一个不大于 Maxsize 的数与 Maxsize 取余运算，结果仍然是该数本身，所以一般状态下，取余运算没有任何影响。

只有在临界状态（Q.rear+1=Maxsize）下，取余运算(Q.rear+1)%Maxsize 才会变为 0。

(Q.rear+1)%Maxsize == Q.front

初始化：

首先分配一个大小为 Maxsize 的空间，然后令 Q.front=Q.rear=0，即队头和队尾为 0，队列为空。

#include<iostream>
using namespace std;
#define Maxsize 100

typedef  struct SqQueue{
	int *base; //基地址
	int front,rear; //头指针,尾指针
}SqQueue;

//循环队列的初始化
bool InitQueue(SqQueue &Q)//注意使用引用参数，否则出了函数，其改变无效
{
	Q.base=new int[Maxsize];//分配空间
	if(!Q.base) return false;
	Q.front=Q.rear=0; //头指针和尾指针置为零，队列为空
	return true;
}

入队：

入队时，首先将元素 x 放入 Q.rear 所指空间，然后 Q.rear 后移一位。

当 Q.rear 后移一位时，为了处理临界状态（Q.rear+1=Maxsize），需要加 1 后取余运算。

//循环队列的入队
bool EnQueue(SqQueue &Q,int e)//将元素e放入Q的队尾
{
	if((Q.rear+1)%Maxsize==Q.front) //尾指针后移一位等于头指针，表明队满
		return false;
	Q.base[Q.rear]=e; //新元素插入队尾
	Q.rear=(Q.rear+1)%Maxsize; //队尾指针加1
	return true;
}

出队：

先用变量保存队头元素，然后队头 Q.front 后移一位。

当 Q.front 后移一位时，为了处理临界状态（Q.front+1=Maxsize），需要加 1后取余运算。

//循环队列的出队
bool DeQueue(SqQueue &Q, int &e) //删除Q的队头元素，用e返回其值
{
	if(Q.front==Q.rear)
		return false; //队空
	e=Q.base[Q.front]; //保存队头元素
	Q.front=(Q.front+1)%Maxsize; //队头指针加1
	return true;
}

取队头元素：

取队头元素时，只是把队头元素数据复制一份即可，并未改变队头位置，因此队列中的内容没有改变。

//取循环队列的队头元素
int GetHead(SqQueue Q)//返回Q的队头元素，不修改队头指针
{
	if(Q.front!=Q.rear) //队列非空
		return Q.base[Q.front];
    return -1;
}

队列元素个数计算：

循环队列中的内容实际上为 Q.front～Q.rear−1 这一区间的数据元素，但是不可以直接用两个下标相减得到。因为队列是循环的，所以存在两种情况。

Q.rear≥Q.front:
Q.rear<Q.front:

此时，Q.rear=4，Q.front=Maxsize−2，Q.rear-Q.front=6−Maxsize。但是我们可以看到循环队列中的元素实际上为 6 个，那怎么办呢？当两者之差为负数时，可以将差值加上 Maxsize计算元素个数，即 Q.rear−Q.front+Maxsize=6−Maxsize+Maxsize=6，元素个数为 6。

因此，在计算元素个数时，可以分两种情况判断。
1）Q.rear≥Q.front：元素个数为 Q.rear−Q.front。
2）Q.rear<Q.front：元素个数为 Q.rear−Q.front+Maxsize。

也可以采用取余的方法把两种情况巧妙地统一为一个语句:

队列中元素个数为：(Q.rear-Q.front+Maxsize)%Maxsize

%Maxsize 是为了防止 Q.rear-Q.front 为正数的情况，

+Maxsize 是为了防止 Q.rear-Q.front为负数的情况

求队列的长度：

通过前面的分析，我们已经知道循环队列中元素个数为：(Q.rear−Q.front+Maxsize)%Maxsize，循环队列中元素个数即为循环队列的长度。

//循环队列的长度
int QueueLength(SqQueue Q)
{
	return (Q.rear-Q.front+Maxsize)%Maxsize;
}

链队列：

链队列类似一个单链表，需要两个指针 front 和 rear 分别指向队头和队尾。从队头出队，从队尾入队，为了出队时删除元素方便，可以增加一个头节点。

注意：链队列需要头节点

初始化：

链队列的初始化，即创建一个头节点，头指针和尾指针指向头节点。

#include<iostream>
using namespace std;

typedef  struct Qnode{
  int data;
  struct Qnode *next;
}Qnode,*Qptr;

typedef struct{
  Qnode *front;
  Qnode *rear;
}LinkQueue;

//链队的初始化
void InitQueue(LinkQueue &Q)//注意使用引用参数，否则出了函数，其改变无效
{
	Q.front=Q.rear=new Qnode; //创建头结点，头指针和尾指针指向头结点
	Q.front->next=NULL;
}

入队：

先创建一个新节点，将元素 e 存入该节点的数值域。
然后将新节点插入队尾，尾指针后移。
- Q.rear->next=s：把 s 节点的地址赋值给队列尾节点的 next 域，即尾节点的 next 指针指向 s。
- Q.rear=s：把 s 节点的地址赋值给尾指针，即尾指针指向 s，尾指针永远指向队尾。

//链队列的入队
void EnQueue(LinkQueue &Q,int e)//将元素e放入队尾
{
	Qptr s;
	s=new Qnode;
	s->data=e;
	s->next=NULL;
	Q.rear->next=s;//新元素插入队尾
	Q.rear=s;     //队尾指针后移
}

出队：

出队相当于删除第一个数据元素，即将第一个数据元素节点跳过去。

首先用 p 指针指向第一个数据节点，然后跳过该节点，即 Q.front->next=p->next。
若队列中只有一个元素，删除后需要修改队尾指针。

//链队列的出队
bool DeQueue(LinkQueue &Q,int &e) //删除Q的队头元素，用e返回其值
{
	Qptr p;
	if(Q.front==Q.rear)//队空
		return false;
	p=Q.front->next;
	e=p->data;     //保存队头元素
	Q.front->next=p->next;
	if(Q.rear==p) //若队列中只有一个元素，删除后需要修改队尾指针
        Q.rear=Q.front;
	delete p;
	return true;
}

取队头元素：

队头实际上是 Q.front->next 指向的节点，即第一个数据节点，队头元素就是将该节点的数据域存储的元素。

//取循环队列的队头元素
int GetHead(LinkQueue Q)//返回Q的队头元素，不修改队头指针
{
	if (Q.front!=Q.rear) //队列非空
		return Q.front->next->data;
    return -1;
}

栈和队列的应用：

数制的转换：

**题目：**将一个十进制数 n 转换为二进制数。

思路：

十进制数转换为二进制，可以采用辗转相除、取余数的方法得到。例如十进制数 11 转二进制。先求余数 11%2=1，求商 11/2=5，然后用商 5 再求余数，求商，直到商为 0，结束。

先求出的余数是二进制数的低位，后求出的余数是二进制数的高位，将得到的余数逆序输出就是所要的二进制数，即 11 的二进制数为 1011。如何将余数逆序输出呢？

逆序输出正好符合栈的先入后出性质，因此可以借助栈来实现。

步骤：

初始化一个栈 S。
如果 n!=0，将 n%2 入栈 S，更新 n=n/2。
重复运行第 2 步，直到 n=0 为止。
如果栈不空，弹出栈顶元素 e，输出 e，直到栈空。

#include<iostream>
typedef int Elemtype;//先类型定义为int 
#include"sqstack.h"//引入自定义头文件,源码目录下名为sqstack.h的文件  
using namespace std;

void binaryconversion(int n)
{
    SqStack S;//定义一个栈S
    int e;
    InitStack(S);//初始化栈
    while(n)
    {
        Push(S,n%2);
        n=n/2;
    }
    while(!Empty(S))//如果栈不空
    {
        Pop(S,e);//出栈
        cout<<e<<"\t";//输出栈顶元素
    }
}

算法复杂度分析：

每次取余后除以 2，n 除以 2 多少次变为 1，那么第一个 while 语句就执行多少次。假设执行 x 次，则 n/2x=1，x=log2n。因此，时间复杂度为 O(log2n)，使用的栈空间大小也是 log2n，空间复杂度也为 O(log 2n)。

回文判定：

**题目：**回文是指正读反读均相同的字符序列，如“abba”和“abcscba”均是回文，也就是说字符串沿中心线对称。试写一个算法判定给定的字符串是否为回文。

思路：

**回文是中心对称的，可以将字符串前一半入栈，然后，栈中元素和字符串后一半进行比较。**即将第一个出栈元素和后一半串中第一个字符比较，若相等，则再将出栈一个元素与后一个字符比较…直到栈空为止，则字符序列是回文。

步骤：

初始化一个栈S。
求字符串长度，将前面一半的字符依次入栈 S。
如果栈不空，弹出栈顶元素 e，与字符串后一半元素比较。**若 n 为奇数，则跳过中心点，比较中心点后面的元素。**如果元素相等，则继续比较直到栈空，返回 true；如果元素不等，返回 false。

#include<iostream>
#include<cstring>
typedef char Elemtype;//先类型定义为char 
#include"sqstack.h"//引入自定义头文件,源码目录下名为sqstack.h的文件   

using namespace std;

bool palindrome(char *str)//判断字符串是否为回文
{
    SqStack S;//定义一个栈S
    int len,i;
    char e;
    len=strlen(str);//返回字符串长度
    InitStack(S);//初始化栈
    for(i=0;i<len/2;i++)//将字符串前一半依次入栈
        Push(S,str[i]);
    if(len%2==1)//字符串长度为奇数，跳过中心点
        i++;
    while(!Empty(S))//如果栈不空
    {
        Pop(S,e);//出栈
        if(e!=str[i])//比较元素是否相等
            return false;
        else
            i++;
    }
    return true;
}

算法复杂度分析：

如果字符串长度为 n，将前一半入栈，后一半依次和出栈元素比较，相当于扫描了整个字符串，因此时间复杂度为 O(n)，使用的栈空间大小是 n/2，空间复杂度也为 O(n)。

双端队列：

**题目：**设计一个数据结构，使其具有栈和队列两种特性。

思路：

栈是后进先出，队列是先进先出，如何具有这两种特性呢？
栈是在一端进出，队列是在一端进、另一端出，能否设计两端都可以进出呢？

允许两端都可以进行入队和出队的队列，就是双端队列

循环队列表示的双端队列，可以用环形形象地表达出来。双端队列和普通循环队列的区别如图所示。

双端队列包括前端和后端，可以从前端进入、前端出队、后端进队、后端出队。

步骤：

入队
- 前端进队时，先令 Q.front 前移一位，再将元素放入 Q.front 的位置，a、b、c 依次从前端进队。
- 后端进队时，先将元素放入 Q.rear 的位置，再令 Q.rear 后移一位，d 从后端进队。
出队
- 从后端出队，先令 Q.rear 前移一位，再将 Q.rear 位置元素取出。
- 从前端出队，先将 Q.front 位置元素取出，再令 Q.front 后移一位。

后端进、前端出或者前端进、后端出体现了先进先出的特点，符合队列的特性。

后端进、后端出或者前端进、前端出体现了后进先出的特点，符合栈的特性。

初始化：

初始化时，头指针和尾指针置为零，双端队列为空。

#include<iostream>
using namespace std;

#define Maxsize 100
typedef char ElemType;

typedef  struct SqQueue{
  ElemType base[Maxsize]; //一维数组存储，也可以设置指针动态分配空间
  int front,rear; //头指针,尾指针
}DuQueue;

//初始化
void InitQueue(DuQueue &Q)//注意使用引用参数，否则出了函数，其改变无效
{
	Q.front=Q.rear=0; //头指针和尾指针置为零，队列为空
}

判队满：

当队尾后移一位等于队头，表明队满。队尾后移一位即 Q.rear+1，加 1 后有可能等于Maxsize，此时下一个位置为 0，因此为处理临界状态，需要与 Maxsize 取余运算。

//判队满
bool isFull(DuQueue Q)
{
    if((Q.rear+1)%Maxsize==Q.front) //尾指针后移一位等于头指针，表明队满
	return true;
    else
       return false;
}

尾进：

尾部进队，即后端进队时，先将元素放入 Q.rear 位置，然后 Q.rear 后移一位，后移时为处理边界情况，需要加 1 后模 Maxsize 取余。

 //尾进
bool push_back(DuQueue &Q,ElemType e)
{
    if(isFull(Q))
        return false;
    Q.base[Q.rear]=e; //先放入
    Q.rear=(Q.rear+1)%Maxsize;//向后移动一位
    return true;
}

尾出：

尾部出队，即后端出队时，先将 Q.rear 前移一位，然后取出元素。前移一位即 Q.rear−1，当 Q.rear 为 0 时，Q.rear−1 为负值，因此加上 Maxsize，正好是 Maxsize−1 的位置。那么，Q.rear−1 为正值时，加上 Maxsize 就超过了下标范围，需要模 Maxsize 取余。

//尾出
bool pop_back(DuQueue &Q,ElemType &x)
{
    if(isEmpty(Q))
        return false;
    Q.rear=(Q.rear-1+Maxsize)%Maxsize;//向前移动一位
    x=Q.base[Q.rear]; //取数据
    return true;
}

头进：

头部进队，即前端进队时，先将 Q.front 前移一位，然后将元素先放入 Q.front 位置。队头前移一位即 Q.front−1，前移时为处理边界情况，需要加 Maxsize 再模 Maxsize 取余。

 //头进
bool push_front(DuQueue &Q,ElemType e)
{
    if(isFull(Q))
        return false;
    Q.front=(Q.front-1+Maxsize)%Maxsize;//先向前移动一位
    Q.base[Q.front]=e; //后放入
    return true;
}

头出：

头部进队，即前端出队时，先取出元素，然后 Q.front 后移一位，即 Q.front+1，后移时为处理边界情况，需要模 Maxsize 取余。

//头出
bool pop_front(DuQueue &Q,ElemType &x)
{
    if(isEmpty(Q))
        return false;
    x=Q.base[Q.front]; //取数据
    Q.front=(Q.front+1)%Maxsize;//向后移动一位
    return true;
}

取队头：

取队头是指将 Q.front 位置的元素取出来，Q.front 未改变。

//取队头
bool get_front(DuQueue Q,ElemType &x)
{
    if(isEmpty(Q))
        return false;
    x=Q.base[Q.front]; //取队头数据;
    return true;
}

取队尾：

因为 Q.rear 指针永远指向空，因此取队尾时，取 Q.rear 前面的那个位置，要想得到前面位置，为处理边界情况，需要加 Maxsize 再模 Maxsize取余。

注意：取队尾时，尾指针不移动。

//取队尾
bool get_back(DuQueue Q,ElemType &x)
{
    if(isEmpty(Q))
        return false;
    x=Q.base[(Q.rear-1+Maxsize)%Maxsize];
    return true;
}

求长度：

和普通循环队列求长度的方法一样，都是求从队头到队尾之间的元素个数。因为循环队列减法有可能有负值，因此需要加 Maxsize 再模 Maxsize 取余。

//求长度
int length(DuQueue Q)
{
    return (Q.rear-Q.front+Maxsize)%Maxsize;
}

遍历：

双端队列的遍历，即从头到尾输出整个队列中的元素，在输出过程中，队头和队尾并不移动，因此借助一个暂时变量即可。

//从头到尾输出整个队列元素（遍历）
void traverse(DuQueue Q)
{
    if(isEmpty(Q))
    {
       cout<<"DuQueue is empty"<<endl;
       return ;
    }
    int temp=Q.front;//设置一个暂存变量，头指针未移动
    while(temp!=Q.rear)
    {
       cout<<Q.base[temp]<<"\t";
       temp=(temp+1)%Maxsize;
     }
     cout<<endl<<"traverse is over!"<<endl;
}

技巧：后移时，加 1 模 Maxsize；前移时，减 1 加 Maxsize 再模 Maxsize。

输出受限的双端队列

允许在一端进队和出队，另一端只允许进队，这样的双端队列称为输出受限的双端队列。
输入受限的双端队列

允许在一端进队和出队，另一端只允许出队，这样的双端队列称为输入受限的双端队列。

栈和队列学习技巧：

栈和队列的比较：

栈解题技巧：

栈顶指针所指位置
- 在顺序栈中，栈顶指针指向的是栈顶元素的上一个位置，即空位置，取栈顶元素时要取*(S.top−1)才可以
- 入栈时，先把元素放入栈顶位置，然后栈顶指针后移，即*S.top++=e。
- 出栈时，栈顶指针前移，用变量暂存栈顶元素，即 e=−−S.top。
出栈只是栈顶指针移动，空间元素仍然存在，但下次入栈时会覆盖
本文以动态分配为例，静态分配的情况处理方式不同
- 静态分配是使用一个固定长度的数组存储数据，然后用一个 int 型的变量 top 指向栈顶，top 实际上是数组的下标。当栈空时，S.top=0。
- 入栈时，先把元素放入栈顶位置，然后栈顶指针后移，即 S.data[S.top++]=e。
- 出栈时，栈顶指针前移，用变量暂存栈顶元素，即 e=S.data[−−S.top]。
栈和队列的灵活运用：
- 栈具有后进先出的特性，可以利用此特性解决如逆序输出、括号匹配等问题。由于栈只能在一端操作，插入、删除都是在栈顶进行，不需要移动元素，因此大多使用顺序栈。
- 队列具有先进先出的特性，可以利用此特性解决一系列排队、先到先得等问题。在确定队列长度范围的情况下，大多使用循环队列。如果队列长度变化较大，则使用链队。

QT-7274

https://qt-7274.github.io/2022/09/10/shu-ju-jie-gou-ru-men-zhan-he-dui-lie/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 QT-7274 !

数据结构

数据结构入门-字符串

字符串的相关操作也是数据结构中的重要一环。

2022-09-14 数据结构

数据结构

Vue动画与过渡

本文介绍如何使用Vue框架进行动画渲染，以及和其他第三方库的结合。

2022-09-09 前端开发

前端 Vue

数据结构入门-栈和队列

栈

顺序栈：

初始化：

入栈：

出栈：

取栈顶元素：

链栈：

初始化：

入栈：

出栈：

取栈顶元素：

队列

顺序队列：

入队和出队操作：

循环队列：

队空：

队满：

临界状态：

一般状态：

初始化：

入队：

出队：

取队头元素：

队列元素个数计算：

求队列的长度：

链队列：

初始化：

入队：

出队：

取队头元素：

栈和队列的应用：

数制的转换：

思路：

步骤：

算法复杂度分析：

回文判定：

思路：

步骤：

算法复杂度分析：

双端队列：

思路：

步骤：

初始化：

判队满：

尾进：

尾出：

头进：

头出：

取队头：

取队尾：

求长度：

遍历：

栈和队列学习技巧：

栈和队列的比较：

栈解题技巧：

你的赏识是我前进的动力