学习笔记之栈与队列

发表于 更新于 分类于

[学习笔记] 栈与队列

栈

栈， 限定尽在表尾进行插入和删除操作的线性表， last in first out （LIFO）

  • 栈顶： 插入和删除的一端
  • 栈底

顺序存储

链式存储

ls

栈的应用 - 递归

队列

顺序存储

建立大于n的数组， 并把队列所有元素存储再前n个单元，数组下标为0即为队头。

  • 插入： 队尾追加

  • 删除：每次删除对头，所有元素都要往前移动

改进1

出队不移动，不去限制元素必须在前n、添加两个指针front（对头），rear指向队尾下一个位置。 当front == rear时 队列为空 （假溢出： 删除导致数组前段为空，插入rear移动到下个位置可能数组越界）

改进2

防止假溢出，头尾相连- 循环队列。

队列满的条件：（rear + 1）% queueSize == front

链式存储

1. enqueue

s->next = null;
Q->rear->next = s;
Q->rear = s;

2. dequeue

Screen Shot 2020-07-28 at 9.18.40 PM 
p = Q->front->next;
Q-> front -> next = p->next;

if(Q->rear == p) {
	Q->rear = Q->front;
}

free(p)