ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【数据结构初阶】栈和队列 [打印本页]

---

作者: 卖不甜枣    时间: 2024-6-11 15:02
标题: 【数据结构初阶】栈和队列
1. 栈

1.1 栈的概念及结构

栈：一种特别的线性表，其只允许在固定的一端进行插入和删除元素操纵。进行数据插入和删除操纵的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）（即最后面进的数据会最先出来）的原则。
压栈：栈的插入操纵叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操纵叫做出栈。出数据也在栈顶。
1.2 栈的实现

栈的实现一般可以利用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
   

• 访问效率：数组的随机访问特性意味着可以在常数时间内访问任何位置的元素，这对于栈的操纵尤为重要，因为栈的操纵总是在栈顶进行。
  
• 空间利用：与链表相比，数组不需要额外的空间来存储指针，这意味着数组的空间利用率更高。
  
• 缓存局部性：由于数组在内存中是连续的，因此具有更好的缓存局部性。当栈顶元素被访问时，相邻的元素也会被加载到缓存中，这大概会提高随后的栈操纵的速率。
  
• 实现简单：数组实现栈的逻辑相对简单，不需要维护额外的指针或是节点信息，这使得代码更加简便，也更容易维护和调试。
  
• 性能考量：在大多数情况下，数组实现的栈在性能上优于链表实现的栈，因为数组的入栈和出栈操纵只需要修改栈顶指针，而链表则需要动态分配节点并调整指针。
  
• 空间分配：数组实现的栈在初始化时大概需要分配较大的空间，这大概会导致肯定的空间浪费，尤其是在栈的大小远小于数组容量时。然而，这一点可以通过动态扩容的策略来缓解。
  

  别的，在选择栈的实现方式时，除了考虑性能因素外，还需要考虑实际应用场景中的具体需求。例如，假如栈的大小厘革非常频繁，那么链表实现大概更为符合，因为链表在插入和删除节点时不需要进行大量的数据复制。然而，假如栈的操纵主要是入栈和出栈，并且对性能有较高的要求，那么数组实现将是更好的选择。
  支持动态增长的栈：

1. typedef char STDataType;
2. typedef struct Stack
3. {
4.         STDataType* _a;
5.         int _top;                // 栈顶
6.         int _capacity;  // 容量
7. }Stack;

复制代码

 初始化栈 

1. void StackInit(Stack* ps)
2. {
3.         ps->_a = NULL;
4.         ps->_capacity = ps->_top = 0;
5. }

复制代码

入栈

1. void StackPush(Stack* ps, STDataType data)
2. {
3.         assert(ps);
4.         if (ps->_capacity == ps->_top)
5.         {
6.                 int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
7.                 STDataType* tmp = (STDataType*)realloc(ps->_a,sizeof(STDataType) * newcapacity);
8.                 if (tmp==NULL)
9.                 {
10.                         perror("realloc");
11.                         return;
12.                 }
13.                 ps->_a = tmp;
14.                 ps->_capacity = newcapacity;
15.         }
16.         ps->_a[ps->_top] = data;
17.         ps->_top++;
18. }

复制代码

 出栈

1. void StackPop(Stack* ps)
2. {
3.         assert(ps);
5.         ps->_top--;
6. }

复制代码

 获取栈顶元素 

1. STDataType StackTop(Stack* ps)
2. {
3.         assert(ps);
4.         assert(ps->_top > 0);
6.         return ps->_a[ps->_top - 1];
7. }

复制代码

 获取栈中有效元素个数

1. int StackSize(Stack* ps)
2. {
3.         assert(ps);
4.         return ps->_top;
5. }

复制代码

判空

检测栈是否为空，假如为空返回非零结果，假如不为空返回0  

1. int StackEmpty(Stack* ps)
2. {
3.         assert(ps);
4.         if (ps->_top == 0)
5.                 return 1;
6.         else
7.                 return 0;
8. }

复制代码

 烧毁栈 

1. void StackDestroy(Stack* ps)
2. {
3.         assert(ps);
5.         free(ps->_a);
6.         ps->_a == NULL;
7.         ps->_capacity = ps->_top = 0;
8. }

复制代码

2. 队列

2.1 队列的概念及结构

队列：只允许在一端进行插入数据操纵，在另一端进行删除数据操纵的特别线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操纵的一端称为队尾 出队列：进行删除操纵的一端称为队头。
2.2 队列的实现

队列也可以用数组和链表的结构实现，利用链表的结构实现更优一些，因为假如利用数组的结构，出队列在数组头上出数据，效率会比较低（因为数组头上出数据，需要把头后面的数据全部向前移，而链表只需要改背叛点的指向就行了）。
链表结构实现队列：

