首页 计算机科学 数据结构笔记

该系列为本人的学习笔记，主要由本人整理书写而成。部分内容来自教材、视频课程等，不能保证完全原创性。

萌新的学习笔记，写错了恳请斧正。

# 栈

栈是一种特殊的线性表，是一种遵循后进先出（LIFO, Last In First Out）原则的数据结构。想象一下一摞盘子，你最后放上去的盘子会是你第一个拿掉的；同样地，在栈中，最后存入的数据会是第一个被取出来的。

其中，进行数据的增加和删除的一端称为栈顶，另一端称为栈底。数据进入栈的过程称为压栈（入栈），数据删除的过程称为弹栈（出栈）。

# 栈的实现

栈一般可以通过数组（顺序表）或链表实现，但是数组实现优于链表，因为仅在数组尾部插入删除数据代价较小。其基本操作有：

  1. Push（入栈）: 添加一个或多个新元素到栈顶。
  2. Pop（出栈）: 移除栈顶的元素，并返回该元素。
  3. Peek（查看栈顶元素）: 返回栈顶的元素，但不从栈中移除它。
  4. IsEmpty（判断栈是否为空）: 检查栈是否为空。如果栈为空，返回 true；否则返回 false。
  5. Size（获取栈的大小）: 返回栈中元素的数量。

下面给出顺序表栈的实现代码：

Stack.h
#pragma once
 
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
 
// 数据类型
typedef int STDataType;
 
typedef struct Stack
{
	STDataType* _data;
	int _top;
	int _capacity;
} Stack, * pStack;
 
// 栈的初始化
void InitStack(pStack pst);
// 压栈
void StackPush(pStack pst, STDataType x);
// 弹栈
void StackPop(pStack pst);
// 栈顶元素
STDataType StackTop(pStack pst);
// 栈大小
int StackSize(pStack pst);
// 栈判空
_Bool StackEmpty(pStack pst);
// 栈销毁
void StackDestory(pStack pst);
Stack.c
#define _CRT_SECURE_NO_WARNINGS
 
#include "Stack.h"
 
// 栈的初始化
void InitStack(pStack pst)
{
	assert(pst);
	pst->_data = NULL;
	pst->_top = 0;
	pst->_capacity = 0;
}
// 容量检查扩容
void StackCheck(pStack pst)
{
	if (pst->_top == pst->_capacity)
	{
		int newCapacity = ((pst->_capacity == 0) ? 4 : (2 * pst->_capacity));
		STDataType* temp = (STDataType*)realloc(pst->_data, newCapacity * sizeof(STDataType));
		if (temp == NULL)
		{
			perror("realloc");
			exit(EXIT_FAILURE);
		}
		pst->_data = temp;
		pst->_capacity = newCapacity;
	}
}
// 压栈
void StackPush(pStack pst, STDataType x)
{
	assert(pst);
	StackCheck(pst); 
	memcpy(&(pst->_data[pst->_top]), &x, sizeof(STDataType));
	pst->_top++;
}
// 弹栈
void StackPop(pStack pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	pst->_top--;
}
// 栈顶元素
STDataType StackTop(pStack pst)
{
	assert(pst);
	return pst->_data[pst->_top - 1];
}
// 栈大小
int StackSize(pStack pst)
{
	assert(pst);
	return pst->_top;
}
// 栈判空
_Bool StackEmpty(pStack pst)
{
	assert(pst);
	return pst->_top == 0;
}
// 栈销毁
void StackDestory(pStack pst)
{
	assert(pst);
	free(pst->_data);
	pst->_capacity = 0;
	pst->_top = 0;
	pst->_data = NULL;
}

# 队列

队列也是一种特殊的顺序表，是一种遵循先进先出（FIFO, First In First Out）原则的数据结构。可以把队列想象成在银行或超市等待服务的人们排成的一行，最先到达的人将是最先得到服务并离开的。

其中，进行数据的插入的一端称为队尾，进行删除的一端称为队头，数据的进入与删除称为入队和出队。

# 队列的实现

队列同样可以通过数组（顺序表）或链表实现，但是链表实现优于数组，因为使用数组的话从队头删除数据的效率就比较低下了。其基本操作有：

  1. Enqueue（入队）: 在队列的末尾添加一个或多个元素。
  2. Dequeue（出队）: 移除队列前端的元素，并返回该元素。
  3. Front（查看队首元素）: 返回队列最前端的元素，但不从队列中移除它。
  4. IsEmpty（判断队列是否为空）: 检查队列是否为空。如果队列为空返回 true；否则返回 false。
  5. Size（获取队列的大小）: 返回队列中元素的数量。

下面给出链表队列的实现代码：

Queue.h
#pragma once
 
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
 
// 队列数据类型
#define QueueData int
 
// 队列
typedef struct QueueNode
{
	QueueData _data;
	struct QueueNode* _next;
} QueueNode;
// 储存队列头尾信息的指针
typedef struct Queue
{
	QueueNode* _front;
	QueueNode* _rear;
	int _size;
} Queue;
 
