数据结构学习笔记--栈和队列

Published on with 0 views and 0 comments

一、栈

1.1 基本概念

栈是只允许在一端进行插入或删除操作的线性表，这意味着我们可以使用顺序表或者链表的形式来实现一个栈，遵循后进先出的原则

image.png

  • 栈顶 线性表允许插入或删除的一端
  • 栈底 不允许插入或删除的一端
  • 空栈 不含有元素的空表

1.2 基本操作

  • InitStack 初始化一个空栈S
  • Push 入栈
  • Pop 出栈
  • GetTop 获取栈顶元素
  • PrintStack(&S) 遍历栈元素

出栈入栈流程如下

image.png

1.3 栈的实现

栈是一个线性表，可以使用顺序表实现，也可以使用链表实现

1.3.1 栈的顺序表实现

使用顺序表实现栈时，需要提前申请连续的内存空间，且存在栈满、扩容等问题

可以建立一个数组，数组头部作为栈底，数组尾部作为栈顶，同时使用一个变量来记录当前栈顶元素所在的数组下标，所有操作都在栈尾进行，这样可以避免移动元素

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 8
#define ARRAY_STACK_INCRE_MENT 8
typedef enum Status { OK, MEMORY_OVERFLOW, ERROR,EMPTY_STACK } Status;
typedef int ElemType;
typedef struct ArrayStack {
	ElemType* data;
	int stackTopIndex;// 栈顶元素位置
	int length;// 栈长度
} ArrayStack;

Status InitStack(ArrayStack* arrayStack) {
	arrayStack->data = (ElemType*)malloc(sizeof(ElemType) * MAX_SIZE);
	if (arrayStack->data == NULL) {
		printf("内存初始化失败\n");
		return MEMORY_OVERFLOW;
	}
	arrayStack->stackTopIndex = -1;
	arrayStack->length = MAX_SIZE;
	return OK;
}


Status Push(ArrayStack* arrayStack,ElemType e) {
	if (arrayStack->stackTopIndex + 1 >= arrayStack->length) {
		ElemType* newData = (ElemType*)realloc(arrayStack->data, (arrayStack->length + ARRAY_STACK_INCRE_MENT) * sizeof(ElemType));
		if (newData == NULL) {
			printf("扩容失败\n");
			free(newData);
			return MEMORY_OVERFLOW;
		}
		arrayStack->data = newData;
		arrayStack->length += ARRAY_STACK_INCRE_MENT;
	}
	arrayStack->data[arrayStack->stackTopIndex + 1] = e;
	arrayStack->stackTopIndex++;
	return OK;
}

ElemType Pop(ArrayStack* arrayStack) {
	if (arrayStack->stackTopIndex == -1) {
		printf("空栈");
		return -1;
	}
	// 这里其实没有真的删除数组中的元素，而是将栈顶下标前移，入栈的时候会覆盖原来的值
	ElemType e = arrayStack->data[arrayStack->stackTopIndex];
	arrayStack->stackTopIndex--;
	return e;
}

ElemType GetPop(ArrayStack* arrayStack) {
	if (arrayStack->stackTopIndex == -1) {
		printf("空栈");
		return -1;
	}
    // 这个方法与出栈的区别仅限于没有移动栈顶下标
	return arrayStack->data[arrayStack->stackTopIndex];
}

Status PrintArrayStack(ArrayStack* arrayStack) {
	if (arrayStack->stackTopIndex == -1) {
		printf("\n");
		return EMPTY_STACK;
	}
	for (int index = 0; index <= arrayStack->stackTopIndex; index++) {
		printf("%d ", arrayStack->data[index]);
	}
	printf("\n");
	return OK;
}

