数据结构与算法-栈和队列的数组实现、具有最小元素的栈

程序员文章站 2022-06-03 13:38:13

...

栈（stack）是一种以后进先出为顺序对对象进行添加或者删除的数据结构，是一种只允许在一端进行插入删除的线性表。可以把栈想象成桌子上的一堆书，可以在这堆书的顶部放上一本书就是入栈，或者把这堆书最顶部的一本书拿走就是出栈，但是你不能直接抽出来书堆中间的书，只能对书堆顶部一本书操作。

1、栈的数组实现

栈的数组实现相比链表容易多了，起码没有指向指针的指针了，实现起来压栈（入栈）无非是将新元素增加到栈顶，而弹栈（出栈）就是将栈顶的元素移除。那么我们需要一个数组来表示栈，还需要一个变量表示当前栈顶的位置。

可以给出栈的结构体

typedef struct STACK_KWEN{
	int top;			//栈顶指针
	int *data;			//存储空间
	int capacity;     //表示栈中最大存储长度
}STACK_KWEN;

有了结构体下一步就是初始化栈了，在初始化之前要进行一个有必要的判断，设置的长度是否超过了最大长度，以及小于等于0的长度等等。初始化栈主要就是：给结构体中的data分配指定长度的空间，初始化栈顶指针为-1，表示当前是一个空栈。

boolean initializeStack(STACK_KWEN **stackHead, int capacity) {
	if(NULL == stackHead || capacity > MAX_SIZE || capacity <= 0 || NULL != *stackHead) {
		return false;
	}

	*stackHead = (STACK_KWEN *)calloc(sizeof(STACK_KWEN), 1);
	(*stackHead)->capacity = capacity;
	(*stackHead)->top = -1;
	(*stackHead)->data = (int *)calloc(sizeof(int), capacity);
	if(NULL == (*stackHead)->data) {  //表示没有分配到空间
		free(*stackHead);
		return false;
	}

	return true;
}

栈的销毁。由于栈里面真正存放数组部分是动态申请的，完了必须要手动释放掉，否则会造成野指针、内存泄漏的现象。没有什么逻辑可言，释放空间指针置为空即可。

void destoryStack(STACK_KWEN **stackHead) {
	if(NULL  == stackHead || NULL == *stackHead) {
		return;
	}

	free((*stackHead)->data);
	free(*stackHead);
	*stackHead = NULL;
}

2、入栈

入栈前要判断栈是否满了，满了就不能再入栈了。

没满的话可以正常入栈入栈的时候应该先把栈顶指针往上移动一个单位，这里就是前置的++，再进行数组赋值。

boolean push(STACK_KWEN *stackHead, const int push_data) {
	if(NULL == stackHead || isStackFull(stackHead)) {
		//如果栈满 则返回 此时不能入栈
		return false;
	}

	stackHead->data[++stackHead->top] = push_data;

	return true;
}

3、出栈

出栈前则要判断栈是否空，栈都空了还拿什么出栈。

出栈的时候要先得到出栈的元素再往下移动栈顶指针，所以这里下标是后置--运算。

int pop(STACK_KWEN *stackHead) {
	if(isStackEmpty(stackHead) || NULL == stackHead) {
		return ERROR;
	}

	return stackHead->data[stackHead->top--];
}

在java中栈的数据结构还提供了一个方法peek( )，peek的意思是偷看，这个方法的功能是查看栈顶的元素，元素并不出栈，不移动栈顶指针。

简而言之就是查看当前栈顶的元素，前提这不是一个空栈，直接获得栈顶下标的数组元素即可。

const int readTop(STACK_KWEN *stackHead) {
	if(isStackEmpty(stackHead) || NULL == stackHead) {
		return ERROR;
	}

	return stackHead->data[stackHead->top];
}

所有的代码

#include<stdio.h>
#include<malloc.h>

#define MAX_SIZE	1000

typedef unsigned char boolean;

#define true	1
#define false	0
typedef struct STACK_KWEN{
	int top;			//栈顶指针
	int *data;			//存储空间
	int capacity;     //表示栈中最大存储长度
}STACK_KWEN;

boolean initializeStack(STACK_KWEN **stackHead, int capacity);
boolean push(STACK_KWEN *stackHead, const int push_data);
int pop(STACK_KWEN *stackHead);
void destoryStack(STACK_KWEN **stackHead);
boolean isStackFull(STACK_KWEN *stackHead);
boolean isStackEmpty(STACK_KWEN *stackHead);
const int readTop(STACK_KWEN *stackHead);

