栈与队列

一种特殊的线性表, 只允许在固定的一端进行插入和删除操作. 进行数据插入和删除操作的一端称为栈顶, 另一端称为栈底. 栈中的数据元素遵守后进先出的原则

压栈: 栈的插入操作, 入数据在栈顶

出栈: 栈的删除操作, 出数据也在栈顶

栈的实现

// Stack.h

#pragma once

typedef int STDataType;
typedef struct Stack {
	STDataType* _array;
	int _capacity;
	int _size;
}Stack;

void StackInit(Stack* ps);
void StackPush(Stack* ps, STDataType data);
void StackPop(Stack* ps);
int StackSize(Stack* ps);
int StackEmpty(Stack* ps);
void StackDestory(Stack* ps);
void CheckCapacity(Stack* ps);
STDataType StackTop(Stack* ps);
// Stack.c

#include "Stack.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

void CheckCapacity(Stack* ps) {
	assert(ps);
	if (ps->_size == ps->_capacity) {
		int newCapacity = ps->_capacity * 2;
		STDataType* pTemp = (STDataType*)malloc(sizeof(STDataType) * newCapacity);
		if (pTemp == NULL) {
			assert(0);
			return;
		}
		for (int i = 0; i < ps->_size; ++i) {
			pTemp[i] = ps->_array[i];
		}
		free(ps->_array);
		ps->_array = pTemp;
		ps->_capacity = newCapacity;
	}
}

void StackInit(Stack* ps) {
	assert(ps);
	ps->_array = (STDataType*)malloc(sizeof(STDataType) * 1024);
	if (ps->_array == NULL) {
		assert(0);
		return;
	}
	ps->_capacity = 1024;
	ps->_size = 0;
}

void StackPush(Stack* ps, STDataType data) {
	CheckCapacity(ps);
	ps->_array[ps->_size++] = data;
}

void StackPop(Stack* ps) {
	assert(ps);
	if (StackEmpty(ps)) {
		return;
	}
	ps->_size -= 1;
}

STDataType StackTop(Stack* ps) {
	assert(ps);
	return ps->_array[ps->_size - 1];
}

int StackSize(Stack* ps) {
	assert(ps);
	return ps->_size;
}

int StackEmpty(Stack* ps) {
	assert(ps);
	return 0 == ps->_size;
}

void StackDestory(Stack* ps) {
	assert(ps);
	if (ps->_array) {
		free(ps->_array);
		ps->_capacity = 0;
		ps->_size = 0;
	}
}

队列

只允许在一端进行插入数据操作, 在另一端进行删除数据操作的特殊线性表. 队列具有先进先出的特点

入队列: 进行插入操作的一端称为队尾

出队列: 进行删除操作的一端称为对头

队列的实现

// Queue.h

#pragma once
typedef int QDataType;
typedef struct QNode {
	struct QNode* _pNext;
	QDataType _data;
}QNode;

typedef struct Queue {
	QNode* _front;
	QNode* _back;
}Queue;

void QueueInit(Queue* q);
void QueuePush(Queue* q, QDataType data);
void QueuePop(Queue* q);
QDataType QueueFront(Queue* q);
QDataType QueueBack(Queue* q);
int QueueSize(Queue* q);
int QueueEmpty(Queue* q);
void QueueDestory(Queue* q);
// Queue.c

#include "Queue.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

QNode* BuyQueueNode(QDataType data) {
	QNode* pNewNode = (QNode*)malloc(sizeof(QNode));
	if (pNewNode == NULL) {
		assert(0);
		return NULL;
	}
	pNewNode->_data = data;
	pNewNode->_pNext = NULL;
	return pNewNode;
}

void QueueInit(Queue* q) {
	assert(q);
	q->_front = q->_back = NULL;
}

void QueuePush(Queue* q, QDataType data) {
	assert(q);
	QNode* pNewNode = BuyQueueNode(data);
	if (QueueEmpty(q)) {
		q->_front = q->_back = pNewNode;
	}
	else {
		q->_back->_pNext = pNewNode;
		q->_back = pNewNode;
	}
}

void QueuePop(Queue* q) {
	QNode* pDelNode = NULL;
	if (QueueEmpty(q)) {
		return;
	}
	pDelNode = q->_front;
	if (pDelNode->_pNext = NULL) {
		q->_front = q->_back = NULL;
	}
	else {
		q->_front = pDelNode->_pNext;
	}
	free(pDelNode);
}

QDataType QueueBack(Queue* q) {
	assert(q);
	return q->_back->_data;
}

QDataType QueueFront(Queue* q) {
	assert(q);
	return q->_front->_data;
}

int QueueSize(Queue* q) {
	int count = 0;
	QNode* pCur = q->_front;
	while (pCur) {
		++count;
		pCur = pCur->_pNext;
	}
	return count;
}

int QueueEmpty(Queue* q) {
	assert(q);
	return NULL == q->_front;
}

void QueueDestory(Queue* q) {
	QNode* pCur = q->_front;
	while (pCur) {
		q->_front = pCur->_pNext;
		free(pCur);
		pCur = q->_front;
	}
	q->_front = q->_back = NULL;
}

堆, 栈, 队列的区别

堆是在程序运行时, 而不是在程序编译时, 申请某个大小的内存空间. 即动态分配内存, 对其访问和对一般内存的访问没有区别. 堆是指程序运行时申请的动态内存, 而栈只是值一种使用堆的方法(先进后出)

也称为堆栈, 一种先进后出, 插入和删除均在栈顶的线性表

堆栈的区别

  • 空间分配

    栈(操作系统): 由操作系统自动分配释放, 存放函数的参数值, 局部变量的值等. 操作方式类似于数据结构中的栈

    堆(操作系统): 一般由程序员分配释放, 若程序员不释放, 程序结束时可能由OS回收. 分配方式类似于链表

  • 缓存方式

    栈: 使用的是一级缓存, 通常是被调用时处于存储空间中, 调用完毕立即释放

    堆: 存放在二级缓存中

  • 数据结构

    栈: 先进后出的数据结构

    堆: 树

队列

一种先进先出, 插入在队尾, 删除在队头的线性表


我们的征途是星辰大海!