栈和队列的实现【1】

栈和队列

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

满足后进先出的规则(先对栈顶的数据)

  • 压栈 入数据在栈顶

  • 出栈 出数据也在栈顶

  • 栈:一种入栈顺序,多种出战顺序

栈的实现

推荐使用数组实现

主要函数接口的实现

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个数