const int readTop(STACK_KWEN *stackHead) {
	if(isStackEmpty(stackHead) || NULL == stackHead) {
		return ERROR;
	}

	return stackHead->data[stackHead->top];
}

boolean isStackEmpty(STACK_KWEN *stackHead) {
	if(NULL == stackHead) {
		return false;  //not initialize
	}

	return stackHead->top <= -1;
}

boolean isStackFull(STACK_KWEN *stackHead) {
	if(NULL == stackHead) {
		return false;  //not initialize
	}

	return stackHead->top >= stackHead->capacity;
}

boolean push(STACK_KWEN *stackHead, const int push_data) {
	if(NULL == stackHead || isStackFull(stackHead)) {
		//如果栈满 则返回 此时不能入栈
		return false;
	}

	stackHead->data[++stackHead->top] = push_data;

	return true;
}

int pop(STACK_KWEN *stackHead) {
	if(isStackEmpty(stackHead) || NULL == stackHead) {
		return ERROR;
	}

	return stackHead->data[stackHead->top--];
}

void destoryStack(STACK_KWEN **stackHead) {
	if(NULL  == stackHead || NULL == *stackHead) {
		return;
	}

	free((*stackHead)->data);
	free(*stackHead);
	*stackHead = NULL;
}

boolean initializeStack(STACK_KWEN **stackHead, int capacity) {
	if(NULL == stackHead || capacity > MAX_SIZE || capacity <= 0 || NULL != *stackHead) {
		return false;
	}

	*stackHead = (STACK_KWEN *)calloc(sizeof(STACK_KWEN), 1);
	(*stackHead)->capacity = capacity;
	(*stackHead)->top = -1;
	(*stackHead)->data = (int *)calloc(sizeof(int), capacity);
	if(NULL == (*stackHead)->data) {  //表示没有分配到空间
		free(*stackHead);
		return false;
	}

	return true;
}

int main(void) {
	STACK_KWEN *stack = NULL;

	initializeStack(&stack, 10);
	
	printf("%d\n",push(stack, 2));
	printf("%d\n", push(stack, 3));
	printf("%d\n", push(stack, 4));

	printf("%d\n", pop(stack));
	printf("%d\n", pop(stack));
	printf("%d\n", pop(stack));
	printf("%d\n", pop(stack));

	destoryStack(&stack);

	return 0;
}	1
#define false	0
typedef struct STACK_KWEN{
	int top;			//栈顶指针
	int *data;			//存储空间
	int capacity;     //表示栈中最大存储长度
}STACK_KWEN;

boolean initializeStack(STACK_KWEN **stackHead, int capacity);
boolean push(STACK_KWEN *stackHead, const int push_data);
int pop(STACK_KWEN *stackHead);
void destoryStack(STACK_KWEN **stackHead);
boolean isStackFull(STACK_KWEN *stackHead);
boolean isStackEmpty(STACK_KWEN *stackHead);
const int readTop(STACK_KWEN *stackHead);

const int readTop(STACK_KWEN *stackHead) {
	if(isStackEmpty(stackHead) || NULL == stackHead) {
		return ERROR;
	}

	return stackHead->data[stackHead->top];
}

boolean isStackEmpty(STACK_KWEN *stackHead) {
	if(NULL == stackHead) {
		return false;  //not initialize
	}

	return stackHead->top <= -1;
}

boolean isStackFull(STACK_KWEN *stackHead) {
	if(NULL == stackHead) {
		return false;  //not initialize
	}

	return stackHead->top >= stackHead->capacity;
}

boolean push(STACK_KWEN *stackHead, const int push_data) {
	if(NULL == stackHead || isStackFull(stackHead)) {
		//如果栈满 则返回 此时不能入栈
		return false;
	}

	stackHead->data[++stackHead->top] = push_data;

	return true;
}

int pop(STACK_KWEN *stackHead) {
	if(isStackEmpty(stackHead) || NULL == stackHead) {
		return ERROR;
	}

	return stackHead->data[stackHead->top--];
}

void destoryStack(STACK_KWEN **stackHead) {
	if(NULL  == stackHead || NULL == *stackHead) {
		return;
	}

	free((*stackHead)->data);
	free(*stackHead);
	*stackHead = NULL;
}

