数据结构--栈和队列 源码

一,栈

栈类似于弹匣，先进后出。

实现方法：动态顺序表

---

Stack.h 文件:
源码：

#pragma once
 
#include<stdlib.h>
#include<iostream>
using namespace std;
 
typedef int type;
 
struct Stack
{
	type* arr;
	int top;
	int capacity;
};
 
typedef struct Stack ST;
 
// 初始化栈 
void StackInit(ST* ps);
// 入栈 
void StackPush(ST* ps, type data);
// 出栈 
void StackPop(ST* ps);
// 获取栈顶元素 
type StackTop(ST* ps);
// 获取栈中有效元素个数 
int StackSize(ST* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(ST* ps);
// 销毁栈 
void StackDestroy(ST* ps);
 
void menu();
 

---

实现文件

St.cpp

源码：

#include"Stack.h"
 
 
 
void StackInit(ST* ps)
{
	ps->capacity = 0;
	ps->arr = NULL;
	ps->top = 0;
}
 
void StackPush(ST* ps, type data)
{
	int newcap = 0;
	if (ps->top+1>= ps->capacity)
	{
 
		newcap = ps->capacity == 0 ? 4 : ps->capacity * 2;
 
		type* neww = (type*)realloc(ps->arr,newcap * sizeof type);
		if (neww == NULL)
		{
			printf("malloc is fail\n");
			return;
		}
 
		ps->arr = neww;
		ps->capacity = newcap;
	}
 
	ps->arr[++ps->top] = data;
}
 
void StackPop(ST* ps)
{
	if (ps->top <= 0)
	{
		printf("stack is empty\n");
		return;
	}
	ps->top--;
 
}
 
type StackTop(ST* ps)
{
	if (ps->top <= 0)
	{
		printf("stack is empty\n");
		return -1;
	}
 
	return ps->arr[ps->top];
}
 
int StackSize(ST* ps)
{
	return ps->top;
}
 
int StackEmpty(ST* ps)
{
	if (ps->top <= 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
 
void StackDestroy(ST* ps)
{
	if (ps == NULL)
	{
		return;
	}
	free(ps->arr);
	ps->capacity = 0;
	ps->top = 0;
}
 
void menu()
{
	printf("**********************\n");
	printf("***1.StackPush********\n");
	printf("***2.StackPop*********\n");
	printf("***3.StackTop*********\n");
	printf("***4.StackSize********\n");
	printf("***5.StackEmpty*******\n");
	printf("***6.StackDestroy*****\n");
	printf("**********************\n");
}
 
 
 
 

1.1 StackInit 初始化函数

void StackInit(ST* ps)
{
	ps->capacity = 0;
	ps->arr = NULL;
	ps->top = 0;
}

(1).把动态顺序表初始化为NULL，把top和capacity 初始化为0。

1.2 StackPush 插入函数

void StackPush(ST* ps, type data)
{
	int newcap = 0;
	if (ps->top+1>= ps->capacity)
	{
 
		newcap = ps->capacity == 0 ? 4 : ps->capacity * 2;
 
		type* neww = (type*)realloc(ps->arr,newcap * sizeof type);
		if (neww == NULL)
		{
			printf("malloc is fail\n");
			return;
		}
 
		ps->arr = neww;
		ps->capacity = newcap;
	}
 
	ps->arr[++ps->top] = data;
}

(1).首先检查动态顺序表容量是否装满。装满后使用realloc函数扩容。

(2).检查完毕后，要先加加再赋值，因为要以top==0为栈空条件，所以top等于0的地方不能存值。

1.3 StackPop 出栈函数

void StackPop(ST* ps)
{
	if (ps->top <= 0)
	{
		printf("stack is empty\n");
		return;
	}
	ps->top--;
 
}

(1).先判断栈是否为空，为空就输出提出并返回。

(2).只需直接将top减1即可，不需要将top的地方赋值为0再减1。

1.4 StackTop 输出栈顶

type StackTop(ST* ps)
{
	if (ps->top <= 0)
	{
		printf("stack is empty\n");
		return -1;
	}
 
	return ps->arr[ps->top];
}

(1).先检查栈是否为空，为空则输出提示并返回。

(2).不为空则直接返回位于top的数值。

1.5 StackSize 返回栈元素个数

int StackSize(ST* ps)
{
	return ps->top;
}

(1).由于是先加加top，所以top的值即为栈元素个数。

1.6 StackEmpty 判断栈是否为空

int StackEmpty(ST* ps)
{
	if (ps->top <= 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

(1).根据top来判断，如果top为0，则返回真，否则返回假。

1.7 StackDestroy 销毁栈

void StackDestroy(ST* ps)
{
	if (ps == NULL)
	{
		return;
	}
	free(ps->arr);
	ps->capacity = 0;
	ps->top = 0;
}

(1).直接将arr销毁即可，使用free函数，并将top和capacity都置为0。

---

二,队列

实现方法：单链表

使用两个结构体来操作

---

Queue.h 文件

#pragma once
 
#include<bits/stdc++.h>
using namespace std;
 
typedef int type;
 
struct node
{
	struct node* next;
	type val;
};
 
struct Queue
{
	node* head;
	node* tail;
	int size;
};
 
typedef struct node node;
typedef struct Queue Queue;
 
 
// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, type data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
type QueueFront(Queue* q);
// 获取队列队尾元素 
type QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);
 
void menu();

(1).使用两个结构体，node为结点结构体，Queue为队列结构体用于存放头结点和尾结点。

---

Q.cpp 文件

源码：

#include"Queue.h"
 
 
// 初始化队列 
void QueueInit(Queue* q)
{
	q->head = NULL;
	q->tail = NULL;
	q->size = 0;
}
// 队尾入队列 
void QueuePush(Queue* q, type data)
{
	node* neww = (node*)malloc(sizeof(node));
	neww->next = NULL;
	neww->val =data;
 
	if (q->head == NULL)
	{
		q->head = q->tail = neww;
	}
	else
	{
		q->tail->next = neww;
		q->tail = neww;
	}
	q->size++;
 
 
}
// 队头出队列 
void QueuePop(Queue* q)
{
	if (q->head != NULL)
	{
		node* temp = q->head->next;
		free(q->head);
		q->head = temp;
		q->size--;
	}
}
// 获取队列头部元素 
type QueueFront(Queue* q)
{
	if (q->head != NULL)
	{
		return q->head->val;
	}
	
	cout << "queue is empty" << endl;
	return -1;
}
// 获取队列队尾元素 
type QueueBack(Queue* q)
{
	if (q->head != NULL)
	{
		return q->tail->val;
	}
	cout << "queue is empty" << endl;
	return -1;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	return q->size == 0;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
	node* cur = q->head;
 
	while (cur)
	{
		node* temp = cur->next;
		free(cur);
		cur = temp;
	}
	cur = NULL;
 
}
 
void menu()
{
	printf("********************\n");
	printf("***1.QueueInit******\n");
	printf("***2.QueuePush******\n");
	printf("***3.QueuePop*******\n");
	printf("***4.QueueFront*****\n");
	printf("***5.QueueBack******\n");
	printf("***6.QueueSize******\n");
	printf("***7.QueueEmpty*****\n");
	printf("***8.QueueDestroy***\n");
	printf("********************\n");
 
}

2.1 QueueInit 初始化函数

void QueueInit(Queue* q)
{
	q->head = NULL;
	q->tail = NULL;
	q->size = 0;
}

2.2 QueuePush 插入函数

void QueuePush(Queue* q, type data)
{
	node* neww = (node*)malloc(sizeof(node));
	neww->next = NULL;
	neww->val =data;
 
	if (q->head == NULL)
	{
		q->head = q->tail = neww;
	}
	else
	{
		q->tail->next = neww;
		q->tail = neww;
	}
	q->size++;
 
 
}

(1).创建新结点，将新结点的next赋为NULL，并且把要插入的值赋值给新创建节点的val中。

(2).如果是最开始，也就是队列为空时，就要把头结点和尾结点都赋值为新创建的结点。

(3).如果不是最开始，就像单链表尾插一样。

(4).最后把size加一，方便要输出队列元素个数时，无需再O(n)遍历队列。

2.3 QueuePop 出队

void QueuePop(Queue* q)
{
	if (q->head != NULL)
	{
		node* temp = q->head->next;
		free(q->head);
		q->head = temp;
		q->size--;
	}
}

(1),如果队列不为空，则按单链表中头删方法，删除队头。

2.4 QueueFront 获取队头元素值

type QueueFront(Queue* q)
{
	if (q->head != NULL)
	{
		return q->head->val;
	}
	
	cout << "queue is empty" << endl;
	return -1;
}

(1).直接返回头结点的val值即可。

2.5 QueueBack 获取队尾元素值

type QueueBack(Queue* q)
{
	if (q->head != NULL)
	{
		return q->tail->val;
	}
	cout << "queue is empty" << endl;
	return -1;
}

(1).直接返回尾结点的val值即可。

2.6 QueueSize 返回元素个数

int QueueSize(Queue* q)
{
	return q->size;
}

(1).由于之前对size值的维护，所以直接返回size值即可。

2.7 QueueEmpty 判断队列是否为空

int QueueEmpty(Queue* q)
{
	return q->size == 0;
}

(1).如果size为0，则队列为空。否则不为空。

2.8 QueueDestroy 销毁队列

void QueueDestroy(Queue* q)
{
	node* cur = q->head;
 
	while (cur)
	{
		node* temp = cur->next;
		free(cur);
		cur = temp;
	}
	cur = NULL;
	q->head = NULL;
	q->tail = NULL;
	q->size = 0;
 
}

(1).遍历单链表，依次释放结点即可，最后把指针全部赋值为NULL。

完结