栈和队列的实现【1】

2024-02-01 23:54:10

栈和队列

栈

一种特殊的线性表，其只允许在固定的一段进行插入和删除，进行数据的插入和删除操作的一端称为栈顶，另一端称为栈底

满足后进先出的规则（先对栈顶的数据）

  • 压栈 入数据在栈顶

  • 出栈 出数据也在栈顶

  • 栈：一种入栈顺序，多种出战顺序

栈的实现

推荐使用数组实现

主要函数接口的实现

bool StackEmpty(ST * ps)
{
	assert(ps);
	return ps->top = 0;
}
//初始化
void StackInit(ST * ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
//删除栈
void StackDestory(ST * ps)
{
	assert(ps);
	if (ps->a != NULL)
	{
		free(ps);
	}

	ps->capacity = 0;
	ps->top = 0;

}
//插入
void StackPush(ST * ps,int x)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		//三目操作符，不够了再增容
		int newcapacity = ps->capacity = 0 ? 4 : ps->capacity * 2;
		STDatatype * tmp = realloc(ps->a, sizeof(STDatatype));

		if (tmp == NULL)
		{
			printf("realloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	
	}

	ps->a[ps->top] = x;
	++ps->top;
}
//弹出栈顶的元素
void StackPop(ST * ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	--ps->top;
}
//获取栈顶的数据
void StackTop(ST * ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}
//栈内元素的个数
int StackSize(ST *ps)
{
	assert(ps);
	return ps->top;
}

队列的实现

队列：只允许在一端进行插入，在另一端进行删除数据操作的特殊线性表

  • 入队列：进行插入操作的一端称为队尾

  • 出队列：进行删除操作的一端称为队头

  • 队列：一种入队顺序，一种出队顺序

应用场景

  1. 保证公平排队
  2. 广度优先遍历

主要接口实现

typedef int QueueDatatype;
typedef struct QueueNode
{
	struct QueueNode * next;
	QueueDatatype data;
}QueueNode;

typedef struct Queue
{
	QueueNode * head;
	QueueNode * tail;
}Queue;

//链表的方式
bool QueueEmpty(Queue * pq)
{
	assert(pq);
	return pq->head == NULL && pq->tail == NULL;
}
void QueueInit(Queue*pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

void QueuePush(Queue * pq, QueueDatatype x)
{
	assert(pq);
	QueueNode * newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)//当只有一个节点或者是空节点
	{
		printf("newnode fail\n");
		exit(0);
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->head == NULL)//就是链表的尾插
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

void QueuePop(Queue * pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)//只有一个节点，并且要小心free掉之后野指针的问题
	{
		free(pq->head);
		pq->head = pq->tail= NULL;
	}
	else
	{
		QueueNode * next = pq->head->next;//????
		free(pq->head);
		pq->head = next;
	}
}

void QueueDestory(Queue * pq)
{
	assert(pq);
	QueueNode * cur = pq->head;
	while (cur)
	{
		QueueNode * next = cur->next;
		free(cur);

		cur = next;
	}
	pq->head = pq->tail = NULL;
}

QueueDatatype QueueFront(Queue * pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

QueueDatatype QueueBack(Queue * pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

int QueueSize(Queue * pq)//如果很少调用可以用这样的方式，如果频繁调用可以在结构体中加个size直接加加就可以
{
	assert(pq);
	QueueNode * cur = pq->head;
	int sz = 0;
	while (cur)
	{
		sz++;
		cur = cur->next;//让cur迭代往下走
	}
	return sz;
}

int main()
{
	Queue pq;
	QueueInit(&pq);
	QueuePush(&pq, 1);
	QueuePush(&pq, 2);
	QueuePush(&pq, 3);
	QueuePush(&pq, 4);
	//想要遍历一遍打印，取队头的数据，再pop一下这样就可以取下一个依次打印，但是会把原有的结构破坏掉
	while (!QueueEmpty(&pq))
	{
		printf("%d ", QueueFront(&pq));
		QueuePop(&pq);
	}
	printf("\n");
	return 0;
}

链式访问

通过内部要修改外部的方法

  1. 传二级指针（传指针，解引用改变）
  2. 返回值 （接收返回值，在不频繁调用的情况下）
  3. 带哨兵位的头节点 （不改变，但是方便尾删尾插或者不想传二级指针）
  4. 结构体包在一起 （传地址，结构体指针）结构体里再涵盖一个结构体

循环队列

循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。(队列满了并没有删除数据，而是直接覆盖掉之前的数据，再去使用原来的空间)

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/design-circular-queue

  1. 链表实现 单链表实现 单链表循环
  2. 数组实现

两者都可以实现循环链表，数组较优一些

栈和队列的实现【1】

改进方法

链表多给一个节点，数组在head和tail之间多给一块空间，删除数据链表是指针往后动，数组是控制下标来移动

节点一开始就是创建好的，出数据是head指针往后走，节点并不删除，入数据是往tail里放数据，不申请节点，tail往后走。

typedef struct
{
	int * a;
	int front;
	int rear;
	int k;
} MyCircularQueue;

bool myCircularQueueIsFull(MyCircularQueue* obj)
{
	assert(obj);
	//还是边界问题，当rear走到数组最后，rear的下一个逻辑上是数组的初始位置，但是物理上实际是数组k+1的位置 ，用模运算可以解决
	return (obj->rear + 1) % (obj->k + 1) == obj->front;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
	assert(obj);
	return obj->front == obj->rear;
}

MyCircularQueue* myCircularQueueCreate(int k)
{
	MyCircularQueue*q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	q->a = (int *)malloc(sizeof(int)*k + 1);        //循环队列多创建一个空间
	q->front = 0;
	q->rear = 0;
	q->k = k;
	return q;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
	assert(obj);
	if (myCircularQueueIsFull)
		return false;

	obj->a[obj->rear] = value;
	obj->rear++;
	//控制边界问题，是以下标来进行访问，要是超过数组下标就要将tail赋值到数组最开始的位置，来体现循环
	/*if(obj->rear == k+1)
	obj->rear = 0;*/
	obj->rear %= (obj->k + 1);
	return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
	assert(obj);
	if (myCircularQueueIsEmpty(obj))
		return false;
	++obj->front;
	obj->front %= (obj->k + 1);
	//出数据head往后走并不用删除，head往后走到时候再插入数据会把之前的覆盖掉
	return true;
}

int myCircularQueueFront(MyCircularQueue* obj)
{
	assert(obj);
	if (myCircularQueueIsEmpty(obj))
		return -1;

	return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj)
{
	assert(obj);
	if (myCircularQueueIsEmpty(obj))
		return -1;

	//如果rear在数组最开始的位置，rear的前一个数据在数组的k的位置
	int prevrear = obj->rear - 1;
	if (prevrear = 0)
		prevrear = obj->k;
	return obj->a[prevrear];
}

void myCircularQueueFree(MyCircularQueue* obj)
{
	assert(obj);
	free(obj->a);
	free(obj);
}
 myCircularQueueRear(MyCircularQueue* obj)
{
	assert(obj);
	if (myCircularQueueIsEmpty(obj))
		return -1;

	//如果rear在数组最开始的位置，rear的前一个数据在数组的k的位置
	int prevrear = obj->rear - 1;
	if (prevrear = 0)
		prevrear = obj->k;
	return obj->a[prevrear];
}

void myCircularQueueFree(MyCircularQueue* obj)
{
	assert(obj);
	free(obj->a);
	free(obj);
}
上一篇：两个有序数组间相加和的Topk问题


下一篇：JZ29：最小的K个数