数据结构---栈&&队列

栈和队列是我们数据结构中经常使用的数据结构，所以现在来了解一下栈和队列。

---

栈

特点：

栈是一种特殊的线性表，其中进行数据插入和弹出的部分叫做栈顶，另一端叫做栈底。

只允许数据从栈顶压入，从栈顶弹出即先进后出的特点，也称LIFO  (Last In First Out)。

压栈：将数据从栈顶压入栈中。

弹栈：将栈顶的数据从栈中弹出。

实现：

接下来基于C语言来实现一个栈，及其增删查改功能：

栈的初始化：

对于栈，肯定要和链表一样进行数据结构定义，但是对于链表我们只需要开一个大小的空间即可，但是栈可能会压入多个数据，我们无法得知具体数目，所以我们一开始选择将栈的大小设置成为4，后续对栈容量进行动态扩容即可。

typedef struct stack {
	int* data;
	int size, top;
}stack;
 
stack* Stack_Init() {
	stack* p = (stack*)malloc(sizeof(stack));
	p->data = (int*)malloc(sizeof(int) * 4);
	p->size = 4;
	p->top = -1;
	return p;
}

栈的销毁：

既然我们使用malloc函数来分配了栈的内存，那么我们就需要设置一个函数来释放栈的内存空间：

 
void Stack_Free(stack* p) {
	if (p == NULL) {
		return;
	}
	free(p->data);
	free(p);
	return;
}

栈的压入操作:

在上文，我们考虑到了由于栈要压入未知数据量，所以我们不能固定栈的大小，则需要动态内存开辟，实现栈的容量的增加。

但是又考虑到另外一个问题，我们要增加多少容量呢？当数据量很大时，只增加个位数或十位数级别的容量对栈的帮助不大，任然需要频繁增加栈的容量，那么我们每次改变栈的容量时，将栈的容量翻一倍即可，以达到减少扩容次数的需要。

在思考完栈的容量管理后，栈的压入就变得简单了，只需要将栈的size位置放入数据并且让size+1即可。

int Stack_Push(int val, stack* p) {
	if ( (p->top) + 1 == p->size || p == NULL) {
		p->data=(int*)realloc(p,p==NULL?sizeof(int)*4:2*p->size*sizeof(int));
	}
	p->data[p->top + 1] = val;
	p->top += 1;
	return 1;
}

查询栈顶元素：

由于栈后进先出的特性，我们只能查找到栈顶元素

int top(stack* p) {
	if (p->top == -1) {
		return NULL;
	}
	return p->data[p->top];
}

栈的判空：

当栈中不含有元素时，我们则不能继续弹出栈顶的元素，所以我们需要判断栈内此时是否存有元素。

int Empty(stack* p) {
	if (p == NULL) {
		return NULL;
	}
	return (p->top == -1);
}

栈的弹出操作：

栈的弹出存在一种特殊情况即栈为空时弹出元素，此时弹出操作则为违法操作。

所以在弹出操作前，我们需要调用判空函数来判断弹出操作是否合法。

若栈内不为空，则弹出栈顶元素；若栈内为空，则返回NULL即可。

int Stack_Pop(stack* p) {
	if (Empty(p) ==0) {
		return 0;
	}
	p->top -= 1;
	return p->data[(p->top) + 1]；
}

此外栈还可以由链表实现，由链表实现的栈则省去了栈的扩容操作，节约了时间。

---

队列：

特点：

队列也是一种特殊的线性表，其中进行数据插入的部分叫做队尾，弹出数据的部分叫做队首。

队列只允许数据从队尾压入，从队首弹出。

具有先进先出的特点，也称FIFO  (First In First Out)。

实现：

接下来是基于C语言实现队列及其增删查改的操作：

队列的初始化：

队列与栈相似，我们都需要对其进行数据结构的定义。

在定义完数据结构后，我们任然需要与栈一样考虑队列的大小管理，所以我们将队列的大小初始化为4。

typedef struct queue {
	int* data;
	int size, count, head, tail;
}queue;
 
 
//初始化队列
queue* Init_Queue(int n) {
	queue* p = (queue*)malloc(sizeof(queue));
	p->data = (int*)malloc(sizeof(int)*4);
	//让count，head，size，tail为0
	p->count = p->head = p->size = p->tail = 0;
	//返回该队列的首地址
	return p;
}

队列的销毁：

由于队列使用了malloc函数分配了内存，所以我们需要手动销毁queue的内存。

//定义一个函数用于释放队列的空间
void Queue_Free(queue* head) {
	if (head == NULL) {
		return;
	}
    free(head->data);
	free(head);
	return;
}

队列的插入操作：

队列与栈一样，当队列容量即将满时，我们将队列的大小翻一倍。

然后将数据插入到队列中即可：

void Queue_Insert(queue* p,int val){
    if(p->data==NULL || (p->count+1==p->size)){
        p->data=(int*)realloc(p->data,p->data==NULL?4:2*sizeof(int)*p->size);
        p->size*=2;
    }
    p->data[p->count++]=val;
    p->tail++;
    return;
}

队列的判空：

队列与栈一致，当队列为空时，弹出队首元素为违法操作，所以我们需要对队列进行判空

 
int Empty(queue* p) {
	return (p->count == 0);
}

队列的弹出操作：

与栈操作一致，当队列为空时，弹出元素为违法操作；队列不为空时，则弹出队首元素。

int Delete(queue* p) {
	//判断队列中是否为空
	if (Empty(p)) {
		return 0;
	}
	//让队首向后一个，含有的数据-1
	p->head += 1;
	p->count -= 1;
	return  p->data[p->head-1];
}

查询队首元素：

对于队列，我们只能查询队首的元素。

//输出队首的数据
int Queue_Front(queue* p) {
	return p->data[p->head];
}

队列也可以由链表实现，你能构思并且设计一个由链表构成的队列吗？

---

至此，队列和栈的讲解到此结束。

如果我的文章对你有所帮助，不妨给我个关注何点赞吧。