手写堆栈和队列

手写堆栈

堆栈是什么？

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

堆栈的英文叫做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);
}

两个注意点

1. 入队时，一开始是不是空得判断一下，如果是空，将插入节点赋给front；
2. 出对时，如果删了最后一个节点，就得把rear赋为空。

无节点状态：rear，front都为NULL

一个节点状态，front指向节点，rear为NULL

总结

关于堆栈和队列的构造大概就是这样啦，多看多写多熟悉，有挺多细节都需要注意！