int main() {
	ArrayStack arrayStack;
	InitStack(&arrayStack);
	for (int i = 0; i < 10; i++) {
		Push(&arrayStack,i+1);
	}
	PrintArrayStack(&arrayStack);
	printf("%d\n", GetPop(&arrayStack));
	printf("%d\n", Pop(&arrayStack));
	printf("%d\n", GetPop(&arrayStack));
	printf("%d\n", Pop(&arrayStack));
	printf("%d\n", GetPop(&arrayStack));
	printf("%d\n", Pop(&arrayStack));
	printf("%d\n", GetPop(&arrayStack));
	printf("%d\n", Pop(&arrayStack));
	printf("%d\n", GetPop(&arrayStack));
	printf("%d\n", Pop(&arrayStack));
	printf("%d\n", GetPop(&arrayStack));
	printf("%d\n", Pop(&arrayStack));
	printf("%d\n", GetPop(&arrayStack));
	printf("%d\n", Pop(&arrayStack));
	printf("%d\n", GetPop(&arrayStack));
	printf("%d\n", Pop(&arrayStack));
	printf("%d\n", GetPop(&arrayStack));
	printf("%d\n", Pop(&arrayStack));
	printf("%d\n", GetPop(&arrayStack));
	printf("%d\n", Pop(&arrayStack));
	printf("%d\n", GetPop(&arrayStack));
	printf("%d\n", Pop(&arrayStack));
}

1.3.2 栈的链表实现

使用链表实现栈时，不需要考虑栈满扩容等因素，所有操作都在链表头部实现，在链表头部入栈，头部出栈

#include <stdio.h>
#include <stdlib.h>

typedef enum Status { OK, MEMORY_OVERFLOW, ERROR, EMPTY_STACK } Status;
typedef int ElemType;
typedef struct StackNode {
	ElemType data;
	struct StackNode* next;
}StackNode;

typedef struct LinkedStack {
	StackNode* head;
	int length;
}LinkedStack;

Status InitLinkedStack(LinkedStack* stack){
	stack->head = NULL;
	stack->length = 0;
	return OK;
}
Status LinkedStackPush(LinkedStack* stack, ElemType e) {
	StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
	if (newNode == NULL) {
		return MEMORY_OVERFLOW;
	}
	newNode->data = e;
	if (stack->length == 0){
		newNode->next = NULL;
		stack->head = newNode;
		stack->length++;
		return OK;
	}
	StackNode* currentHead = stack->head;
	newNode->next = currentHead;
	stack->head = newNode;
	stack->length++;
	return OK;
}

ElemType LinkedStackPop(LinkedStack* stack) {
	if (stack->length == 0){
		printf("空栈\n");
		return -1;
	}
	StackNode* currentHead = stack->head;
	ElemType data = currentHead->data;
	stack->head = currentHead->next;
	free(currentHead);
	stack->length--;
	return data;
}

ElemType LinkedStackGetPop(LinkedStack* stack) {
	if (stack->length == 0) {
		printf("空栈\n");
		return -1;
	}
	StackNode* currentHead = stack->head;
	ElemType data = currentHead->data;
	return data;
}

Status PrintLinkedStack(LinkedStack* stack) {
	if (stack->length == 0) {
		printf("空栈\n");
		return EMPTY_STACK;
	}
	StackNode* currentHead = stack->head;
	while (currentHead != NULL) {
		printf("%d ", currentHead->data);
		currentHead = currentHead->next;
	}
	printf("\n");
	return OK;
}

