• 数据结构之栈和队列

    要努力，但不要急。繁花锦簇，硕果累累都需要过程！

     1.栈

    1.栈的概念：

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

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

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

    2.栈的实现：

    栈的实现一般使用数据或者是链表实现，但一般情况下使用顺序表，因为数据在尾插的时候代价比较小。

    1.创建结构体：

    缺点：指定内存大小，无法改变，因此一般使用动态增长的栈：

     

     2.初始化栈：

    void StackInit(ST* ps);

     3.入栈：

    void StackPush(ST* ps, STDataType x);

    4.出栈：

     void StackPop(ST* ps);

     5.检查栈是否为空：

    bool StackEmpty(ST* ps);

     6.获取栈中有效元素的个数：

    int StackSize(ST* ps);

    7.获取栈顶的元素：

    STDataType StackTop(ST* ps);

     8.销毁栈：

     void StackDestroy(ST* ps);

     

    2.队列

    1.概念：

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

     

    2.队列的实现：

    队列的实现可以使用数组和链表，但是队列从头出数据，数组需要每次往前移动，时间复杂度为O(N)，所以一般采用链表来实现队列

    1.创建链式结构：表示队列

    2.队列的结构：

     3.初始化队列：

    void QueueInit(Queue* pq);

    4.队列插入数据： 

    void QueuePush(Queue* pq, QDataType x);

    5.队列删除数据：

     void QueuePop(Queue* pq);

    6.判断队列是否为空：

     bool QueueEmpty(Queue* pq);

    7.获取队列头部的元素：

     QDataType QueueFront(Queue* pq);

    8.获取队列尾部的元素：

     QDataType QueueBack(Queue* pq);

    9.获取队列有效元素个数：

     int QueueSize(Queue* pq);

    10.销毁队列：

     void QueueDestroy(Queue* pq);

     

    3.栈和队列的面试题：

    题目1：

    括号匹配问题：

    oj链接

    解法思路：将左括号放入栈中，然后取出来一一和外边的比较

    不匹配的三种情况：

    1.栈中的元素为空

    2.栈中的元素不为空

    3.类型不匹配

    1. typedef char STDataType;
    2. typedef struct Stack
    3. {
    4. 	STDataType* arr;
    5. 	int top;
    6. 	int capacity;//记录数组的容量
    7. }ST;
    8. //初始化栈：
    9. void StackInit(ST* ps);
    10. //入栈：
    11. void StackPush(ST* ps, STDataType x);
    12. //出栈：
    13. void StackPop(ST* ps);
    14. //获取栈顶的元素：
    15. STDataType StackTop(ST* ps);
    16. //检查栈是否为空：
    17. bool StackEmpty(ST* ps);
    18. //获取栈中有效元素的个数：
    19. int StackSize(ST* ps);
    20. //销毁栈：
    21. void StackDestroy(ST* ps);
    22. void StackInit(ST* ps)
    23. {
    24. 	assert(ps);
    25. 	ps->arr = NULL;
    26. 	ps->top = ps->capacity = 0;
    27. }
    28. void StackPush(ST* ps, STDataType x)
    29. {
    30. 	assert(ps);
    31. 	//检查容量：
    32. 	if (ps->top == ps->capacity)
    33. 	{
    34. 		//增容：
    35. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    36. 		STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * newCapacity);
    37. 		if (tmp == NULL)
    38. 		{
    39. 			perror("realloc fail");
    40. 			exit(-1);
    41. 		}
    42. 		ps->arr = tmp;
    43. 		ps->capacity = newCapacity;
    44. 	}
    45. 	ps->arr[ps->top] = x;
    46. 	ps->top++;
    47. }
    48. bool StackEmpty(ST* ps)
    49. {
    50. 	assert(ps);
    51. 	return ps->top == 0;
    52. }
    53. void StackPop(ST* ps)
    54. {
    55. 	assert(ps);
    56. 	assert(!StackEmpty(ps));
    57. 	ps->top--;
    58. }
    59. STDataType StackTop(ST* ps)
    60. {
    61. 	assert(ps);
    62. 	assert(!StackEmpty(ps));
    63. 	return ps->arr[ps->top - 1];
    64. }
    65. int StackSize(ST* ps)
    66. {
    67. 	assert(ps);
    68. 	return ps->top;
    69. }
    70. void StackDestroy(ST* ps)
    71. {
    72. 	assert(ps);
    73. 	free(ps->arr);
    74. 	ps->arr = NULL;
    75. 	ps->capacity = ps->top = 0;
    76. }
    77. bool isValid(char * s){
    78.     ST st;
    79.     StackInit(&st);
    80.     while(*s)
    81.     {
    82.         //将左括号放入栈中：
    83.         if(*s == '(' || *s == '{' || *s == '[')
    84.         {
    85.             StackPush(&st,*s);
    86.         }
    87.         else//取出栈中的括号和外边的比较：
    88.         {
    89.             //取到右括号，栈为空，说明左括号数量不匹配
    90.             if(StackEmpty(&st))
    91.             {
    92.                 StackDestroy(&st);
    93.                 return false;
    94.             }
    95.  
    96.             char top = StackTop(&st);
    97.             StackPop(&st);
    98.             if((*s == '}' && top != '{')
    99.             ||(*s == ']' && top != '[')
    100.             ||(*s == ')' && top != '('))
    101.             {
    102.                 StackDestroy(&st);
    103.                 return false;
    104.             }
    105.         }
    106.         s++;
    107.     }
    108.     //栈不为空说明右括号数量不匹配：
    109.     bool flag = StackEmpty(&st);
    110.     StackDestroy(&st);
    111.     return flag;
    112. }

    题目二：

    用两个队列实现一个栈：oj链接

    解法思路：保持一个队列为空，然后进行转换

    1. typedef int QDataType;
    2. typedef struct QListNode
    3. {
    4. 	struct QListNode* next;
    5. 	QDataType data;
    6. }QNode;
    7.  
    8. typedef struct Queue
    9. {
    10. 	QNode* head;//头指针
    11. 	QNode* tail;//尾指针
    12. 	int size;//记录队列元素个数
    13. }Queue;
    14.  
    15. //初始化队列：
    16. void QueueInit(Queue* pq);
    17. //销毁队列：
    18. void QueueDestroy(Queue* pq);
    19. //队列插入数据：
    20. void QueuePush(Queue* pq, QDataType x);
    21. //队列删除数据：
    22. void QueuePop(Queue* pq);
    23. //判断队列是否为空：
    24. bool QueueEmpty(Queue* pq);
    25. //获取队列头部的元素：
    26. QDataType QueueFront(Queue* pq);
    27. //获取队列尾部的元素：
    28. QDataType QueueBack(Queue* pq);
    29. //获取队列有效元素个数：
    30. int QueueSize(Queue* pq);
    31. void QueueInit(Queue* pq)
    32. {
    33. 	assert(pq);
    34. 	pq->head = pq->tail = NULL;
    35. 	pq->size = 0;
    36. }
    37. void QueueDestroy(Queue* pq)
    38. {
    39. 	assert(pq);
    40. 	QNode* cur = pq->head;
    41. 	while (cur)
    42. 	{
    43. 		QNode* del = cur;
    44. 		cur = cur->next;
    45. 		free(del);
    46. 		del = NULL;
    47. 	}
    48. 	pq->head = NULL;
    49. 	pq->tail = NULL;
    50. }
    51. void QueuePush(Queue* pq, QDataType x)
    52. {
    53. 	assert(pq);
    54. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    55. 	if (newnode == NULL)
    56. 	{
    57. 		perror("malloc fail:");
    58. 		exit(-1);
    59. 	}
    60. 	else
    61. 	{
    62. 		newnode->next = NULL;
    63. 		newnode->data = x;
    64. 	}
    65. 	if (pq->tail == NULL)
    66. 	{
    67. 		pq->head = pq->tail = newnode;
    68. 	}
    69. 	else
    70. 	{
    71. 		pq->tail->next = newnode;
    72. 		pq->tail = newnode;
    73. 	}
    74. 	pq->size++;
    75. }
    76. bool QueueEmpty(Queue* pq)
    77. {
    78. 	assert(pq);
    79. 	return pq->head == NULL && pq->tail == NULL;
    80. }
    81. void QueuePop(Queue* pq)
    82. {
    83. 	assert(pq);
    84. 	assert(!QueueEmpty(pq));
    85. 	if (pq->head->next == NULL)
    86. 	{
    87. 		free(pq->head);
    88. 		pq->head = pq->tail = NULL;
    89. 	}
    90. 	else
    91. 	{
    92. 		Queue* del = pq->head;
    93. 		pq->head = pq->head->next;
    94. 		free(del);
    95. 		del = NULL;
    96. 	}
    97. 	pq->size--;
    98. }
    99. QDataType QueueFront(Queue* pq)
    100. {
    101. 	assert(pq);
    102. 	assert(!QueueEmpty(pq));
    103. 	return pq->head->data;
    104. }
    105. QDataType QueueBack(Queue* pq)
    106. {
    107. 	assert(pq);
    108. 	assert(!QueueEmpty(pq));
    109. 	return pq->tail->data;
    110. }
    111. int QueueSize(Queue* pq)
    112. {
    113. 	return pq->size;
    114. }
    115. typedef struct {
    116.     Queue q1;
    117.     Queue q2;
    118. } MyStack;
    119.  
    120.  
    121. MyStack* myStackCreate() {
    122.     MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    123.     QueueInit(&obj->q1);
    124.     QueueInit(&obj->q2);
    125.     return obj;
    126. }
    127.  
    128. void myStackPush(MyStack* obj, int x) {
    129.     if(!QueueEmpty(&obj->q1))
    130.         QueuePush(&obj->q1,x);
    131.     else
    132.         QueuePush(&obj->q2,x);
    133. }
    134.  
    135. int myStackPop(MyStack* obj) {
    136.     Queue* empty = &obj->q1;
    137.     Queue* noEmpty = &obj->q2;
    138.     if(!QueueEmpty(&obj->q1))
    139.     {
    140.         empty = &obj->q2;
    141.         noEmpty = &obj->q1;
    142.     }
    143.     while(QueueSize(noEmpty) > 1)
    144.     {
    145.         QueuePush(empty,QueueFront(noEmpty));
    146.         QueuePop(noEmpty);
    147.     }
    148.     int top = QueueFront(noEmpty);
    149.     QueuePop(noEmpty);
    150.     return top;
    151. }
    152.  
    153. int myStackTop(MyStack* obj) {
    154.     if(!QueueEmpty(&obj->q1))
    155.         return QueueBack(&obj->q1);
    156.     else
    157.         return QueueBack(&obj->q2);
    158. }
    159.  
    160. bool myStackEmpty(MyStack* obj) {
    161.     return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
    162. }
    163.  
    164. void myStackFree(MyStack* obj) {
    165.     QueueDestroy(&obj->q1);
    166.     QueueDestroy(&obj->q2);
    167.     free(obj);
    168. }

    题目三：

    用栈实现队列：oj链接

    解法思路：一个栈中专门用来存放数据，一个栈中专门用来删除数据

     

    1. typedef int STDataType;
    2. typedef struct Stack
    3. {
    4. 	STDataType* arr;
    5. 	int top;
    6. 	int capacity;//记录数组的容量
    7. }ST;
    8.  
    9.  
    10. //初始化栈：
    11. void StackInit(ST* ps);
    12. //入栈：
    13. void StackPush(ST* ps, STDataType x);
    14. //出栈：
    15. void StackPop(ST* ps);
    16. //获取栈顶的元素：
    17. STDataType StackTop(ST* ps);
    18. //检查栈是否为空：
    19. bool StackEmpty(ST* ps);
    20. //获取栈中有效元素的个数：
    21. int StackSize(ST* ps);
    22. //销毁栈：
    23. void StackDestroy(ST* ps);
    24. void StackInit(ST* ps)
    25. {
    26. 	assert(ps);
    27. 	ps->arr = NULL;
    28. 	ps->top = ps->capacity = 0;
    29. }
    30. void StackPush(ST* ps, STDataType x)
    31. {
    32. 	assert(ps);
    33. 	//检查容量：
    34. 	if (ps->top == ps->capacity)
    35. 	{
    36. 		//增容：
    37. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    38. 		STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * newCapacity);
    39. 		if (tmp == NULL)
    40. 		{
    41. 			perror("realloc fail");
    42. 			exit(-1);
    43. 		}
    44. 		ps->arr = tmp;
    45. 		ps->capacity = newCapacity;
    46. 	}
    47. 	ps->arr[ps->top] = x;
    48. 	ps->top++;
    49. }
    50. bool StackEmpty(ST* ps)
    51. {
    52. 	assert(ps);
    53. 	return ps->top == 0;
    54. }
    55. void StackPop(ST* ps)
    56. {
    57. 	assert(ps);
    58. 	assert(!StackEmpty(ps));
    59. 	ps->top--;
    60. }
    61. STDataType StackTop(ST* ps)
    62. {
    63. 	assert(ps);
    64. 	assert(!StackEmpty(ps));
    65. 	return ps->arr[ps->top - 1];
    66. }
    67. int StackSize(ST* ps)
    68. {
    69. 	assert(ps);
    70. 	return ps->top;
    71. }
    72. void StackDestroy(ST* ps)
    73. {
    74. 	assert(ps);
    75. 	free(ps->arr);
    76. 	ps->arr = NULL;
    77. 	ps->capacity = ps->top = 0;
    78. }
    79. typedef struct {
    80.     ST pushST;
    81.     ST popST;
    82. } MyQueue;
    83.  
    84.  
    85. MyQueue* myQueueCreate() {
    86.     MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    87.     StackInit(&obj->pushST);
    88.     StackInit(&obj->popST);
    89.  
    90.     return obj;
    91. }
    92.  
    93. void myQueuePush(MyQueue* obj, int x) {
    94.     StackPush(&obj->pushST,x);
    95. }
    96. void pushSTTopopST(MyQueue* obj)
    97. {
    98.     if(StackEmpty(&obj->popST))
    99.     {
    100.         while(!StackEmpty(&obj->pushST))
    101.         {
    102.             StackPush(&obj->popST,StackTop(&obj->pushST));
    103.             StackPop(&obj->pushST);
    104.         }
    105.     }
    106. }
    107. int myQueuePop(MyQueue* obj) {
    108.     pushSTTopopST(obj);
    109.     int front = StackTop(&obj->popST);
    110.     StackPop(&obj->popST);
    111.     return front;
    112. }
    113.  
    114. int myQueuePeek(MyQueue* obj) {
    115.     pushSTTopopST(obj);
    116.     return StackTop(&obj->popST);
    117. }
    118.  
    119. bool myQueueEmpty(MyQueue* obj) {
    120.     return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
    121. }
    122.  
    123. void myQueueFree(MyQueue* obj) {
    124.     StackDestroy(&obj->pushST);
    125.     StackDestroy(&obj->popST);
    126.     free(obj);
    127. }

    题目四：

    设计循环队列：oj链接

    解法思路：用数组实现

    循环队列的逻辑结构：

    定义两个下标依次插入数据，为了区分数据空和满的情况，需要多开辟一个空间，当back的下一个位置等于front的时候说明队列数据满了：

    1. typedef struct {
    2.     int* a;
    3.     int front;//标记头
    4.     int back;//标记尾
    5.     int N;//记录空间大小
    6. } MyCircularQueue;
    7.  
    8.  
    9. MyCircularQueue* myCircularQueueCreate(int k) {
    10.     MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    11.     obj->a = (int*)malloc(sizeof(int)*(k+1));//多开辟一个空间
    12.     obj->front = 0;
    13.     obj->back = 0;
    14.     obj->N = k + 1;
    15.     return obj;
    16. }
    17. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    18.     return obj->front == obj->back;
    19. }
    20.  
    21. bool myCircularQueueIsFull(MyCircularQueue* obj) {
    22.     //%obj->N 当back在最后的时候回到起始位置
    23.     return (obj->back + 1) % obj->N == obj->front;
    24. }
    25. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    26.     if(myCircularQueueIsFull(obj))
    27.         return false;
    28.     obj->a[obj->back] = value;
    29.     obj->back++;
    30.     //当到队尾的时候，返回到起始位置
    31.     obj->back %= obj->N;
    32.     return true;
    33. }
    34. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    35.     if(myCircularQueueIsEmpty(obj))
    36.         return false;
    37.     obj->front++;
    38.     // //当到队尾的时候，返回到起始位置
    39.     obj->front %= obj->N;
    40.     return true;
    41. }
    42. int myCircularQueueFront(MyCircularQueue* obj) {
    43.     if(myCircularQueueIsEmpty(obj))
    44.         return -1;
    45.     return obj->a[obj->front];
    46. }
    47. int myCircularQueueRear(MyCircularQueue* obj) {
    48.     if(myCircularQueueIsEmpty(obj))
    49.         return -1;
    50.     else if(obj->back == 0)
    51.         return obj->a[obj->N-1];
    52.     else
    53.         return obj->a[obj->back-1];
    54. }
    55. void myCircularQueueFree(MyCircularQueue* obj) {
    56.     free(obj->a);
    57.     obj->a = NULL;
    58.     free(obj);
    59.     obj = NULL;
    60. }

    总结：

    以上就是关于栈和队列的知识点和相关面试题，本质上栈和队列也是在内存中管理数据，是通过数组和链表的结构来实现的。

  • 相关阅读:
    利用PHP的特性做免杀Webshell
    Linux内核驱动开发的需要掌握的知识点
    〔003〕虚幻 UE5 基础教程和蓝图入门
    java学习（常用类)
    如何使用Docker安装最新版本的Redis并设置远程访问（含免费可视化工具）
    Nginx下PHP连接到GBase 8s数据库 - PDO_GBASEDBT方式
    【牛客刷题】每日一练—ArrayList的实例强化
    进程调度算法详解
    头哥实践平台之Linux 文件/目录管理
    bind搭建内网DNS服务器架构(主从、子域授权、DNS转发器)
  • 原文地址：https://blog.csdn.net/qq_65307907/article/details/126166669