boolean initializeStack(STACK_KWEN **stackHead, int capacity) {
	if(NULL == stackHead || capacity > MAX_SIZE || capacity <= 0 || NULL != *stackHead) {
		return false;
	}

	*stackHead = (STACK_KWEN *)calloc(sizeof(STACK_KWEN), 1);
	(*stackHead)->capacity = capacity;
	(*stackHead)->top = -1;
	(*stackHead)->data = (int *)calloc(sizeof(int), capacity);
	if(NULL == (*stackHead)->data) {  //表示没有分配到空间
		free(*stackHead);
		return false;
	}

	return true;
}

int main(void) {
	STACK_KWEN *stack = NULL;

	initializeStack(&stack, 10);
	
	printf("%d\n",push(stack, 2));
	printf("%d\n", push(stack, 3));
	printf("%d\n", push(stack, 4));

	printf("%d\n", pop(stack));
	printf("%d\n", pop(stack));
	printf("%d\n", pop(stack));
	printf("%d\n", pop(stack));

	destoryStack(&stack);

	return 0;
}

很多算法会用到栈，比如逆置一个数组，求表达式的运算等，栈这种先进后出的特性就回派上用场。

完成一个具有当前栈中最小元素的数据结构，也就是每次访问栈顶就能得到栈中最小的元素。

思路就是每次存放在栈中的元素不单纯的只保存数据，同时还包含一个属性：最小值，栈中的每个元素就是一个结构体，而这个结构包括两个成员一个时数据，一个是当前最小的值，当然你也可也增加一个当前最大，在入栈的时候比较入栈元素的值是否比栈顶元素中保存的最小值小，小的话就替换掉，反之则保持不变。

那么栈的存储方式就应该做相应的变换

typedef struct STACK_ELE {
	USER_TYPE minData;
	USER_TYPE data;
}STACK_ELE;

typedef struct MEC_STACK {
	int topIndex;
	STACK_ELE *stack_data;
}MEC_STACK;

有了以上的结构体，完成一个最小元素的栈，主要是在入栈时有所不同，需要加上：比较新的元素和当前栈顶元素中存放的最小元素，然后做响应的操作，是更新最小还是保持不变的操作。

int compare(USER_TYPE pushData, USER_TYPE nowMinData) {
	return pushData < nowMinData ? LESSTHAN : NOTLESSTHAN;
}

boolean push(MEC_STACK *stackHead, USER_TYPE pushData, int (*compare)(USER_TYPE, USER_TYPE)) {
	STACK_ELE newEle = {0};

	if(!isStackFull(stackHead)) {
		printf("Stack is Full!");
		return FALSE;
	}

	newEle.data = pushData;
	newEle.minData = (isStackEmpty(stackHead)) ? pushData : (compare(pushData, stackHead->stack_data[stackHead->topIndex].minData) == LESSTHAN ? pushData : stackHead->stack_data[stackHead->topIndex].minData);
	stackHead->stack_data[++stackHead->topIndex] = newEle;

	return TRUE;
}

其他地方和普通的栈没有什么区别是完全的一样的。

----------------------------------------------------------------------------------------------------------------------------------

队列是一种以先进先出为顺序对对象进行添加和删除的数据结构。队列就如同去超市排队结账，买好东西后加入到当前结账队伍的末尾等待，当终于到了队伍的前端，收银员就会收走你的钱给你小票就可以出去超市了。队列它只允许插入在表的一端（队尾rear）进行，而删除在表的另一端（头部front）进行，和栈相似，队列主要有：入队、出队、队满、队空等。

队列的实现可以通过链表或者数组，通过链表实现的队列，也称链队列，这种实现的方法较数组要简单，并且入队出队也更简单，入队的时候就在尾巴后面追加就行，出队的时候就出去头结点后面一个节点就行，不涉及移动更多的元素，只需要对链表头部和尾部进行操作，唯一不足的是每次需要遍历到链表的尾部。数组同样也可以实现队列，实际上它是一个循环数组，通过front和rear来记录队列的头和尾，队列的元素就在头至尾这段，把循环数组可以想成是一个圈。本篇文章的队列便是用数组实现的。

typedef struct QUENE {
	DataQueneType *data;
	int maxRoom;
	int rear;   //只允许在后端进行插入操作
	int front;   //只允许在前端进行删除操作
	boolean flag;  
}QUENE;

数据结构与算法-栈和队列的数组实现、具有最小元素的栈

因为在初始化的时候头尾指针都是在0的位置，也可以给成-1，只是细节上的区别。