int main() {
	LinkedStack stack;
	InitLinkedStack(&stack);
	for (int i = 0; i < 10; i++) {
		LinkedStackPush(&stack, i + 1);
	}
	PrintLinkedStack(&stack);
	printf("%d\n", LinkedStackGetPop(&stack));
	printf("%d\n", LinkedStackPop(&stack));
	printf("%d\n", LinkedStackGetPop(&stack));
	printf("%d\n", LinkedStackPop(&stack));
	printf("%d\n", LinkedStackGetPop(&stack));
	printf("%d\n", LinkedStackPop(&stack));
	printf("%d\n", LinkedStackGetPop(&stack));
	printf("%d\n", LinkedStackPop(&stack));
	printf("%d\n", LinkedStackGetPop(&stack));
	printf("%d\n", LinkedStackPop(&stack));
	printf("%d\n", LinkedStackGetPop(&stack));
	printf("%d\n", LinkedStackPop(&stack));
	printf("%d\n", LinkedStackGetPop(&stack));
	printf("%d\n", LinkedStackPop(&stack));
	printf("%d\n", LinkedStackGetPop(&stack));
	printf("%d\n", LinkedStackPop(&stack));
	printf("%d\n", LinkedStackGetPop(&stack));
	printf("%d\n", LinkedStackPop(&stack));
	printf("%d\n", LinkedStackGetPop(&stack));
	printf("%d\n", LinkedStackPop(&stack));
	printf("%d\n", LinkedStackGetPop(&stack));
	printf("%d\n", LinkedStackPop(&stack));
}

二、队列

2.1 队列

2.1.1 基本概念

队列是一种受限的线性表，允许在表的一端进行插入（入队），在另一端进行删除（出队）

image.png

  • 队头 允许插入的一端
  • 队尾 允许删除的一端
  • 空队 不含任何元素的队列

2.1.2 基本操作

  • InitQueue 初始化队列
  • EnQueue 入队
  • DeQueue 出队

2.1.3 队列顺序表实现

2.1.3.1 队满问题

队列使用顺序存储有两种方法，一种是出队时真的删除那个元素，这样的话就需要对数组进行移动，此时算法的时间复杂度就为变成O(n)

另一种是用front，rear两个变量记录当前队首元素和队尾元素在数组中的下标位置，但是此时带来另一个问题，就是队列满无法判断

image.png

如上图队列有以下特点：

  • 队初始 front = rear = 0
  • 入队 数据入队到队尾，队尾指针+1
  • 出队 取出对头元素，对头指针+1
  • 队满 此时堆满无法判断，因为我们使用rear==MAX_SIZE判断的话，可以看到上图b出队时，空间还有剩余，此时是一种假溢出
2.1.3.2 循环队列

把存储元素的线性表从逻辑上视为一个环，称为循环队列

循环队列性质：

  • 队列初始 front=rear=0
  • 队首指针进1 front = (front+1)%MAX_SIZE
  • 队尾指针进1 rear= (rear+1)%MAX_SIZE
  • 队列中元素个数 (rear-front+MAX_SIZE)%MAX_SIZE

循环队列出队入队

image.png

空队和队满的区分防范

  1. 牺牲一个单元来区分对空和队满，入队时少用一个队列单元（如下图）
    1. 此时队满条件 (rear+1)%MAX_SIZE==front
    2. 此时队空条件front==rear
    3. 队列中元素个数 (rear-front+MAX_SIZE)%MAX_SIZE
  2. 类型中新增表示元素个数的数据成员size，对空条件size==0，队满条件size==MAX_SIZE，入队size++,出队size--
  3. 新增一个boolean类型的数据成员isFull，若因删除元素导致front==rear，设置isFull等于false表示队空，若因新增元素导致front==rear则设置isFull等于true表示队满

image.png

2.1.3.3 代码实现
#include <stdio.h>
#include <stdlib.h>


#define MAX_SIZE 6
#define TRUE 1
#define FALSE 0
typedef int bool;
typedef int ElemType;
typedef struct ArrayQueue {
	ElemType data[MAX_SIZE];
	int front, rear;
}ArrayQueue;

