开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 手写堆栈，队列 -> 正文阅读

[数据结构与算法]手写堆栈，队列

手写堆栈和队列

手写堆栈

堆栈是什么？

首先我们必须知道堆栈是什么？

堆栈的英文叫做stack，而stack还有盘子的意思，所以堆栈实际上就是像盘子一样。而盘子是什么样的咧，盘子就是一个个叠上去，之前放的都被压在下面，拿只能拿最上面一层。所以也就是先进后出（FILO），先进去的后拿出来，后进去的先拿进来。

如何实现堆栈

线性堆栈

线性的堆栈和队列其实本质都是数组。

堆栈说白了就是受限的数组，删除元素的时候只能在数组尾删除。所以我们需要什么，我们需要一个指向队尾的指针（或者说数组的长度，然后随时随刻知道队尾在哪）

所以怎么实现堆栈：

就是一个结构体，结构体中有一个数组，然后还有一个size（队尾指针）。

typedef struct  {
	DataType stack[MaxStackSize];//MAX是数组最大存储的容量
	int top;
}SeqStack;

初始化

void StackInitiate(SeqStack* S)
{
	S->top = 0;
}

初始化这里很重要，top可以设置为0或者-1。这在插入和删除时是不一样的。

当top设置为0时，则top表示的是下一个要插入的位置
当top设置为-1时，则top表示的目前的位置。

插入操作

int stackpush(SeqStack* q,int x) {

	if (q->top > MaxStackSize)
	{
		cout << "栈满无法插入" << endl;
		return 0;
	}
	else
	{
		q->stack[q->top] = x;
		q->top++;
		return 1;
	}
}

因为top是下一个要插入的位置，首以直接 q->stack[q->top] = x; 插入，插入完成后将top++，指向下一个插入的位置。

出栈（删除）


int stackpop(SeqStack* q,int *x) {

	if (q->top <=0)
	{
		cout << "栈已空无法删除" << endl;
		return 0;
	}
	else
	{
		 q->top--;
		 *x = q->stack[q->top];
		return 1;
	}
}

因为top指向的是下一个要插入的位置，所以实际上指的是空的，所以要删除时，先得把top减1，然后再赋值删除。

取栈顶元素

int stackTop(SeqStack* q, int* x) {

	if (q->top <= 0)
	{
		cout << "栈已空" << endl;
		return 0;
	}
	else
	{
		*x = q->stack[q->top-1];
		return 1;
	}
}

看着和出栈很像，但其实不同，取栈顶只是取，并没有删除，所以没有top–的操作，只是再括号内q->top-1,但这个表示的只是数值上的加减而已。

链式堆栈

链表的特点就是插入取出操作都比较方便，而链式堆栈就是限制了插入取出的链表。堆栈是插入删除都在同一个地方，那么想一下，是要插入删除都在链表头呢，还是在链表尾呢？

如果在链表尾，那么插入删除就在链表尾，你需要一个额外的空间去存放尾指针
而如果在链表头，则插入删除都在链表头，本来链表就是需要头指针这种东西，就不需要额外的内存空间了