1. typedef struct QListNode
2. {
3.         struct QListNode* _next;
4.         QDataType _data;
5. }QNode;
7. // 队列的结构
8. typedef struct Queue
9. {
10.         QNode* _front;
11.         QNode* _rear;
12.         int size;
13. }Queue;

复制代码

初始化队列 

1. void QueueInit(Queue* q)
2. {
3.         assert(q);
4.         q->_front = NULL;
5.         q->_rear = NULL;
6.         q->size = 0;
7. }

复制代码

 队尾入队列

1. QNode* SLBuyNode(QDataType data)
2. {
3.         QNode* newNode = (QNode*)malloc(sizeof(QNode));
4.         if (newNode == NULL)
5.         {
6.                 perror("malloc");
7.                 return;
8.         }
9.         newNode->_next = NULL;
10.         newNode->_data = data;
11.         return newNode;
12. }
14. void QueuePush(Queue* q, QDataType data)
15. {
16.         QNode* newNode = SLBuyNode(data);
17.         if (q->_front == NULL)
18.         {
19.                 q->_front = q->_rear = newNode;
20.                 q->size++;
21.         }
22.         else
23.         {
24.                 q->_rear->_next = newNode;
25.                 q->_rear = q->_rear->_next;
26.                 q->size++;
27.         }
28. }

复制代码

队头出队列 

1. void QueuePop(Queue* q)
2. {
3.         assert(q&&q->_front);
4.         QNode* next = q->_front->_next;
5.         free(q->_front);
6.         if (next == NULL)
7.                 q->_front = q->_rear = next;
8.         else
9.                 q->_front = next;
10.         q->size--;
11. }

复制代码

 获取队列头部元素 

1. QDataType QueueFront(Queue* q)
2. {
3.         assert(q && q->_front);
4.         return q->_front->_data;
5. }

复制代码

 获取队列队尾元素 

1. QDataType QueueBack(Queue* q)
2. {
3.         assert(q && q->_rear);
4.         return q->_rear->_data;
5. }

复制代码

 获取队列中有效元素个数

1. int QueueSize(Queue* q)
2. {
3.         QNode* head = q->_front;
4.         int count = 0;
5.         while (head)
6.         {
7.                 head = head->_next;
8.                 count++;
9.         }
10.         return count;
11. }

复制代码

 判空

检测队列是否为空，假如为空返回非零结果，假如非空返回0 

1. int QueueEmpty(Queue* q)
2. {
3.         if (q->_front == NULL)
4.                 return 1;
5.         else
6.                 return 0;
7. }

复制代码

 烧毁队列

1. void QueueDestroy(Queue* q)
2. {
3.         assert(q);
4.         while (q->_front)
5.         {
6.                 QNode* next = q->_front->_next;
7.                 free(q->_front);
8.                 q->_front = next;
9.         }
10.         q->_rear = NULL;
11. }

复制代码

3. 栈和队列的面试题

3.1 队列实现栈


. - 力扣（LeetCode）

解题思路：

队列中的数据依照先进先出的原则，而栈中的数据依照后进先出的原则，以是要想队列实现栈，就需要让队列实现数据的后进先出，这时候我们就可以设置两个队列，其中一个队列入数据，当出数据的时候，就把除了最后一个数据的全部数据放到另一个队列中，然后从队列1出数据，这样就实现了后进先出。（如下图）
还有一个问题就是当入数据的时候该往哪个队列入数据呢？
假如是往空队列入数据的话，空队列就酿成了非空队列，这样就会导致两个队列都是非空队列，而无法分辨下一次该往哪个队列入数据。而往非空队列入数据则避免了这一情况，固然假如两个队列都为空，那就随便往一个队列入数据就可以了。

1. typedef int QDataType;// 链式结构：表现队列 typedef struct QListNode
2. {
3.         struct QListNode* _next;
4.         QDataType _data;
5. }QNode;
7. // 队列的结构
8. typedef struct Queue
9. {
10.         QNode* _front;
11.         QNode* _rear;
12.         int size;
13. }Queue;// 初始化队列 void QueueInit(Queue* q)
14. {
15.         assert(q);
16.         q->_front = NULL;
17.         q->_rear = NULL;
18.         q->size = 0;
19. }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)
20. {
21.         assert(q&&q->_front);
22.         QNode* next = q->_front->_next;
23.         free(q->_front);
24.         if (next == NULL)
25.                 q->_front = q->_rear = next;
26.         else
27.                 q->_front = next;
28.         q->size--;
29. }// 获取队列头部元素 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)
30. {
31.         QNode* head = q->_front;
32.         int count = 0;
33.         while (head)
34.         {
35.                 head = head->_next;
36.                 count++;
37.         }
38.         return count;
39. }// 检测队列是否为空，假如为空返回非零结果，假如非空返回0 int QueueEmpty(Queue* q)
40. {
41.         if (q->_front == NULL)
42.                 return 1;
43.         else
44.                 return 0;
45. }// 烧毁队列 void QueueDestroy(Queue* q)
46. {
47.         assert(q);
48.         while (q->_front)
49.         {
50.                 QNode* next = q->_front->_next;
51.                 free(q->_front);
52.                 q->_front = next;
53.         }
54.         q->_rear = NULL;
55. }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）