InitArrayQueue(ArrayQueue* queue) {
	queue->front = 0;
	queue->rear = 0;
}
bool isEmpty(ArrayQueue* queue) {
	if (queue->front == queue->rear) {
		return TRUE;
	}
	return FALSE;
}
void EnArrayQueue(ArrayQueue* queue,ElemType e) {
	if ((queue->rear + 1) % MAX_SIZE == queue->front) {
		printf("队满!\n");
		return;
	}
	queue->data[queue->rear] = e;
	queue->rear = (queue->rear + 1) % MAX_SIZE;
}
ElemType DeArrayQueue(ArrayQueue* queue) {
	if (isEmpty(queue) == TRUE) {
		printf("队空!\n");
		return -1;
	}
	ElemType e = queue->data[queue->front];
	printf("%d出队\n", e);
	queue->front = (queue->front + 1) % MAX_SIZE;
	return e;
}

int main() {
	ArrayQueue queue;
	InitArrayQueue(&queue);
	for (int i = 0; i < 10; i++) {
		EnArrayQueue(&queue, i);
	}
	for (int i = 0; i < 10; i++) {
		DeArrayQueue(&queue);
	}

}

2.1.4 队列链表实现

队列链表实现不存在队满问题，但是任然需要两个指针，一个指向链表头元素，一个指向链表尾部元素，从链表尾部入队，从链表头部出队，这里建立一个空的头节点，初始化或链表为空都指向这个空节点，方便后续操作

image.png

2.1.4.1 代码实现
#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
typedef int bool;
typedef int ElemType;
typedef struct LinkedQueueNode {
	ElemType data;
	struct LinkedQueueNode* next;
}LinkedQueueNode;
typedef struct LinkedQueue {
	LinkedQueueNode* front;
	LinkedQueueNode* rear;
}LinkedQueue;


void InitLinkedQueue(LinkedQueue* queue) {
	LinkedQueueNode* head = (LinkedQueueNode*)malloc(sizeof(LinkedQueueNode));
	if (head == NULL) {
		printf("内存申请失败\n");
		return;
	}
	head->next = NULL;
	queue->front = head;
	queue->rear = head;
}

bool IsLinkedQueueEmpty(LinkedQueue* queue) {
	if (queue->front == queue->rear) {
		return TRUE;
	}
	return FALSE;
}

void EnLinkedQueue(LinkedQueue* queue,ElemType e) {
	LinkedQueueNode* newNode = (LinkedQueueNode*)malloc(sizeof(LinkedQueueNode));
	if (newNode == NULL) {
		printf("内存申请失败\n");
		return;
	}
	newNode->next = NULL;
	newNode->data = e;
	queue->rear->next = newNode;
	queue->rear = newNode;
	printf("%d入队\n", e);
}

void DeLinkedQueue(LinkedQueue* queue) {
	if (IsLinkedQueueEmpty(queue) == TRUE) {
		printf("队空\n");
		return;
	}
	LinkedQueueNode* deQueueNode = queue->front->next;
	printf("%d出队\n", deQueueNode->data);
	//最后一个元素出队
	if (deQueueNode == queue->rear) {
		queue->rear = queue->front;
	}
	else {
		queue->front->next = deQueueNode->next;
	}
	free(deQueueNode);
}

int main() {
	LinkedQueue queue;
	InitLinkedQueue(&queue);
	for (int i = 0; i < 10; i++) {
		EnLinkedQueue(&queue, i);
	}
	for (int i = 0; i < 10; i++) {
		DeLinkedQueue(&queue);
	}

}

2.2 双端队列

2.2.1 基本概念

双端队列再队列的基础上，在对列两端都允许进行出栈和入栈操作

image.png

如果在某一端允许出队和入队，但是在另一端只允许入队，则这是一个输出受限的双端队列image.png

如果在某一端允许出队和入队，但是在另一端只允许出队，则这是一个输入受限的双端队列

image.png

如果只允许在一端进行入队和出队，那么这就是一个栈

image.png

2.2.2 双端队列顺序表实现

使用数组实现顺序表时，还是要注意队列满的问题，也是使用循环队列的解决

#include <stdio.h>
#include <stdlib.h>


#define MAX_SIZE 6
#define TRUE 1
#define FALSE 0
typedef int bool;
typedef int ElemType;
typedef struct ArrayDEQueue {
	ElemType data[MAX_SIZE];
	int front, rear;
}ArrayDEQueue;

