欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构(栈和队列的链表方式实现)

程序员文章站 2024-01-24 17:34:22
...

:一种特殊的线性结构,删除与插入元素的一端为栈顶,另一端为栈底,栈中元素遵循先进后出LIFO((Last In First Out)的原则.
数据结构(栈和队列的链表方式实现)
栈的实现可以使用数组或者链表,我们今天主要使用链表实现,我们在前面已经谈了单链表的操作,关于栈和队列只不过是对链表加以限制,好了,我们直接开始。
一、链栈的定义和初始化

//结构定义
typedef int STData;
typedef struct StackNode{
	STData Data;
	struct StackNode *Next;
}StackNode,*Stack;
//初始化
void StackInit(Stack *phead){    
	assert(phead != NULL);
	*phead = NULL;
}

二、入栈

 //进栈(尾插)
	assert(phead != NULL);
void StackPush(Stack *phead, STData x){   
	StackNode *s = (StackNode *)malloc(sizeof(StackNode));
	s->Data = x;
	s->Next = *phead;
	*phead = s;
}

三、判栈空

bool IsEmpty(Stack phead){
	return phead == NULL;
}

四、出栈

//出栈
void StackPop(Stack *phead){
	assert(phead != NULL);
	StackNode *p = *phead;
	if (IsEmpty(*phead)){
		printf("栈为空,无法出栈\n");
		return;
	}
	*phead = (*phead)->Next;
	free(p);
}

五、遍历栈元素

void StackShow(Stack phead){
	StackNode *p = phead;
	while (p != NULL){
		printf("|%d|\n", p->Data);
		p = p->Next;
	}
	printf(" - \n");
}

六、取栈顶元素

//取栈顶元素
STData StackTop(Stack phead){
	assert(phead != NULL);
	return phead->Data;
}

七、栈中元素个数

//求栈的元素个数
int StackSize(Stack phead){
	StackNode *p = phead;
	int count = 0;
	while (p != NULL){
		count++;
		p = p->Next;
	}
	return count;
}

八、摧毁栈

//摧毁栈
void StackDestroy(Stack *phead){
	assert(phead != NULL);
	StackNode *p = (*phead)->Next;
	StackNode *q = NULL;
	while (p != NULL){
		q = p;
		*phead = p;
		p = p->Next;
		free(q);
	}
	free(phead);
}

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO(First In First Out) ,进行插入操作的一端称为队尾,进行删除操作的一端称为队头
数据结构(栈和队列的链表方式实现)
一、链式队列的定义与初始化

//链式队列结构定义
typedef struct QueueNode{
	QUData Data;
	struct QueueNode *Next;
}QueueNode;

typedef struct Queue{
	QueueNode *head;  //队头指针
	QueueNode *tail;   //队尾指针
}Queue;

二、入队

//入队
void QueueEn(Queue *pq, QUData x){
	assert(pq != NULL);
	QueueNode *s = (QueueNode *)malloc(sizeof(QueueNode));
	s->Data = x;
	s->Next = NULL;
	if (pq->head == NULL){
		pq->head = pq->tail = s;
	}
	else{
		pq->tail->Next = s;
		pq->tail = s;
	}
}

三、出队

//出对
void QueueDe(Queue *pq){
	assert(pq != NULL);
	if (IsEmpty(pq)){
		printf("队列无元素,无法出对!\n");
		return;
	}
	QueueNode *p = pq->head;
	if (pq->head == pq->tail){
		pq->head = pq->tail = NULL;
	}
	else{
		pq->head = p->Next;
		free(p);
	}
}

四、遍历

//遍历
void QueueShow(Queue *pq){
	assert(pq != NULL);
	Queue *q = pq;
	while (q->head!=NULL){
		printf("%d ", q->head->Data);
		q->head = q->head->Next;
	}
}

五、取队头元素以及元素个数

//取队头元素
QUData QueueFront(Queue *pq){
	assert(pq != NULL);
	assert(IsEmpty(pq));
	return pq->head->Data;
}
//求队列元素个数
int QueueSize(Queue *pq){
	assert(pq != NULL);
	QueueNode *p = pq->head;
	int i = 0;
	while (p!= NULL){
		i++;
		p = p->Next;
	}
	return i;
}

六、判空

//判空
bool IsEmpty(Queue *pq){
	assert(pq != NULL);
	return pq->head == NULL;
}

七、摧毁队列

//摧毁队列
void QueueDestroy(Queue *pq){
	assert(pq != NULL);
	QueueNode *p = pq->head;
	while (p != NULL){
		pq->head = p->Next;
		free(p);
		p = pq->head;
	}
}

关于栈与队列的基本操作已经实现完成,大家如果有兴趣,可以取使用数组实现,在这里主要强调数组实现队列,有可能会出现“假满”状态,所以要懂得使用循环队列,后边我也会谈这个循环队列的实现,敬请期待!