【数据结构初阶】栈和队列
1. 栈1.1 栈的概念及结构
栈：一种特别的线性表，其只允许在固定的一端进行插入和删除元素操纵。进行数据插入和删除操纵的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）（即最后面进的数据会最先出来）的原则。
压栈：栈的插入操纵叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操纵叫做出栈。出数据也在栈顶。
1.2 栈的实现
栈的实现一般可以利用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
[*] 访问效率：数组的随机访问特性意味着可以在常数时间内访问任何位置的元素，这对于栈的操纵尤为重要，因为栈的操纵总是在栈顶进行。
[*] 空间利用：与链表相比，数组不需要额外的空间来存储指针，这意味着数组的空间利用率更高。
[*] 缓存局部性：由于数组在内存中是连续的，因此具有更好的缓存局部性。当栈顶元素被访问时，相邻的元素也会被加载到缓存中，这大概会提高随后的栈操纵的速率。
[*] 实现简单：数组实现栈的逻辑相对简单，不需要维护额外的指针或是节点信息，这使得代码更加简便，也更容易维护和调试。
[*] 性能考量：在大多数情况下，数组实现的栈在性能上优于链表实现的栈，因为数组的入栈和出栈操纵只需要修改栈顶指针，而链表则需要动态分配节点并调整指针。
[*] 空间分配：数组实现的栈在初始化时大概需要分配较大的空间，这大概会导致肯定的空间浪费，尤其是在栈的大小远小于数组容量时。然而，这一点可以通过动态扩容的策略来缓解。
别的，在选择栈的实现方式时，除了考虑性能因素外，还需要考虑实际应用场景中的具体需求。例如，假如栈的大小厘革非常频繁，那么链表实现大概更为符合，因为链表在插入和删除节点时不需要进行大量的数据复制。然而，假如栈的操纵主要是入栈和出栈，并且对性能有较高的要求，那么数组实现将是更好的选择。
支持动态增长的栈：
typedef char STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 栈顶
int _capacity;// 容量
}Stack; 初始化栈
void StackInit(Stack* ps)
{
ps->_a = NULL;
ps->_capacity = ps->_top = 0;
} 入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
if (ps->_capacity == ps->_top)
{
int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->_a,sizeof(STDataType) * newcapacity);
if (tmp==NULL)
{
perror("realloc");
return;
}
ps->_a = tmp;
ps->_capacity = newcapacity;
}
ps->_a = data;
ps->_top++;
} 出栈
void StackPop(Stack* ps)
{
assert(ps);
ps->_top--;
} 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->_top > 0);
return ps->_a;
} 获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->_top;
} 判空
检测栈是否为空，假如为空返回非零结果，假如不为空返回0
int StackEmpty(Stack* ps)
{
assert(ps);
if (ps->_top == 0)
return 1;
else
return 0;
} 烧毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->_a);
ps->_a == NULL;
ps->_capacity = ps->_top = 0;
} 2. 队列
2.1 队列的概念及结构
队列：只允许在一端进行插入数据操纵，在另一端进行删除数据操纵的特别线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操纵的一端称为队尾 出队列：进行删除操纵的一端称为队头。
2.2 队列的实现
队列也可以用数组和链表的结构实现，利用链表的结构实现更优一些，因为假如利用数组的结构，出队列在数组头上出数据，效率会比较低（因为数组头上出数据，需要把头后面的数据全部向前移，而链表只需要改背叛点的指向就行了）。
链表结构实现队列：
typedef struct QListNode
{
struct QListNode* _next;
QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* _front;
QNode* _rear;
int size;
}Queue; 初始化队列
void QueueInit(Queue* q)
{
assert(q);
q->_front = NULL;
q->_rear = NULL;
q->size = 0;
} 队尾入队列
QNode* SLBuyNode(QDataType data)
{
QNode* newNode = (QNode*)malloc(sizeof(QNode));
if (newNode == NULL)
{
perror("malloc");
return;
}
newNode->_next = NULL;
newNode->_data = data;
return newNode;
}
void QueuePush(Queue* q, QDataType data)
{
QNode* newNode = SLBuyNode(data);
if (q->_front == NULL)
{
q->_front = q->_rear = newNode;
q->size++;
}
else
{
q->_rear->_next = newNode;
q->_rear = q->_rear->_next;
q->size++;
}
} 队头出队列
void QueuePop(Queue* q)
{
assert(q&&q->_front);
QNode* next = q->_front->_next;
free(q->_front);
if (next == NULL)
q->_front = q->_rear = next;
else
q->_front = next;
q->size--;
} 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q && q->_front);
return q->_front->_data;
} 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q && q->_rear);
return q->_rear->_data;
} 获取队列中有效元素个数
int QueueSize(Queue* q)
{
QNode* head = q->_front;
int count = 0;
while (head)
{
head = head->_next;
count++;
}
return count;
} 判空
检测队列是否为空，假如为空返回非零结果，假如非空返回0
int QueueEmpty(Queue* q)
{
if (q->_front == NULL)
return 1;
else
return 0;
} 烧毁队列
void QueueDestroy(Queue* q)
{
assert(q);
while (q->_front)
{
QNode* next = q->_front->_next;
free(q->_front);
q->_front = next;
}
q->_rear = NULL;
} 3. 栈和队列的面试题
3.1 队列实现栈
. - 力扣（LeetCode）
https://img-blog.csdnimg.cn/direct/7126925a3efc44af90a7962e80ad287a.png
解题思路：
队列中的数据依照先进先出的原则，而栈中的数据依照后进先出的原则，以是要想队列实现栈，就需要让队列实现数据的后进先出，这时候我们就可以设置两个队列，其中一个队列入数据，当出数据的时候，就把除了最后一个数据的全部数据放到另一个队列中，然后从队列1出数据，这样就实现了后进先出。（如下图）
还有一个问题就是当入数据的时候该往哪个队列入数据呢？
假如是往空队列入数据的话，空队列就酿成了非空队列，这样就会导致两个队列都是非空队列，而无法分辨下一次该往哪个队列入数据。而往非空队列入数据则避免了这一情况，固然假如两个队列都为空，那就随便往一个队列入数据就可以了。
https://img-blog.csdnimg.cn/direct/4da04f89287f4892b58020cf388c2b71.png
typedef int QDataType;// 链式结构：表现队列 typedef struct QListNode
{
struct QListNode* _next;
QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* _front;
QNode* _rear;
int size;
}Queue;// 初始化队列 void QueueInit(Queue* q)
{
assert(q);
q->_front = NULL;
q->_rear = NULL;
q->size = 0;
}QNode* SLBuyNode(QDataType data){ QNode* newNode = (QNode*)malloc(sizeof(QNode)); if (newNode == NULL) { perror("malloc"); return 0; } newNode->_next = NULL; newNode->_data = data; return newNode;}// 队尾入队列 void QueuePush(Queue* q, QDataType data){ QNode* newNode = SLBuyNode(data); if (q->_front == NULL) { q->_front = q->_rear = newNode; q->size++; } else { q->_rear->_next = newNode; q->_rear = q->_rear->_next; q->size++; }}// 队头出队列 void QueuePop(Queue* q)
{
assert(q&&q->_front);
QNode* next = q->_front->_next;
free(q->_front);
if (next == NULL)
q->_front = q->_rear = next;
else
q->_front = next;
q->size--;
}// 获取队列头部元素 QDataType QueueFront(Queue* q){ assert(q); assert(q->_front); return q->_front->_data;}// 获取队列队尾元素 QDataType QueueBack(Queue* q){ assert(q); assert(q->_rear); return q->_rear->_data;}// 获取队列中有效元素个数 int QueueSize(Queue* q)
{
QNode* head = q->_front;
int count = 0;
while (head)
{
head = head->_next;
count++;
}
return count;
}// 检测队列是否为空，假如为空返回非零结果，假如非空返回0 int QueueEmpty(Queue* q)
{
if (q->_front == NULL)
return 1;
else
return 0;
}// 烧毁队列 void QueueDestroy(Queue* q)
{
assert(q);
while (q->_front)
{
QNode* next = q->_front->_next;
free(q->_front);
q->_front = next;
}
q->_rear = NULL;
}typedef struct { Queue q1; Queue q2;} MyStack;MyStack* myStackCreate() { MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&pst->q1); QueueInit(&pst->q2); return pst;}void myStackPush(MyStack* obj, int x) { if(QueueEmpty(&obj->q1)==0) { QueuePush(&obj->q1, x); } else{ QueuePush(&obj->q2, x); }}int myStackPop(MyStack* obj) { Queue* Empty = &obj->q1; Queue* nonEmpty = &obj->q2; if(QueueEmpty(&obj->q1)==0) { Empty = &obj->q2; nonEmpty = &obj->q1; } while(nonEmpty->size>1) { QueuePush(Empty, QueueFront(nonEmpty)); QueuePop(nonEmpty); } int top = QueueFront(nonEmpty); QueuePop(nonEmpty); return top;}int myStackTop(MyStack* obj) { if(QueueEmpty(&obj->q1)==0) { return QueueBack(&obj->q1); } else return QueueBack(&obj->q2);}bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);}void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj);} 3.2 用栈实现队列
标题描述：
. - 力扣（LeetCode）
https://img-blog.csdnimg.cn/direct/12eb0d95879d46c5a2b51acd61f8e1c5.png
解题思路：
栈中的数据依照后进先出的原则，而队列中的数据依照先进先出的原则，以是要想用栈实现栈，就需要让栈实现数据的先进先出，如下图我们可以设置两个栈，一个栈存放数据，另一个栈出数据。具体实现是：往非空的栈插入数据，出数据的时候将栈1的数据导入栈2，然后从栈2出数据，最后将栈的数据导回栈1，因为不导回数据的话根据栈后进先出的原则，会将插入的数据倒过来，假如直接将数据插入栈2，就会导致栈插入的数据顺序被打乱。
https://img-blog.csdnimg.cn/direct/a5acd005a5754370a84670c69534403a.png
typedef int QDataType;// 链式结构：表现队列 typedef struct QListNode
{
struct QListNode* _next;
QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* _front;
QNode* _rear;
int size;
}Queue;// 初始化队列 void QueueInit(Queue* q)
{
assert(q);
q->_front = NULL;
q->_rear = NULL;
q->size = 0;
}QNode* SLBuyNode(QDataType data){ QNode* newNode = (QNode*)malloc(sizeof(QNode)); if (newNode == NULL) { perror("malloc"); return 0; } newNode->_next = NULL; newNode->_data = data; return newNode;}// 队尾入队列 void QueuePush(Queue* q, QDataType data){ QNode* newNode = SLBuyNode(data); if (q->_front == NULL) { q->_front = q->_rear = newNode; q->size++; } else { q->_rear->_next = newNode; q->_rear = q->_rear->_next; q->size++; }}// 队头出队列 void QueuePop(Queue* q)
{
assert(q&&q->_front);
QNode* next = q->_front->_next;
free(q->_front);
if (next == NULL)
q->_front = q->_rear = next;
else
q->_front = next;
q->size--;
}// 获取队列头部元素 QDataType QueueFront(Queue* q){ assert(q); assert(q->_front); return q->_front->_data;}// 获取队列队尾元素 QDataType QueueBack(Queue* q){ assert(q); assert(q->_rear); return q->_rear->_data;}// 获取队列中有效元素个数 int QueueSize(Queue* q)
{
QNode* head = q->_front;
int count = 0;
while (head)
{
head = head->_next;
count++;
}
return count;
}// 检测队列是否为空，假如为空返回非零结果，假如非空返回0 int QueueEmpty(Queue* q)
{
if (q->_front == NULL)
return 1;
else
return 0;
}// 烧毁队列 void QueueDestroy(Queue* q)
{
assert(q);
while (q->_front)
{
QNode* next = q->_front->_next;
free(q->_front);
q->_front = next;
}
q->_rear = NULL;
}typedef struct { Queue q1; Queue q2;} MyStack;MyStack* myStackCreate() { MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&pst->q1); QueueInit(&pst->q2); return pst;}void myStackPush(MyStack* obj, int x) { if(QueueEmpty(&obj->q1)==0) { QueuePush(&obj->q1, x); } else{ QueuePush(&obj->q2, x); }}int myStackPop(MyStack* obj) { Queue* Empty = &obj->q1; Queue* nonEmpty = &obj->q2; if(QueueEmpty(&obj->q1)==0) { Empty = &obj->q2; nonEmpty = &obj->q1; } while(nonEmpty->size>1) { QueuePush(Empty, QueueFront(nonEmpty)); QueuePop(nonEmpty); } int top = QueueFront(nonEmpty); QueuePop(nonEmpty); return top;}int myStackTop(MyStack* obj) { if(QueueEmpty(&obj->q1)==0) { return QueueBack(&obj->q1); } else return QueueBack(&obj->q2);}bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);}void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj);} 3.3 设计循环队列
标题描述：
. - 力扣（LeetCode）
https://img-blog.csdnimg.cn/direct/ff3e201782f04deda243d2a8ce53466e.png
解题思路：
typedef struct {
int*_a;
int head;
int tail;
int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* tmp = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
tmp->_a = (int*)malloc(sizeof(int)*(k+1));
tmp->head=0;
tmp->tail=0;
tmp->k=k;
return tmp;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if((obj->tail+1)%(obj->k+1)==obj->head)
return false;
obj->_a = value;
obj->tail = (obj->tail+1)%(obj->k+1);
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(obj->tail==obj->head)
{
return false;
}
obj->head = (obj->head+1)%(obj->k+1);
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(obj->head==obj->tail)
{
return -1;
}
return obj->_a;
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(obj->head==obj->tail)
{
return -1;
}
return obj->_a[(obj->tail+obj->k)%(obj->k+1)];
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->head==obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->tail+1)%(obj->k+1)==obj->head;
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->_a);
free(obj);
obj->_a==NULL;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]