InitArrayDEQueue(ArrayDEQueue* queue) {
	queue->front = 0;
	queue->rear = 0;
}
bool isArrayDEQueueEmpty(ArrayDEQueue* queue) {
	if (queue->front == queue->rear) {
		return TRUE;
	}
	return FALSE;
}
void ArrayDEQueueInsertFront(ArrayDEQueue* queue, ElemType e) {
	if ((queue->rear + 1) % MAX_SIZE == queue->front) {
		printf("队满!\n");
		return;
	}
	// front向前移动一位，为了避免负数，先加MAX_SIZE再求余
	queue->front = (queue->front - 1 + MAX_SIZE)%MAX_SIZE; 
	queue->data[queue->front] = e;
	printf("%d入队\n", e);

}

void ArrayDEQueueInsertRear(ArrayDEQueue* queue, ElemType e) {
	if ((queue->rear + 1) % MAX_SIZE == queue->front) {
		printf("队满!\n");
		return;
	}
	// rear向后移动一位
	queue->data[queue->rear] = e;
	queue->rear = (queue->rear + 1) % MAX_SIZE;
	printf("%d入队\n", e);
}


ElemType ArrayDEQueueRemoveFront(ArrayDEQueue* queue) {
	if (isArrayDEQueueEmpty(queue) == TRUE) {
		printf("队空!\n");
		return -1;
	}
	ElemType e = queue->data[queue->front];
	printf("%d出队\n", e);
	queue->front = (queue->front + 1) % MAX_SIZE;
	return e;
}

ElemType ArrayDEQueueRemoveRear(ArrayDEQueue* queue) {
	if (isArrayDEQueueEmpty(queue) == TRUE) {
		printf("队空!\n");
		return -1;
	}
	// 从队尾出队，此时需要将rear前移一位
	queue->rear = (queue->rear - 1+ MAX_SIZE) % MAX_SIZE;
	ElemType e = queue->data[queue->rear];
	printf("%d出队\n", e);
	return e;
}
int main() {
	ArrayDEQueue queue;
	InitArrayDEQueue(&queue);

	printf("从队尾入队，队尾出队\n");
	for (int i = 0; i < 10; i++) {
		ArrayDEQueueInsertRear(&queue, i);
	}
	for (int i = 0; i < 10; i++) {
		ArrayDEQueueRemoveRear(&queue);
	}

	printf("从队头入队，队头出队\n");
	for (int i = 0; i < 10; i++) {
		ArrayDEQueueInsertFront(&queue, i);
	}
	for (int i = 0; i < 10; i++) {
		ArrayDEQueueRemoveFront(&queue);
	}

	printf("从队头入队，队尾出队\n");
	for (int i = 0; i < 10; i++) {
		ArrayDEQueueInsertFront(&queue, i);
	}
	for (int i = 0; i < 10; i++) {
		ArrayDEQueueRemoveRear(&queue);
	}

	printf("从队尾入队，队头出队\n");
	for (int i = 0; i < 10; i++) {
		ArrayDEQueueInsertRear(&queue, i);
	}
	for (int i = 0; i < 10; i++) {
		ArrayDEQueueRemoveFront(&queue);
	}
}

2.2.3 双端队列的链表实现

为了方便查询前后节点，使用双链表，且不需要空的头节点

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
typedef int bool;
typedef int ElemType;
typedef struct LinkedDEQueueNode {
	ElemType data;
	struct LinkedDEQueueNode* next, * pre;
}LinkedDEQueueNode;
typedef struct LinkedDEQueue {
	LinkedDEQueueNode* front;
	LinkedDEQueueNode* rear;
}LinkedDEQueue;


void InitLinkedDEQueue(LinkedDEQueue* queue) {
	queue->front = NULL;
	queue->rear = NULL;
}

