• 【C语言 - 数据结构】浅析栈和队列

    对于线性表，我们可能要执行下列操作：访问表的第k个结点、在k这个结点之前或者之后插入一个新结点，抑或是删除第k个结点等等操作，其中我们会遇到值对第一个或者最后一个结点插入、删除、和访问值的线性表，我们给它们以特殊的名称：栈、队列、双端队列。

    让我们一起用热爱奔赴山海！

     

    文章目录

    • 一、栈、队列以及双端队列的概念
    • 二、栈的实现（动态）和模拟静态栈
    • 三、队列的实现（动态）和模拟静态队列
    • 四、leetcode-栈实现队列和用队列实现栈
    • 总结

    提示：以下是本篇文章正文内容，下面案例可供参考

    一、栈、队列以及双端队列的概念

    1.1栈的概念及结构

    栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

    压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

    出栈：栈的删除操作叫做出栈。出数据也在栈顶

     1.2队列的概念及结构

    队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)

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

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

    1.3双端队列的概念及结构

     双端队列：是一种线性表，又称为双向队列，所有的插入和删除（通常还有所有的访问）都在表的两端进行。

     

    二、栈的实现和模拟栈

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

     

    2.1 实现一个支持动态增长的栈

    头文件：

    1. #pragma once
    2.  
    3. #include<stdio.h>
    4. #include<stdlib.h>
    5. #include<stdbool.h>
    6. #include<assert.h>
    7. typedef int STDataType;
    8. typedef struct Stack//动态栈
    9. {
    10. 	int *a;
    11. 	int top;//栈顶的位置
    12. 	int capacity;//容量
    13. }ST;
    14. STDataType StackTop(ST* ps);//返回栈顶的值
    15. void StackInit(ST* ps);//初始化栈
    16. void StackDestory(ST* ps);//销毁栈
    17. void StackPop(ST* ps);//弹出
    18. void StackPush(ST* ps, STDataType x);//插入
    19. bool StackEmpty(ST* ps);//判断栈是否为空。

    源文件：

     

    1. #include"Stack.h"
    2.  
    3.  
    4. void StackInit(ST* ps)//栈的初始化
    5. {
    6. 	assert(ps);
    7. 	ps->a = NULL;//a点的值指向空
    8. 	ps->top = 0;//栈底为0
    9. 	ps->capacity = 0;//空间为0
    10. }
    11. void StackDestory(ST* ps)
    12. {
    13. 	assert(ps);
    14. 	free(ps->a);//把a释放掉
    15. 	ps->a = NULL;
    16. 	ps->capacity = ps->top = 0;
    17. }
    18. void StackPush(ST* ps, STDataType x)//入数据
    19. {
    20. 	assert(ps);
    21. 	//满了就扩容
    22. 	if (ps->top == ps->capacity)//如果栈的栈顶恰好和容量相等就扩容
    23. 	{
    24. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    25. 		ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
    26. 		if (ps->a == NULL)
    27. 		{
    28. 			printf("realloc fail\n");
    29. 			exit(-1);
    30. 		}
    31.  
    32. 		ps->capacity = newCapacity;//新的空间赋给旧的
    33. 	}
    34. 	ps->a[ps->top] = x;//栈顶插入x;
    35. 	ps->top++;//top++
    36. }
    37. void StackPop(ST* ps)
    38. {
    39. 	assert(ps);
    40. 	assert(ps->top > 0);
    41. 	--ps->top;//top--就相当于删除操作
    42. }
    43. bool StackEmpty(ST* ps)
    44. {
    45. 	assert(ps);
    46. 	//两种写法
    47. 	//if (ps->top > 0)
    48. 	//{
    49. 	//	return false;
    50. 	//}
    51. 	//else
    52. 	//{
    53. 	//	return true;
    54. 	//}
    55. 	return ps->top == 0;
    56. }
    57. STDataType StackTop(ST* ps)
    58. {
    59. 	assert(ps);
    60. 	assert(ps->top > 0);
    61. 	return ps->a[ps->top - 1];//访问栈顶元素（这里因为top我们设为0，所以访问栈顶元素相当于top-1
    62. }
    63. int StackSize(ST* ps)
    64. {
    65. 	assert(ps);
    66.  
    67. 	return ps->top;
    68. }

     2.2数组模拟静态栈

    1. #include<iostream>
    2. using namespace std;
    3. const int N = 1e6 + 10;
    4. int n;
    5. int stk[N];
    6. int top = - 1;
    7.  
    8. int main ()
    9. {
    10.     cin >> n;
    11.     while(n --)
    12.     {
    13.         string s;
    14.         cin >> s;
    15.         if(s == "push")
    16.         {
    17.             int a;
    18.             cin >> a;
    19.             stk[++top] = a;
    20.         }
    21.         if(s == "pop")
    22.         {
    23.             top--;
    24.         }
    25.         if(s == "empty")
    26.         {
    27.             if(top >= 0) printf("NO\n");
    28.             else printf("YES\n");
    29.         }
    30.         if(s == "query")
    31.         {
    32.             printf("%d\n", stk[top]);
    33.         }
    34.     }
    35.     return 0;
    36. }

    三、 队列的实现（动态）和模拟静态队列

    队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数 组头上出数据，效率会比较低。

     2.1 实现一个支持动态增长的栈

    头文件：

    1. #pragma once
    2.  
    3. #include<stdio.h>
    4. #include<stdlib.h>
    5. #include<stdbool.h>
    6. #include<assert.h>
    7.  
    8. typedef int QDataType;//方便改类型
    9.  
    10. typedef struct QueueNode//保存每个节点的数据
    11. {
    12. 	QDataType data;
    13. 	struct QueueNode* next;
    14. }QNode;
    15.  
    16. typedef struct Queue
    17. {
    18. 	QNode* head;
    19. 	QNode* tail;
    20. }Queue;
    21. //上面的写法等价于：
    22. //typedef struct Queue
    23. //{
    24. //	QNode* head;
    25. //	QNode* tail;
    26. //};
    27. //
    28. //typedef struct Queue Queue;//
    29. //一般实际情况哨兵位的头节点不存储值，不放数据
    30. void QueueInit(Queue* pq);//队列初始化
    31. void QueueDestory(Queue* pq);//队列销毁
    32. void QueuePush(Queue* pq, QDataType x);//队尾插入
    33. void QueuePop(Queue* pq);//弹出队头
    34. bool QueueEmpty(Queue* pq);//判断是否为空
    35. size_t QueueSize(Queue* pq);//size_t相当于Unsinged int
    36. QDataType QueueFront(Queue* pq);
    37. QDataType QueueBack(Queue* pq);

    源文件：

    1. #include"Queue.h"
    2. void QueueInit(Queue* pq)
    3. {
    4. 	assert(pq);
    5. 	pq->head = pq->tail = NULL;
    6. }
    7. void QueueDestory(Queue* pq)
    8. {
    9. 	assert(pq);
    10. 	QNode* cur = pq->head;
    11. 	while (cur)
    12. 	{
    13. 		QNode* next = cur->next;//先记录下一个位置
    14. 		free(cur);//free掉cur指针
    15. 		cur = next;//cur赋值到下一个位置
    16. 	}
    17. 	pq->head = pq->tail = NULL;//置空
    18. }
    19. void QueuePush(Queue* pq, QDataType x)//队尾插入//插入int类型的参数
    20. {
    21. 	assert(pq);
    22. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    23. 	assert(newnode);
    24. 	newnode->data = x;//新的节点的值被赋与x
    25. 	newnode->next = NULL;//新的节点是在队尾，所以指向的下一个位置是空
    26. 	if (pq->tail == NULL)//如果链表的第一个值为空，则head = tail = NULL
    27. 	{
    28. 		assert(pq->head == NULL);
    29. 		pq->head = pq->tail = newnode;
    30. 	}
    31. 	else//尾插
    32. 	{
    33. 		pq->tail->next = newnode;//先改指向
    34. 		pq->tail = newnode;//再改地址
    35. 	}
    36. }
    37. void QueuePop(Queue* pq)//弹出队首
    38. {
    39. 	assert(pq);
    40. 	assert(pq->head && pq->tail);
    41. 	if (pq->head->next == NULL)//只有一个节点
    42. 	{
    43. 		free(pq->head);
    44. 		pq->head = pq->tail = NULL;
    45. 	}
    46. 	else
    47. 	{
    48. 		QNode* next = pq->head->next;//QNode* next相当于是QDataType的头指针的下一个位置
    49. 		free(pq->head);
    50. 		pq->head = next;//头往后走
    51. 	}
    52. 	
    53. }
    54. bool QueueEmpty(Queue* pq)
    55. {
    56. 	assert(pq);
    57. 	//return pq->head == NULL && pq->tail == NULL;
    58. 	return pq->head == NULL;//程序调试了快一个小时就是因为pq->head没加后面的== NULL
    59. }
    60. size_t QueueSize(Queue* pq)//size_t相当于Unsinged int
    61. {
    62. 	assert(pq);
    63. 	QNode* cur = pq->head;
    64. 	size_t size = 0;
    65. 	while (cur)
    66. 	{
    67. 		size++;
    68. 		cur = cur->next;
    69. 	}
    70. 	return size;
    71. }
    72. QDataType QueueFront(Queue* pq)//返回队头第一个位的值
    73. {
    74. 	assert(pq);
    75. 	assert(pq->head);
    76. 	return pq->head->data;
    77. }
    78. QDataType QueueBack(Queue* pq)//返回队尾的值
    79. {
    80. 	assert(pq);
    81. 	assert(pq->tail);
    82. 	return pq->tail->data;
    83. }

     3.2数组模拟静态队列

     

    1. #include<iostream>
    2. #include<cstring>
    3. #include<algorithm>
    4.  
    5. using namespace std;
    6.  
    7. const int N = 1e5 + 10;
    8. int q[N];
    9. int n;
    10. int hh ,tt = -1;//hh表示头，tt表示尾
    11. int main ()
    12. {
    13.     cin >> n;
    14.     while(n --)
    15.     {
    16.         string s;
    17.         cin >> s;
    18.         if(s == "push")
    19.         {
    20.             int x;
    21.             cin >> x;
    22.             q[++tt] = x;
    23.         }
    24.         else if(s == "pop")
    25.         {
    26.             hh ++;
    27.         }
    28.         else if(s == "empty")
    29.             {
    30.                 if(hh <= tt) printf("NO\n");//尾在逻辑上要比头更前面
    31.                 else printf("YES\n");
    32.             }
    33.         else cout << q[hh] << endl;
    34.     }
    35.     return 0;
    36. }

     四、leetcode-栈实现队列和用队列实现栈

     225. 用队列实现栈 - 力扣（LeetCode）

    代码：
     

    1. typedef int QDataType;
    2.  
    3. typedef struct QueueNode//保存每个节点的数据
    4. {
    5. 	QDataType data;
    6. 	struct QueueNode* next;
    7. }QNode;
    8.  
    9. typedef struct Queue
    10. {
    11. 	QNode* head;
    12. 	QNode* tail;
    13. }Queue;
    14. void QueueInit(Queue* pq);
    15. void QueueDestory(Queue* pq);
    16. void QueuePush(Queue* pq, QDataType x);//队尾插入
    17. void QueuePop(Queue* pq);
    18. bool QueueEmpty(Queue* pq);
    19. size_t QueueSize(Queue* pq);//size_t相当于Unsinged int
    20. QDataType QueueFront(Queue* pq);
    21. QDataType QueueBack(Queue* pq);
    22. void QueueInit(Queue* pq)
    23. {
    24. 	assert(pq);
    25. 	pq->head = pq->tail = NULL;
    26. }
    27. void QueueDestory(Queue* pq)
    28. {
    29. 	assert(pq);
    30. 	QNode* cur = pq->head;
    31. 	while (cur)
    32. 	{
    33. 		QNode* next = cur->next;//先记录下一个位置
    34. 		free(cur);//free掉cur指针
    35. 		cur = next;//cur赋值到下一个位置
    36. 	}
    37. 	pq->head = pq->tail = NULL;//置空
    38. }
    39. void QueuePush(Queue* pq, QDataType x)//队尾插入
    40. {
    41. 	assert(pq);
    42. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    43. 	assert(newnode);
    44. 	newnode->data = x;
    45. 	newnode->next = NULL;
    46. 	if (pq->tail == NULL)//如果链表的第一个值为空，则head = tail = NULL
    47. 	{
    48. 		assert(pq->head == NULL);
    49. 		pq->head = pq->tail = newnode;
    50. 	}
    51. 	else//尾插
    52. 	{
    53. 		pq->tail->next = newnode;
    54. 		pq->tail = newnode;
    55. 	}
    56. }
    57. void QueuePop(Queue* pq)//弹出队首
    58. {
    59. 	assert(pq);
    60. 	assert(pq->head && pq->tail);
    61. 	if (pq->head->next == NULL)//只有一个节点
    62. 	{
    63. 		free(pq->head);
    64. 		pq->head = pq->tail = NULL;
    65. 	}
    66. 	else
    67. 	{
    68. 		QNode* next = pq->head->next;//QNode* next相当于是QDataType的头指针的下一个位置
    69. 		free(pq->head);
    70. 		pq->head = next;//头往后走
    71. 	}
    72. 	
    73. }
    74. bool QueueEmpty(Queue* pq)
    75. {
    76. 	assert(pq);
    77. 	//return pq->head == NULL && pq->tail == NULL;
    78. 	return pq->head == NULL;//程序调试了快一个小时就是因为pq->head没加后面的== NULL
    79. }
    80. size_t QueueSize(Queue* pq)//size_t相当于Unsinged int
    81. {
    82. 	assert(pq);
    83. 	QNode* cur = pq->head;
    84. 	size_t size = 0;
    85. 	while (cur)
    86. 	{
    87. 		size++;
    88. 		cur = cur->next;
    89. 	}
    90. 	return size;
    91. }
    92. QDataType QueueFront(Queue* pq)//返回队头第一个位的值
    93. {
    94. 	assert(pq);
    95. 	assert(pq->head);
    96. 	return pq->head->data;
    97. }
    98. QDataType QueueBack(Queue* pq)
    99. {
    100. 	assert(pq);
    101. 	assert(pq->tail);
    102. 	return pq->tail->data;
    103. }
    104. typedef struct {
    105.     Queue q1;
    106.     Queue q2;
    107. } MyStack;
    108.  
    109.  
    110. MyStack* myStackCreate() {
    111.     MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    112.     assert(pst);
    113.  
    114.     QueueInit(&pst->q1);
    115.     QueueInit(&pst->q2);
    116.     return pst;
    117. }
    118.  
    119. void myStackPush(MyStack* obj, int x) {
    120.     assert(obj);
    121.     if(!QueueEmpty(&obj->q1))
    122.     {
    123.         QueuePush(&obj->q1, x);
    124.     }
    125.     else
    126.     {
    127.         QueuePush(&obj->q2, x);
    128.     }
    129.  
    130. }
    131.  
    132. int myStackPop(MyStack* obj) {
    133.     Queue* emptyQ = &obj->q1;//假设q1为空，q2不为空
    134.     Queue* nonEmptyQ = &obj->q2;
    135.     if(!QueueEmpty(&obj->q1))
    136.     {
    137.         emptyQ = &obj->q2;
    138.         nonEmptyQ = &obj->q1;
    139.     }
    140.     //把非空队列的前N个数据导入空队列，剩下一个删掉
    141.     //就实现了后进先出
    142.     while(QueueSize(nonEmptyQ) > 1)
    143.     {
    144.         QueuePush(emptyQ, QueueFront(nonEmptyQ));
    145.         QueuePop(nonEmptyQ);
    146.     }
    147.     int top = QueueFront(nonEmptyQ);//此时那个非空的队列只剩下一个数据
    148.     QueuePop(nonEmptyQ);
    149.     return top;
    150. }
    151.  
    152. int myStackTop(MyStack* obj) {
    153.     assert(obj);
    154.       if(!QueueEmpty(&obj->q1))//如果q1不为空
    155.     {
    156.      return QueueBack(&obj->q1);  
    157.     }
    158.     else
    159.     {
    160.      return QueueBack(&obj->q2);  
    161.     }
    162.  
    163. }
    164.  
    165. bool myStackEmpty(MyStack* obj) {
    166.     return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
    167. }
    168.  
    169. void myStackFree(MyStack* obj) {
    170.     assert(obj); 
    171.     QueueDestory(&obj->q1);
    172.     QueueDestory(&obj->q2);
    173.     free(obj);
    174. }

     

     232. 用栈实现队列 - 力扣（LeetCode）栈是后进先出

    思路：设计两个栈，一个栈专门用来入数据，一个栈专门用来出数据。

     

    1. typedef int STDataType;
    2. typedef struct Stack//动态链表
    3. {
    4. 	int *a;
    5. 	int top;//栈顶的位置
    6. 	int capacity;//容量
    7. }ST;
    8. STDataType StackTop(ST* ps);
    9. void StackInit(ST* ps);//初始化栈
    10. void StackDestory(ST* ps);
    11. void StackPop(ST* ps);
    12. void StackPush(ST* ps, STDataType x);
    13. bool StackEmpty(ST* ps);
    14. void StackInit(ST* ps)
    15. {
    16. 	assert(ps);
    17. 	ps->a = NULL;
    18. 	ps->top = 0;
    19. 	ps->capacity = 0;
    20. }
    21. void StackDestory(ST* ps)
    22. {
    23. 	assert(ps);
    24. 	free(ps->a);
    25. 	ps->a = NULL;
    26. 	ps->capacity = ps->top = 0;
    27. }
    28. void StackPush(ST* ps, STDataType x)//入数据
    29. {
    30. 	assert(ps);
    31. 	//满了就扩容
    32. 	if (ps->top == ps->capacity)
    33. 	{
    34. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    35. 		ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
    36. 		if (ps->a == NULL)
    37. 		{
    38. 			printf("realloc fail\n");
    39. 			exit(-1);
    40. 		}
    41.  
    42. 		ps->capacity = newCapacity;
    43. 	}
    44. 	ps->a[ps->top] = x;
    45. 	ps->top++;
    46. }
    47. void StackPop(ST* ps)
    48. {
    49. 	assert(ps);
    50. 	assert(ps->top > 0);
    51. 	--ps->top;
    52. }
    53. bool StackEmpty(ST* ps)
    54. {
    55. 	assert(ps);
    56. 	//两种写法
    57. 	//if (ps->top > 0)
    58. 	//{
    59. 	//	return false;
    60. 	//}
    61. 	//else
    62. 	//{
    63. 	//	return true;
    64. 	//}
    65. 	return ps->top == 0;
    66. }
    67. STDataType StackTop(ST* ps)
    68. {
    69. 	assert(ps);
    70. 	assert(ps->top > 0);
    71. 	return ps->a[ps->top - 1];//访问栈顶元素
    72. }
    73. int StackSize(ST* ps)
    74. {
    75. 	assert(ps);
    76.  
    77. 	return ps->top;
    78. }
    79. typedef struct
    80. {
    81.     ST pushST;
    82.     ST popST;
    83. } MyQueue;
    84.  
    85.  
    86. MyQueue* myQueueCreate() {
    87.     MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    88.     assert(obj);
    89.     StackInit(&obj->pushST);//&符要加，要改变结构体里面的内容
    90.     StackInit(&obj->popST);
    91.  
    92.     return obj;
    93. }
    94.  
    95. void myQueuePush(MyQueue* obj, int x) {
    96.     assert(obj);
    97.     StackPush(&obj->pushST, x);
    98. }
    99.  
    100. int myQueuePop(MyQueue* obj) {
    101.     assert(obj);
    102.     //如果popST为空， 把pushST的数据拿过来，就符合先进先出的顺序了
    103.     if(StackEmpty(&obj->popST))//如果ST Pop为空就执行
    104.     {
    105.         while(!StackEmpty(&obj->pushST))
    106.         {
    107.             StackPush(&obj->popST, StackTop(&obj->pushST));
    108.             StackPop(&obj->pushST);//把pushST里的数据删掉
    109.         }
    110.     }
    111.     int front = StackTop(&obj->popST);//记录栈顶的数据
    112.     StackPop(&obj->popST);
    113.  
    114.     return front;
    115. }
    116.  
    117. int myQueuePeek(MyQueue* obj) {
    118.     assert(obj);
    119.     //如果popST为空， 把pushST的数据拿过来，就符合先进先出的顺序了
    120.     if(StackEmpty(&obj->popST))//如果ST Pop为空就执行
    121.     {
    122.         while(!StackEmpty(&obj->pushST))
    123.         {
    124.             StackPush(&obj->popST, StackTop(&obj->pushST));
    125.             StackPop(&obj->pushST);//把pushST里的数据删掉
    126.         }
    127.     }
    128.     return StackTop(&obj->popST);
    129. }
    130.  
    131. bool myQueueEmpty(MyQueue* obj) {
    132.         assert(obj);
    133.     return StackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);
    134. }
    135.  
    136. void myQueueFree(MyQueue* obj) {
    137.     assert(obj);
    138.     StackDestory(&obj->pushST);
    139.     StackDestory(&obj->popST);
    140.  
    141.     free(obj);
    142. }
    143.

     

    总结

     本文分别从（1）栈、队列以及双端队列的概念、（2）栈的实现（动态）和模拟静态栈、（3）队列的实现（动态）和模拟静态队列、（4）leetcode-栈实现队列和用队列实现栈四个方面对栈和队列这两个数据结构进行了分析，希望大家读后能够有所收获，也希望大家多多支持。

  • 相关阅读:
    Transformer，浅析归纳偏置对模型缩放的影响
    vite vue项目 运行时 \esbuild\esbuild.exe 缺失 错误码 errno: -4058, code: ‘ENOENT‘,
    【C++】模板-非类型模板参数
    阿里企业邮箱域名解析MX记录表
    智领未来，安全无忧：智能网联汽车监控大屏的守护之旅
    14.MongoDB导出备份
    如何在单链表中的任意一个位置插入一个结点
    【MySql】Mysql之备份与恢复
    静态路由——实现两个不相连的网段通信实验
    编译
  • 原文地址：https://blog.csdn.net/qq_62662919/article/details/124898215