// 队列的初始化
void QueueInit(Queue* pq);
// 入队
void QueuePush(Queue* pq, QueueData x);
// 出队
void QueuePop(Queue* pq);
// 队列头
QueueData QueueFront(Queue* pq);
// 队列尾
QueueData QueueBack(Queue* pq);
// 队列长
int QueueSize(Queue* pq);
// 队列判空
_Bool QueueEmpty(Queue* pq);
// 队列销毁
void QueueDestory(Queue* pq);
Queue.c
#define _CRT_SECURE_NO_WARNINGS
 
#include "Queue.h"
 
// 队列的初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->_front = NULL;
	pq->_rear = NULL;
	pq->_size = 0;
}
// 入队
void QueuePush(Queue* pq, QueueData x)
{
	assert(pq);
	QueueNode* new = (QueueNode*)malloc(sizeof(QueueNode));
	if (new == NULL)
	{
		perror("malloc");
		exit(EXIT_FAILURE);
	}
 
	new->_data = x;
	new->_next = NULL;
 
	if (pq->_rear)
	{
		pq->_rear->_next = new;
		pq->_rear = new;
	}
	else
	{
		pq->_front = pq->_rear = new;
	}
 
	pq->_size++;
}
// 出队
void QueuePop(Queue* pq)
{
	assert(pq);
	if (pq->_front == NULL)
	{
		return;
	}
	if (pq->_front->_next == NULL)
	{
		free(pq->_front);
		pq->_front = pq->_rear = NULL;
	}
	else
	{
		QueueNode* head = pq->_front->_next;
		free(pq->_front);
		pq->_front = head;
	}
	pq->_size--;
}
// 队列头
QueueData QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->_front);
	return pq->_front->_data;
}
// 队列尾
QueueData QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->_rear); 
	return pq->_rear->_data;
}
// 队列长
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->_size;
}
// 队列判空
_Bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->_size == 0;
}
// 队列销毁
void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->_front;
	while (cur != NULL)
	{
		QueueNode* next = cur->_next;
		free(cur);
		cur = next;
	}
	pq->_front = pq->_rear = NULL;
	pq->_size = 0;
}
# 循环队列

有一种特殊的队列，称为循环队列。

循环队列是一种使用有限数组并采用特殊规则来模拟无限长度队列行为的数据结构。

它的核心思想是当数组达到末端时，会循环回到数组的开头，继续使用数组的前端空间。这种方式解决了在普通队列中使用数组实现时可能遇到的空间浪费问题。

在普通队列中，即使在数组前端有空闲空间，一旦队尾达到数组末端，就不能再添加新元素，除非进行昂贵的数组复制或移动操作。循环队列通过循环利用数组空间，优雅地解决了这一问题。

这里可以参考 leetcode 第 622 题，解答如下：

力扣-第622题题目链接
#define _CRT_SECURE_NO_WARNINGS
 
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
typedef struct {
    int* data;
    int front;
    int rear;
    int capacity;
} MyCircularQueue;
 
 
MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue* tmp = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    tmp->capacity = k + 1;
    tmp->front = tmp->rear = 0;
    tmp->data = (int*)malloc(tmp->capacity * sizeof(int));
    return tmp;
}
 
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    if ((obj->rear + 1) % obj->capacity == obj->front)
    {
        return false;
    }
    obj->data[obj->rear] = value;
    obj->rear = (obj->rear + 1) % obj->capacity;
    return true;
}
 
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (obj->rear == obj->front)
    {
        return false;
    }
    obj->front = (obj->front + 1) % obj->capacity;
    return true;
}
 
int myCircularQueueFront(MyCircularQueue* obj) 
{
    if (obj->front == obj->rear)
    {
        return -1;
    }
    return obj->data[obj->front];
}
 
int myCircularQueueRear(MyCircularQueue* obj) 
{
    if (obj->front == obj->rear)
    {
        return -1;
    }
    return obj->data[(obj->rear + obj->capacity - 1) % obj->capacity];
}
 
bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    return obj->rear == obj->front;
}
 
bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    return (obj->rear + 1) % obj->capacity == obj->front;
}
 
void myCircularQueueFree(MyCircularQueue* obj) 
{
    free(obj->data);
    free(obj);
}

# 一些练习题

  1. 一个栈的初始状态为空。现将元素 1、2、3、4、5、A、B、C、D、E 依次入栈，然后再依次出栈，则元素出栈的顺序是 。

    • 12345ABCDE
    • EDCBA54321
    • ABCDE12345
    • 54321EDCBA

  2. 若进栈序列为 1,2,3,4 进栈过程中可以出栈，则下列不可能的一个出栈序列是 。

    • 1, 4, 3, 2
    • 2, 3, 4, 1
    • 3, 1, 4, 2
    • 3, 4, 2, 1

  3. 循环队列的存储空间为 Q (1:100) ，初始状态为 front=rear=100 。经过一系列正常的入队与退队操作后，front=rear=99 ，则循环队列中的元素个数为 。

    • 1
    • 2
    • 99
    • 0 或 100

  4. 以下不是队列的基本运算？

    • 从队尾插入一个新元素
    • 从队列中删除第 i 个元素
    • 判断一个队列是否为空
    • 读取队头元素的值

  5. 现有一循环队列，其队头指针为 front，队尾指针为 rear; 循环队列长度为 N 。其队内有效长度为？(假设队头不存放数据)

    • (rear - front + N) % N + 1
    • (rear - front + N) % N
    • (rear - front) % (N + 1)
    • (rear - front + N) % (N - 1)