void LinkedDEQueueInsertFront(LinkedDEQueue* queue, ElemType e) {
	LinkedDEQueueNode* newNode = (LinkedDEQueueNode*)malloc(sizeof(LinkedDEQueueNode));
	if (newNode == NULL) {
		printf("内存申请失败\n");
		return;
	}
	newNode->pre = NULL;
	newNode->next = queue->front;
	newNode->data = e;
	// 入队若现在队首不为空，则将新节点设置为当前队首的前驱，若为空说明是空队列，要设置尾指针
	if (queue->front != NULL) {
		queue->front->pre = newNode;
	}
	else {
		queue->rear = newNode;
	}
	queue->front = newNode;

	printf("%d入队\n", e);
}

void LinkedDEQueueInsertRear(LinkedDEQueue* queue, ElemType e) {
	LinkedDEQueueNode* newNode = (LinkedDEQueueNode*)malloc(sizeof(LinkedDEQueueNode));
	if (newNode == NULL) {
		printf("内存申请失败\n");
		return;
	}
	newNode->pre = queue->rear;
	newNode->next = NULL;
	newNode->data = e;
	// 入队若现在队尾不为空，则将新节点设置为当前队首的后继，若为空说明是空队列，要设置头指针
	if (queue->rear != NULL) {
		queue->rear->next = newNode;
	}
	else {
		queue->front = newNode;
	}
	queue->rear = newNode;

	printf("%d入队\n", e);
}

void LinkedDEQueueRemoveFront(LinkedDEQueue* queue) {
	if (queue->front == NULL) {
		printf("空队\n");
		return;
	}
	LinkedDEQueueNode* currentHead = queue->front;
	printf("%d出队\n", currentHead->data);
	queue->front = currentHead->next;
	// 删除队首元素，新的队首元素没有前节点
	if (queue->front != NULL) {
		queue->front->pre = NULL;
	}
	// 删除队首元素，队列为空则队尾指针也要重置
	else {
		queue->rear = NULL;
	}
	free(currentHead);
}


void LinkedDEQueueRemoveRear(LinkedDEQueue* queue) {

	if (queue->front == NULL) {
		printf("空队\n");
		return;
	}
	LinkedDEQueueNode* currentHead = queue->rear;
	printf("%d出队\n", currentHead->data);
	queue->rear = currentHead->pre;
	// 删除队首元素，新的队首元素没有前节点
	if (queue->rear != NULL) {
		queue->rear->next = NULL;
	}
	// 删除队首元素，队列为空则队尾指针也要重置
	else {
		queue->front = NULL;
	}
	free(currentHead);
}

int main() {
	LinkedDEQueue queue;
	InitLinkedDEQueue(&queue);

	printf("从队尾入队，队尾出队\n");
	for (int i = 0; i < 10; i++) {
		LinkedDEQueueInsertRear(&queue, i);
	}
	for (int i = 0; i < 10; i++) {
		LinkedDEQueueRemoveRear(&queue);
	}

	printf("从队头入队，队头出队\n");
	for (int i = 0; i < 10; i++) {
		LinkedDEQueueInsertFront(&queue, i);
	}
	for (int i = 0; i < 10; i++) {
		LinkedDEQueueRemoveFront(&queue);
	}

	printf("从队头入队，队尾出队\n");
	for (int i = 0; i < 10; i++) {
		LinkedDEQueueInsertFront(&queue, i);
	}
	for (int i = 0; i < 10; i++) {
		LinkedDEQueueRemoveRear(&queue);
	}

	printf("从队尾入队，队头出队\n");
	for (int i = 0; i < 10; i++) {
		LinkedDEQueueInsertRear(&queue, i);
	}
	for (int i = 0; i < 10; i++) {
		LinkedDEQueueRemoveFront(&queue);
	}
}
标题：数据结构学习笔记--栈和队列
作者：wenyl
地址：http://www.wenyoulong.com/articles/2024/05/16/1715868196511.html

↑ ↓