1、队列的初始化和销毁

初始化队列需要设置队列的长度，可以容纳多少个元素，结构体里面的flag作用是：判断队空队满起作用，后续会讲。

void initializeQuene(QUENE **queneHead, int maxRoom) {
	if(NULL != *queneHead || maxRoom <= 0) {
		return;
	}

	(*queneHead) = (QUENE *)calloc(sizeof(QUENE), 1);
	if(NULL == *queneHead) {	
		return;
	}

	(*queneHead)->data = (DataQueneType *)calloc(sizeof(int), maxRoom);
	if((*queneHead)->data == NULL) {
		// 没有分配到空间
		free(*queneHead);
		return;
	}
	
	(*queneHead)->maxRoom = maxRoom;
	(*queneHead)->rear = (*queneHead)->front = 0;  //这里初始化给成-1要更合适点
	(*queneHead)->flag = false;
}

销毁释放掉申请的数组空间还给堆空间。

void destoryQuene(QUENE **queneHead) {
	if(NULL == *queneHead || NULL == queneHead) {
		return;
	}

	free((*queneHead)->data);
	free(*queneHead);
	*queneHead = NULL;
}

如何判断队列的队满，队空?

一个新元素入队前要判断队是不是满了，由于是在循环链表中，队满和队空的情况都是头尾指针在相同的位置，所以判断队满队空就不能直接判断头尾指针是不是在相同的位置，有两种方法可以判断队满队空。

1、再给结构体里面加一个成员count记录当前有多少个元素，每次入队一个就count++，反之出队就count--，这样子就很简单的判断队满队空，队满就是count == maxRoom，队空就是count == 0。

2、结构体里面加一个bool类型的标记，开始的时候是false，每每入队一次，flag=true，表示最新的一次操作是入队。而每每出队一次flag= false，表明最新的一次操作是出队操作。那么有了这个标记的作用，在判断队满的时候，上一次的操作是如队并且头尾指针相同，队空的条件就是，上一次的操作是出队并且头尾指针相同。

1、入队和队满

入队前先判断队列是否满了，在不满的前提下再进行入队，由于初始化的时候rear在0的位置，那么就先赋值，再移动头指针。