链表(对链表已掌握熟悉的可以跳过这部分内容）

链表还会写吗？哈哈哈，好像有点忘了！

链表是什么？其实链表不重要，重要的是链表的节点。我们能写出来的不是链表，而是链表的节点，我们往链表的节点一直添加节点它就自动变成链表了。我们只要有链表的头节点，就能找到它后面的所有节点。

那么链表的节点是什么？是一个结构体（或者是一个类）
该结构体（类）中有自己存储的数据和指向自己本结构的指针。

java中的链表是这样的

public class ListNode{
int val；//表示数值
ListNode next；//表示下一个对象

c的链表

int struct snode
{
int data;
struct snode*next;
}LSNode;

不过要注意，链表分有头结点和无头结点两种。其实都可以。

如果带头结点，那么插入和删除，改变的都是头结点指向的那个节点。
如果没有带头节点，那么每次改变的都是头指针，你那么头指针参数必须设计成节点的双重指针类型，这样才能将头指针参数值的改变带回到调用参数中。

接下来就讲一下带头结点的链表

首先是初始化

void StackInitate(LSNode**head)
{
*head=(LSNode*)malloc(sizeof(LSNode));//头指针的地址
(*head)->next=NULL;
}
//上面的LSNode只是声明，并没有分配空间，定义才有分配空间
//所以下面才需要*head=(LSNode*)malloc(sizeof(LSNode));为其分配空间

其实这里初始化的时候，因为要对链表的头节点进行修改，链表的头结点是一个指针，要对指针修改，所以传进去的必须是二级指针。

（不要被这个head迷惑，后面有一些操作变量的名字也定义为head，但是却是不一样的）

比如说

插入

链表如何插入？
在正常的链表中，找到要插入的位置，生成新节点，赋值，然后插入

void ListPush(LSNode*head,i,x)//在头结点为head的链表中的第i个位置插入数据为x的节点
{
LSNode*q=head;
//这里必须要注意！！！i从0还是1开始，有没有头节点，j从-1还是0还是1开始while循环的条件有很大的区别
//但有一点是核心，就是要在位置i插入，就要找到i-1的节点
//下面以有头结点，i从0开始为例
j=-1;
while(q->next!=NULL&&j<i-1)//这里必然是q->next!=NULL,才能保证是指向最后一个节点，如果是q!=NULL,则是指向最后一个节点的下一个节点
{
q=q->next;
j++;
}
if(j!=i-1)
{
cout<<"插入的元素位置参数错！"<<endl;
return 0;
}
LSNode*new=（LSNode*）malloc（sizeof（LSNode））;
new->data=x;
new->next=q->next;
q->next=new;
return 1;
}

删除

void ListPop(LSNode*head,i,int *x)//在头结点为head的链表中的第i个位置删除节点
{
LSNode*q=head;
LSNode*s;
//这里必须要注意！！！i从0还是1开始，有没有头节点，j从-1还是0还是1开始while循环的条件有很大的区别
//但有一点是核心，就是要在位置i插入，就要找到i-1的节点
//下面以有头结点，i从0开始为例
j=-1;
while(q->next!=NULL&&q->next->next!=NULL&&j<i-1)
//这里要多一个q—>next->next!=NULL,为什么呢，因为后面需要用到它赋值，所以也就不能为空
{
q=q->next;
j++;
}
if(j!=i-1)
{
cout<<"删除的元素位置参数错！"<<endl;
return 0;
}
s=q->next;
*x=s—>data;
q->next=q->next->next;//(在物理意义上把该节点删除了）
free(s);
return 1;
}

取数据元素

void ListGet(LSNode*head,i,int *x)//在头结点为head的链表中的第i个位置取节点
{
LSNode*q=head;
LSNode*s;
j=-1;
while(q->next!=NULL&&j<i)//这里最大的特点就是 变成了j<i,为什么，因为取元素只要直接取就行，不需要找到前一个节点去操作
{
q=q->next;
j++;
}
if(j!=i-1)
{
cout<<"取元素位置参数错！"<<endl;
return 0;
}
*x=q—>data;
return 1;
}

撤销单链表

void Destory(SLNode **head)
{
SLNode*p,*p1;
p=*head;
while(p!=NULL)
{
p1=p;
p=p->next;
free(p1);
}
*head=NULL;
}

head

好，现在来讲讲一开始说到的head的问题，

初始化时：void StackInitate(LSNode**head)
插入时：void ListPush(LSNode*head,i,x)
虽然两个都是head，但是只是名称叫做head而已，代表的意义不同，第二个head才是实质意义上的头结点，而第一个head其实是头结点的指针。

所以实际上在构建的时候是这样构建的

SLNode*head;
ListInitiate(&head);

堆栈链表化

上面讲的是原本的链表，而堆栈链表其实就是在插入和删除的时候有限制，其它都和普通链表没有区别。

插入

void StackPush(LSNode*head,int x)
{
LSNode*q;
q=(LSNode*)malloc(sizeof(LSNode)));
q->data=x;
q->next=head->next;
head->next=q;
}

删除

void StackPush(LSNode*head,int *x)
{
LSNode*q;
q=head->next;
if(q==NULL)
{
cout<<"堆栈已空出错"<<endl;
return 0;
}
*x=q->data;
head->next=q->next;
free(q);
return 1;

}

手写队列

好吧，接下来讲一下队列是什么？

队列，顾名思义，就是队列，跟我们在排队一样，先排的人先到，先进先出（FIFO）。

既然知道了队列是这样，那么要如何实现队列呢？

线性队列

队列实质上也是一个数组（顺序表），然后在插入和删除时都有限制。

插入时只能从队尾进，而删除时只能从对头出。

但是从队头删除的时候，整个数组并不会往前移动，而是让删除的地方空着。

所以队列是一个数组加上两个指针，头指针和尾指针。

队列的结构

int struct{
int queue[MaxQueueSize];
int rear;//队尾指针
int front;//对头指针
int count;//计算器
//为什么还需要一个计算器呢？这就是队列与栈的区别，待会会讲到，实现队列需要多两个特性，一个是环状队列，一个是计算器
}

初始化

void QueueInitiate(SeqCQueue*Q)
{
Q->rear=0;
Q->front=0;
Q->count=0;
}

入队与出队

这里就涉及到队列的第一个特性，也就是循环（环状队列）

假溢出

假设这种情况：
在这里插入图片描述
队尾指向了数组的最尾，而队头删除了位置0和位置1的元素。

这时如果再插入的话，正常情况会提示数组已经满了，插不进去了，但是实际上这个队列还没满，因为前面有删除的，所以这就是著名的假溢出问题

如何解决假溢出问题，就是看成一个循环队列。如果队尾指针目前已经到6了，那么下一个就得重新到0。

那么如何实现呢？其实就是运用一个余数。

原本不循环，队尾加1就是rear+1；
现在循环，就变成(rear+1)&MaxQueueSize;//MaxQueueSize是数组长度
//比如上面例子，Size为7，那么当最后尾指针为6时，6+1&7就为0，下一个插入位置就是0；满足要求，而1，2，3这些小于7的数对7取余都等于本身。

既然讲到了假溢出问题，就顺便讲一下另一个问题。
就是队空和队满的判断

如果队列中没有元素，那么frontrear，此时是队空的标志，这是原本的情况。但是现在是循环队列，如果循环了一次，重新插满了，你会发现队满也是frontrear的情况。所以不好判断。

所以为了解决这个问题一般有三种方法

少用一个存储空间，则以队尾指针rear+1等于队头指针front为队列满的判断条件，此时队满的情况为（rear+1）&MaxQueueSize==front；
设置一个标签位，初始时tag=0，每当队列入队操作成功，就置tag=1；每当出队成功，就置tag=0；
设置一个计算器count，初始时设置count=0；每当入队成功，count++，每当出队成功count减1.
所以队空的条件是count=0；
队满的条件是count>0&&rear==front；

入队列

int QueueAppend(SeqCQueue*Q,int x)
{
if(Q->count>0&&Q->rear==Q->front)
{
cout<<"队列已满无法插入"<<endl;
return 0;
}
else{
Q->queue[Q->rear]=x;
Q->rear=(Q->rear+1)%MaxQueueSize;
Q->count++;
return 1;
}

出队列

int QueueAppend(SeqCQueue*Q,int *x)
{
if(Q->count==0)
{
cout<<"队列已空无法删除"<<endl;
return 0;
}
else{
*x=Q->queue[front]
Q->front=(Q->front+1)%MaxQueueSize;
Q->count--;
return 1;
}

取队首元素和判断是否空大同小异，就不赘述了。

链式队列

链式队列就是特殊的一种队列而已，这里要讨论的问题只有一个。

就是队列是一头进一头出，那么到底是要将链表的头当队列的头还是当队列的尾呢？

首先我们考虑插入，如果在链表头插入可以吗？

可以吗，时间复杂度是O1，那么在链表尾插入可以吗，可以，也是O1（因为我们会定义一个指针指向链表尾）

那么删除呢，在链表头删除可以吗，可以，时间复杂度是O1。
但是在链表尾删除可以吗，不太可以，虽然我们有队尾指针，我们可以删除队尾的节点，但是我们要让原本队尾前的节点指向空，但是我们如何获得这个节点呢，我们没有，我们必须从头指针一直循环到最后，时间复杂度是On。

所以总结下来，链表头作为队列的队头，执行删除操作。
链表尾作为队列的队尾，执行插入操作。
尾进头出

实现

不同于前面的链表和链式堆栈，这次队列必须有一个队头指针和队尾指针。

int struct qnode
{
int data;
struct qnode*next;
}LQNode;

int struct 
{
LQNode *front;
LQNode*rear;
}LQueue;

要记住，不同之处就是链式队列是一个由节点头指针和尾指针组成的结构体。（之前的链表只需要一个头指针就行）

初始化

void QueueInitiate(LQueue *Q)
{
Q->rear=NULL;
Q->front=NULL;
}

在这里插入图片描述

记住，尾进，头出

非空否

int QueueNotEmpty(LQueue)
{
if(Q->front==NULL) return 0;
else return 1;
}

//头出，如果头为空，代表没得出，代表为空

入队列

int  QueuePoP(LQueue *Q,int x)
{
LQNode*p=(LNode*)malloc(sizeof(LQNode)));
p->data=x;
p->next=NULL;

//原本这样 Q->rear->next=p;就行，但是如果一开始是空的，那么Q->rear为NULL,不可以。

所以要判断一开始空不空。

if(Q->front==NULL) Q->front=p;//如果为空，将p赋为头指针，因为头出，待会头才可以出，这样头就不空了。虽然此时rear还是NULL，但是没关系阿，下一次插入的时候，Q->front已经不为空了
else 
{Q->rear->next=p;
Q->rear=p;}
//记住，尾指针要记住移动
}

出队列

int  QueuePush(LQueue *Q,int* x)
{
LQNode*p;
if(Q->front==NULL) 
{
cout<<"无元素可出"<<endl;
return 0;
}
else{
*x=Q->front->data;
p=Q->front;
Q->front=Q->front->next;

//还有一点要注意的是：
//删除最后一个节点后，要置队尾指针为空
if(Q->front==NULL)Q->rear=NULL;

free(p);
}