解题思路： 

栈中的数据依照后进先出的原则，而队列中的数据依照先进先出的原则，以是要想用栈实现栈，就需要让栈实现数据的先进先出，如下图我们可以设置两个栈，一个栈存放数据，另一个栈出数据。具体实现是：往非空的栈插入数据，出数据的时候将栈1的数据导入栈2，然后从栈2出数据，最后将栈的数据导回栈1，因为不导回数据的话根据栈后进先出的原则，会将插入的数据倒过来，假如直接将数据插入栈2，就会导致栈插入的数据顺序被打乱。

1. typedef int QDataType;// 链式结构：表现队列 typedef struct QListNode
2. {
3.         struct QListNode* _next;
4.         QDataType _data;
5. }QNode;
7. // 队列的结构
8. typedef struct Queue
9. {
10.         QNode* _front;
11.         QNode* _rear;
12.         int size;
13. }Queue;// 初始化队列 void QueueInit(Queue* q)
14. {
15.         assert(q);
16.         q->_front = NULL;
17.         q->_rear = NULL;
18.         q->size = 0;
19. }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)
20. {
21.         assert(q&&q->_front);
22.         QNode* next = q->_front->_next;
23.         free(q->_front);
24.         if (next == NULL)
25.                 q->_front = q->_rear = next;
26.         else
27.                 q->_front = next;
28.         q->size--;
29. }// 获取队列头部元素 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)
30. {
31.         QNode* head = q->_front;
32.         int count = 0;
33.         while (head)
34.         {
35.                 head = head->_next;
36.                 count++;
37.         }
38.         return count;
39. }// 检测队列是否为空，假如为空返回非零结果，假如非空返回0 int QueueEmpty(Queue* q)
40. {
41.         if (q->_front == NULL)
42.                 return 1;
43.         else
44.                 return 0;
45. }// 烧毁队列 void QueueDestroy(Queue* q)
46. {
47.         assert(q);
48.         while (q->_front)
49.         {
50.                 QNode* next = q->_front->_next;
51.                 free(q->_front);
52.                 q->_front = next;
53.         }
54.         q->_rear = NULL;
55. }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）

解题思路： 

1. typedef struct {
2.     int*_a;
3.     int head;
4.     int tail;
5.     int k;
6. } MyCircularQueue;
9. MyCircularQueue* myCircularQueueCreate(int k) {
10.     MyCircularQueue* tmp = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
11.     tmp->_a = (int*)malloc(sizeof(int)*(k+1));
12.     tmp->head=0;
13.     tmp->tail=0;
14.     tmp->k=k;
15.     return tmp;
16. }
18. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
19.     if((obj->tail+1)%(obj->k+1)==obj->head)
20.         return false;
21.     obj->_a[obj->tail] = value;
23.     obj->tail = (obj->tail+1)%(obj->k+1);
24.     return true;
25. }
27. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
28.     if(obj->tail==obj->head)
29.     {
30.         return false;
31.     }
32.     obj->head = (obj->head+1)%(obj->k+1);
33.     return true;
34. }
36. int myCircularQueueFront(MyCircularQueue* obj) {
37.     if(obj->head==obj->tail)
38.     {
39.         return -1;
40.     }
41.     return obj->_a[obj->head];
42. }
44. int myCircularQueueRear(MyCircularQueue* obj) {
45.     if(obj->head==obj->tail)
46.     {
47.         return -1;
48.     }
49.     return obj->_a[(obj->tail+obj->k)%(obj->k+1)];
50. }
52. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
53.     return obj->head==obj->tail;
54. }
56. bool myCircularQueueIsFull(MyCircularQueue* obj) {
57.     return (obj->tail+1)%(obj->k+1)==obj->head;
58. }
60. void myCircularQueueFree(MyCircularQueue* obj) {
61.     free(obj->_a);
62.     free(obj);
63.     obj->_a==NULL;
64. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4