boolean isQueneFull(QUENE *queneHead) {

boolean isQueneEmpty(QUENE *queneHead) {
	return false == queneHead->flag && queneHead->rear == queneHead->front;
}

void DeQuene(QUENE *queneHead, DataQueneType *data) {
	if(isQueneEmpty(queneHead)) {
		printf("Quene is empty!\n");
		return;
	}

	*data = queneHead->data[queneHead->front];
	queneHead->front = (queneHead->front + 1) % queneHead->maxRoom;
	queneHead->flag = false;
}

2、出队和队空

同样出队前判断队里面还存在元素否，没有元素就不能再出队了。

boolean isQueneEmpty(QUENE *queneHead) {
	return false == queneHead->flag && queneHead->rear == queneHead->front;
}

void DeQuene(QUENE *queneHead, DataQueneType *data) {
	if(isQueneEmpty(queneHead)) {
		printf("Quene is empty!\n");
		return;
	}

	*data = queneHead->data[queneHead->front];
	queneHead->front = (queneHead->front + 1) % queneHead->maxRoom;
	queneHead->flag = false;
}

入队的过程是一个尾指针front去追赶头指针front的过程，等到rear追上了front，队列也就满了，而出队反之，出队是头指针front去追赶尾指针rear的过程，追赶上了队列也就空了。

用两个栈实现一个队列的功能： 队列的进出顺序和栈是完全相反的，思考如何用两个栈来实现一个队列，既然栈的进出顺序是相反的，也就是把一组元素全部入栈后再出栈，这组元素的顺序就完全逆置，那么再全部入栈一次出栈一次就得到了和初始顺序相同的序列，那么思路就是，先把元素全部入栈到栈1后，再把栈1的元素倒到栈2里面，需要入队出队就用栈2即可，达到队列的效果。

完整的代码

#ifndef _KWEN_QUENE_H_
#define _KWEN_QUENE_H_

#include<malloc.h>

#include"../../include/kwenbase.h"

typedef int DataQueneType;

typedef struct QUENE {
	DataQueneType *data;
	int maxRoom;
	int rear;   //只允许在后端进行插入操作
	int front;   //只允许在前端进行删除操作
	boolean flag;  
}QUENE;

//对一个新的队列初始化，头尾指针均为0，根据传递进来的maxRoom申请队列数据空间
void initializeQuene(QUENE **queneHead, int maxRoom);

//入队操作，若队未满，可以入队，入队在尾指针rear处操作，rear指针去追赶头指针front
boolean EnQuene(QUENE *queneHead, DataQueneType data);

//出队操作，若队未空，可以出队，出队在头指针front操作，front指针去追赶指针rear
void DeQuene(QUENE *queneHead, DataQueneType *data);

// 销毁一个队列
void destoryQuene(QUENE **queneHead);

//判断队空队满不能像判断栈一样去判断top指针，队列是一个环形结构
//存在front == rear时候，队满队空都有可能存在
//说明两种方法：
//1、结构体增加一个记录队列实际元素的count，入队成功一个count++，出队成功一个count--
//2、结构体添加一个bool类型标记，
// 判断队是否为空，队空有两个前提，头尾指针相遇，并且当前flag是false，也就是上一次做的是出队操作
// 出队的时候flag= 0，出队的时候是头指针front去追赶尾指针rear，当front==rear && flag = 0，说明此时队空
boolean isQueneEmpty(QUENE *queneHead);

//入队的时候flag= 1,入队的时候是尾指针rear去追赶头指针front，当rear==front && flag == 1说明 此时队满
//此时的flag为true并且头尾指针相遇,说明上一次做的是入队操作,此时已经队满了
boolean isQueneFull(QUENE *queneHead);

boolean isQueneFull(QUENE *queneHead) {
	return true == queneHead->flag && queneHead->rear == queneHead->front;
}

boolean isQueneEmpty(QUENE *queneHead) {
	return false == queneHead->flag && queneHead->rear == queneHead->front;
}

void DeQuene(QUENE *queneHead, DataQueneType *data) {
	if(isQueneEmpty(queneHead)) {
		printf("Quene is empty!\n");
		return;
	}

	*data = queneHead->data[queneHead->front];
	queneHead->front = (queneHead->front + 1) % queneHead->maxRoom;
	queneHead->flag = false;
}

boolean EnQuene(QUENE *queneHead, DataQueneType data) {
	if(isQueneFull(queneHead)) {
		printf("Quene is Full! no EnQuene!\n");
		return false;
	}

	queneHead->data[queneHead->rear] = data;
	queneHead->rear = (queneHead->rear + 1) % queneHead->maxRoom;
	queneHead->flag = true;

	return true;
}

void destoryQuene(QUENE **queneHead) {
	if(NULL == *queneHead || NULL == queneHead) {
		return;
	}

	free((*queneHead)->data);
	free(*queneHead);
	*queneHead = NULL;
}

void initializeQuene(QUENE **queneHead, int maxRoom) {
	if(NULL != *queneHead || maxRoom <= 0) {
		return;
	}

	(*queneHead) = (QUENE *)calloc(sizeof(QUENE), 1);
	if(NULL == *queneHead) {	
		return;
	}

	(*queneHead)->data = (DataQueneType *)calloc(sizeof(int), maxRoom);
	if((*queneHead)->data == NULL) {
		// 没有分配到空间
		free(*queneHead);
		return;
	}
	
	(*queneHead)->maxRoom = maxRoom;
	(*queneHead)->rear = (*queneHead)->front = 0;  //这里初始化给成-1要更合适点
	(*queneHead)->flag = false;
}


#endif

#include<stdio.h>

#include"../../include/kwenquene.h"

int main(void) {
	QUENE *quene = NULL;
	int i;
	const int maxRoom = 5;
	int dequenedata;

	initializeQuene(&quene, maxRoom);
	EnQuene(quene, 2);
	EnQuene(quene, 3);
	EnQuene(quene, 4);
	EnQuene(quene, 5);
	EnQuene(quene, 6);

	while(0 == isQueneEmpty(quene)) {
		DeQuene(quene, &dequenedata);
		printf("%d\n", dequenedata);
	}

	destoryQuene(&quene);

	return 0;
}

相关标签：数据结构与算法栈队列

上一篇：导入excel文件时疏失在线求解

下一篇： Python实现股市信息下载的方法

数据结构与算法-栈和队列的数组实现、具有最小元素的栈

程序员代码面试指南 python实现（第一章栈和队列 :最大值减去最小值小于或等于num的子数组数量）

算法之路_17、用数组结构实现大小固定的队列和栈