• 算法基础：栈和队列

    栈和队列

    目录

    概念

    常见操作

    进制转换器(栈的方式)

    栈实现括号匹配

    算法考题

    两个栈实现一个队列

    思路

    代码

    两个队列实现栈

    思路

    代码

    最小栈

    题目描述

    思路

    代码实现

    每日温度（Medium）

    题目描述

    代码实现

    最大的矩形

    题目描述

    思路：

    代码实现

    概念

    栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集（也具有顺序结构和链式结构），它们是操作受限的线性表，因此，可称为限定性的数据结构。

    栈是一种只能从表的一端存取数据且遵循 "先进后出" 原则的线性存储结构。

    队列中数据的进出要遵循 "先进先出" 的原则

    常见操作

    进制转换器(栈的方式)

    例如，用户提供了一个十进制数：10，要求将此数据以二进制形式转换，则通过进制转换器转换的最终结果应该：1010。

    1. #include 
    2. #include 
    3. #include 
    4. int top=-1;//top变量时刻表示栈顶元素所在位置
    5. void push(char * a,char elem){
    6.     a[++top]=elem;
    7. }
    8. void pop(char * a){
    9.     if (top==-1) {
    10.         return ;
    11.     }
    12.     //输出时要按照正确的格式显示给用户
    13.     if (a[top]>=10) {
    14.         printf("%c",a[top]+55); //因为是10到35所以,要加55变成A-Z对应的ASCII码值,65-90
    15.     }else{
    16.         printf("%d",a[top]);
    17.     }
    18.     top--;
    19. }
    20. //将各进制数转换成十进制数
    21. int scaleFun(char * data,int system){
    22.     int k=(int)strlen(data)-1;
    23.     int system_10_data=0;
    24.     int i;
    25.     for (i=k; i>=0; i--) {
    26.         int temp;
    27.         if (data[i]>=48 && data[i]<=57) { //0-9
    28.             temp=data[i]-48;
    29.         }else{
    30.             temp=data[i]-55;  //A-Z的ASCII码值65-90,所以减55变成10-35
    31.         }
    32.         system_10_data+=temp*pow(system, k-i); // double pow(double x, double y) 返回 x 的 y 次幂，即 xy。
    33.     }
    34.     return system_10_data;
    35. }
    36. int main() {
    37.     char data[100];
    38.     int system;
    39.     int newSystem;
    40.     int system_10_data;
    41.     printf("进制转换器，请输入原数据的进制（2-36）:");
    42.     scanf("%d",&system);
    43.     getchar();
    44.     printf("请输入要转换的数据：");
    45.     scanf("%s",data);
    46.     getchar();
    47.     system_10_data=scaleFun(data, system);
    48.     printf("请输入转换后的数据的进制：");
    49.     scanf("%d",&newSystem);
    50.     getchar();
    51.     while (system_10_data/newSystem) { //十进制转其它进制,除其它进制,倒取余,用商继续除.
    52.         push(data,system_10_data%newSystem );//倒取余,所以用栈
    53.         system_10_data/=newSystem;
    54.     }
    55.     push(data,system_10_data%newSystem);
    56.     printf("转换后的结果为：\n");
    57.     while (top!=-1) {
    58.         pop(data);
    59.     }
    60. }

    栈实现括号匹配

    1. //这次实现中涉及到的括号只包括小中大三种
    2. #include
    3. #include
    4. #include
    5.  
    6. #define MaxSize 100
    7. typedef struct{
    8. 	char data[MaxSize];
    9. 	int top;
    10. }SqStack;
    11.  
    12. //顺序栈的初始化
    13. bool InitStack(SqStack &S)
    14. {
    15.     for(int i=0;i'\0';
    16.     S.top=-1;
    17.     return true;
    18. }
    19.  
    20. //判断栈空：
    21. bool StackEmpty(SqStack S)
    22. {
    23. 	if(S.top==-1)return true;
    24. 	else return false;
    25. } 
    26.  
    27. //顺序栈入栈操作：
    28. bool Push(SqStack &S,char x)
    29. {
    30. 	if(S.top==(MaxSize-1))return false;
    31. 	S.data[++S.top]=x;
    32. 	return true;
    33. }
    34.  
    35. //顺序栈出栈操作：
    36. bool Pop(SqStack &S,char &x) 
    37. {
    38. 	if(S.top==-1)return false;
    39. 	x=S.data[S.top--];
    40. 	return true;
    41. }
    42.  
    43. //基于顺序栈的括号匹配算法： 
    44. bool bracketCheck(char str[],int length)
    45. {
    46. 	SqStack S;
    47. 	
    48. 	InitStack(S);
    49. 	for(int i=0;i
    50. 	{
    51. 		if(str[i]=='('||str[i]=='{'||str[i]=='[')
    52. 		{
    53. 			Push(S,str[i]);
    54. 		}
    55. 		else{
    56. 			if((str[i]==')'||str[i]=='}'||str[i]==']')&&StackEmpty(S))return false;
    57. 			
    58. 			char topElem;
    59. 			Pop(S,topElem);
    60. 			if(str[i]==')'&&topElem!='(')return false;
    61. 			if(str[i]=='}'&&topElem!='{')return false;
    62. 			if(str[i]==']'&&topElem!='[')return false;
    63. 		}
    64. 	}
    65. 	return StackEmpty(S);
    66. }
    67.  
    68. int main()
    69. {
    70. 	int j=0;char x;
    71. 	char g[MaxSize];
    72. 	memset(g,'\0',MaxSize);
    73. 	
    74. 	printf("输入你的括号组合:\n");
    75. 	scanf("%c",&x);
    76. 	while(x!='!')
    77. 	{
    78. 		g[j]=x;
    79. 		j++;
    80. 		scanf(" %c",&x);
    81. 	}
    82. 	
    83. 	printf("括号组合是否规范:  ");
    84. 	if(bracketCheck(g,j))printf("是\n");
    85. 	else printf("否\n");
    86. 	
    87. 	return 0; 
    88. }

    算法考题

    两个栈实现一个队列

    思路

    （1） 使用两个栈A,B，其中假定A负责push操作，B负责pop操作。使用一个变量back_elem来存储最后添加的元素。

    （2） 实现队列的push操作， 每次进行添加操作，都会相应得对栈A进行添加元素。并对back_elem赋值

    （3） 实现队列的pop操作，每次进行删除操作，因为栈B负责pop操作，

    首先判断栈B是否为空？

    a.如果B为空，则判断A是否为空？

    如果A也为空，则输出错误信息，此时队列为空。

    如果A不为空，则将栈A中的所有数据存储到B中。执B.push(A.top()), A.pop(). 然后在对栈B 执行B.pop()操作，将队列的头元素删除

    b.如果B不为空， 则直接对B执行 B.pop()操作。

    （4）实现队列的front()操作，方法如pop操作相同，只是在最后一步使用B.top()返回值。

    （5）实现队列的back()操作，因为我们变量back_elem保存着最后一个输入的数据，故直接将其返回。

    （6）实现队列的size()操作，和empty()操作，就是对A,B分别执行操作。

    代码

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. template<typename T>
    7. class Queue {
    8. private:
    9. 	stackstackA;	//栈A
    10. 	stackstackB;	//栈B
    11. 	T back_elem;	//用于存储新添加的元素
    12. public:
    13. 	void push(T elem);	//将新元素压入队列（压入栈A）中
    14. 	void pop();			//将元素弹出队列（从栈B中弹出）
    15. 	T front();			//队首元素
    16. 	T back();			//队尾元素
    17. 	int size()const;    //队列长度
    18. 	bool empty()const;  //队列是否为空
    19. };
    20.  
    21. /*
    22. 入队操作
    23. 实现队列的push操作， 每次进行添加操作，都会相应得对栈A进行添加元素。并对back_elem赋值
    24. */
    25. template<typename T>
    26. void Queue::push(T elem)
    27. {
    28. 	stackA.push(elem);//将元素压入队列
    29. 	back_elem = elem;	//存储新添加的元素
    30. }
    31.  
    32. /*
    33. 出队操作
    34. 实现队列的pop操作，每次进行删除操作，因为栈B负责pop操作。
    35. 首先判断栈B是否为空？
    36. a.如果栈B为空，则判断A是否为空？
    37. 		如果A也为空，则输出错误信息，此时队列为空。
    38. 		如果A不为空，则将栈A中的所有数据存储到B中。执B.push(A.top()), A.pop().然后在对栈B
    39. 			执行，B.pop()操作，将队列的头元素删除
    40. b.如果栈B不为空， 则直接对栈B执行 B.pop()操作。
    41. */
    42. template<typename T>
    43. void Queue::pop()
    44. {
    45. 	//判断栈B是否为空？
    46. 	if (!stackB.empty())	//栈B不为空， 则直接对栈B执行 B.pop()操作。
    47. 	{
    48. 		stackB.pop();
    49. 	}
    50. 	else if (!stackA.empty())	//栈B为空，则判断栈A是否为空？栈A不为空,则将栈A中的所有数据
    51.    //存储到B中。执B.push(A.top()), A.pop().然后在对栈B执行，B.pop()操作，将队列的头元素删除
    52. 	{
    53. 		stackB.push(stackA.top());
    54. 		stackA.pop();
    55. 	}
    56. 	else
    57. 	{
    58. 		std::cout << "error pop(),empty queue!" << std::endl;
    59. 	}
    60. }
    61.  
    62. /*
    63. 队首元素
    64. */
    65. template<typename T>
    66. T Queue::front()
    67. {
    68. 	if (!stackB.empty())
    69. 	{
    70. 		return stackB.top();
    71. 	}
    72. 	else if (!stackA.empty())
    73. 	{
    74. 		while (!stackA.empty())
    75. 		{
    76. 			stackB.push(stackA.top());
    77. 			stackA.pop();
    78. 		}
    79. 		return stackB.top();
    80. 	}
    81. 	else
    82. 	{
    83. 		std::cout << "error front(),empty queue!" << std::endl;
    84. 	}
    85. }
    86.  
    87. /*
    88. 队尾元素
    89. */
    90. template<typename T>
    91. T Queue::back()
    92. {
    93. 	if (!empty())
    94. 	{
    95. 		return back_elem;
    96. 	}
    97. 	else
    98. 	{
    99. 		std::cout << "error back(),empty queue!" << std::endl;
    100. 	}
    101. }
    102.  
    103. /*
    104. 队列长度
    105. */
    106. template<typename T>
    107. int Queue::size() const
    108. {
    109. 	return stackA.size() + stackB.size();
    110. }
    111.  
    112. /*
    113. 队列是否为空
    114. */
    115. template<typename T>
    116. bool Queue::empty() const {
    117. 	return stackA.empty() && stackB.empty();
    118. }
    119.  
    120. int main()
    121. {
    122. 	Queue<int>queue;
    123. 	//入队操作
    124. 	queue.push(1);
    125. 	queue.push(2);
    126. 	queue.push(3);
    127. 	queue.push(4);
    128. 	cout << "Four times push() After:" << endl;
    129. 	//队首元素
    130. 	cout << "The queue front:" << queue.front() << endl;
    131. 	//队尾元素
    132. 	cout << "The queue back:" << queue.back() << endl;
    133. 	//队列size
    134. 	cout << "The queue size:" << queue.size() << endl;
    135. 	//出队操作
    136. 	queue.pop();
    137. 	queue.pop();
    138. 	queue.pop();
    139. 	queue.pop();
    140. 	cout << "----------------------------" << endl;
    141. 	cout << "Four times pop() After:" << endl;
    142. 	//队首元素
    143. 	cout << "The queue front:" << queue.front() << endl;
    144. 	//队尾元素
    145. 	cout << "The queue back:" << queue.back() << endl;
    146. 	//队列size
    147. 	cout << "The queue size:" << queue.size() << endl;
    148.  
    149. 	//system("pause");
    150. 	return 0;
    151. }

    两个队列实现栈

    思路

    入栈和出栈，都在 queue1 中完成，而 queue2 作为中转空间。

    • 入栈：直接入 queue1 即可。
    • 出栈：把 queue1 中除最后一个元素外的所有元素都移动到 queue2 中，再将 queue1 转化为queue2，queue2转化为queue1

    代码

    1. #include
    2. #include
    3. using namespace std;
    4.  
    5. template<typename T>
    6. class CStack
    7. {
    8. public:
    9. 	CStack(){}
    10. 	~CStack(){}
    11. 	void push(const T &val)
    12. 	{
    13. 		if(queue1.empty() && queue2.empty())  //两个队列为空，则插入queue1
    14. 		{
    15. 			queue1.push(val);     
    16. 		}
    17.  
    18. 		if(queue1.empty())         //如果queue1为空，则插入queue2
    19. 		{
    20. 			queue2.push(val);
    21. 		}
    22. 		else
    23. 		{
    24. 			queue1.push(val);      //如果queue2为空，则插入queue1
    25. 		}
    26. 	}
    27. 	T pop()
    28. 	{
    29. 		if(queue1.empty())        //如果queue1为空
    30. 		{
    31. 			if(queue2.empty())    //如果queue2为空，则说明栈为空
    32. 			{
    33. 				throw new exception("stack is empty");
    34. 			}
    35. 			else
    36. 			{
    37. 				if(queue2.size() == 1)   //如过queue2只有一个元素，直接退出
    38. 				{
    39. 					T result = queue2.front();
    40. 					queue2.pop();
    41. 					return result;
    42. 				}
    43. 				else
    44. 				{
    45. 					while(queue2.size() != 1)  //依次退出队中元素，直到队列中只有队尾元素
    46. 					{
    47. 						queue1.push(queue2.front());
    48. 						queue2.pop();
    49. 					}
    50. 					T result = queue2.front();  //将队尾元素退出
    51. 					queue2.pop();
    52. 					return result;
    53. 				}
    54. 			}
    55. 		}
    56. 		else          //如果queue1不为空
    57. 		{
    58. 			if(queue1.size() == 1)     //如果queue1中只有队尾元素时，直接退出
    59. 			{
    60. 				T result = queue1.front();
    61. 				queue1.pop();
    62. 				return result;
    63. 			}
    64. 			else
    65. 			{
    66. 				while(queue1.size() != 1)  //依次退出queue1中的元素到queue2，直到queue1只有队尾元素
    67. 				{
    68. 					queue2.push(queue1.front());
    69. 					queue1.pop();
    70. 				}
    71. 				T result = queue1.front(); //将队尾元素弹出
    72. 				queue1.pop();
    73. 				return result;
    74. 			}
    75. 		}
    76. 		
    77. 	}
    78. private:
    79. 	queue queue1;
    80. 	queue queue2;
    81. };
    82.  
    83. int main()
    84. {
    85. 	CStack<char> stack;
    86. 	
    87. 	//测试用例1:
    88. 	stack.push('a');           //元素a入栈
    89. 	stack.push('b');           //元素b入栈
    90. 	stack.push('c');           //元素c入栈
    91. 	cout << "第1次出栈元素是：" << stack.pop() << endl;
    92. 	cout << "第2次出栈元素是：" << stack.pop() << endl;
    93. 	stack.push('d');           //元素d入栈
    94. 	cout << "第3次出栈元素是：" << stack.pop() << endl;
    95. 	cout << "第4次出栈元素是："<< stack.pop() << endl;
    96. 	return 0;
    97. }

    最小栈

    题目描述

    设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

    push(x) – 将元素 x 推入栈中。
    pop() – 删除栈顶的元素。
    top()– 获取栈顶元素。
    getMin() – 检索栈中的最小元素。

    思路

    通过双栈来实现最小栈，因为这样可以在常数时间复杂度中得到栈内元素最小值。这是典型的空间换时间的操作。

    入栈时要对两个栈同时进行操作，normal栈正常压栈，对于min栈进行参数条件判定：如果此时

    最小栈为空 （说明是第一次压栈）

    这个值小于此时最小栈的栈顶元素 （说明是压入了一个小于已入栈全部元素的值）

    两条件是任满足其一即可进行最小栈的压栈，否则不满足条件执行最小栈的栈顶元素压栈，说明压入的这个值不是最小值，将目前最小值再次压入最小栈。

    代码实现

    1. #include 
    2. #include 
    3.  
    4. class MinStack {
    5. public:
    6.     MinStack() {
    7.     }
    8.     void push(int x) {
    9.     	_data.push(x);
    10.     	if (_min.empty()){
    11. 	    	_min.push(x);
    12. 	    }
    13. 	    else{
    14. 	    	if (x > _min.top()){
    15. 	    		x = _min.top();
    16. 	    	}
    17.     		_min.push(x);
    18.     	}
    19.     }
    20.     void pop() {
    21.     	_data.pop();
    22.     	_min.pop();
    23.     }
    24.     int top() {
    25.         return _data.top();
    26.     }
    27.     int getMin() {
    28.         return _min.top();
    29.     }
    30. private:
    31. 	std::stack<int> _data;
    32. 	std::stack<int> _min;
    33. };

    每日温度（Medium）

    题目描述

    根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。

    例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

    提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

    题目解析

    • 维护一个递减栈，若当前元素大于栈顶元素，则说明温度升高，栈顶元素出栈，两者下标的差值即为栈顶元素所在下标的所求天数。
    • 直到当前元素小于栈顶元素，当前元素入栈，继续判断。
    • 时间复杂度：O(N)。
    • 空间复杂度：O(N)。

    代码实现

    1. int* dailyTemperatures(int* T, int TSize, int* returnSize) {
    2.     int* result = (int*)malloc(sizeof(int)*TSize);
    3.     // 用栈记录T的下标。
    4.     int* stack_index = malloc(sizeof(int)*TSize);
    5.     *returnSize = TSize;
    6.     result[TSize-1] = 0;
    7.     // 栈顶指针。
    8.     int top = 0;
    9.     
    10.     for (int i = 0; i < TSize; i++)
    11.         result[i] = 0;
    12.     for (int i = 0; i < TSize; i++) {
    13.         // 若当前元素大于栈顶元素，栈顶元素出栈。即温度升高了，所求天数为两者下标的差值。
    14.         while (top > 0 && T[i] > T[stack_index[top-1]]) {
    15.             result[stack_index[top-1]] = i-stack_index[top-1];
    16.             top--;
    17.         }
    18.         
    19.         // 当前元素入栈。
    20.         stack_index[top] = i;
    21.         top++;
    22.     }
    23.     
    24.     return result;
    25. }

    最大的矩形

    题目描述

    在横轴上放了n个相邻的矩形，每个矩形的宽度是1，而第i（1 ≤ i ≤ n）个矩形的高度是hi。这n个矩形构成了一个直方图。例如，下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。

    请找出能放在给定直方图里面积最大的矩形，它的边要与坐标轴平行。对于上面给出的例子，最大矩形如下图所示的阴影部分，面积是10。

    思路：

    我们可以维持一个单调递增的栈，为了便于计算矩形宽度，我们在栈里存放单个矩形的位置。
    我们从左到右遍历高度数组，对于每个矩形的高度p，如果p大于等于当前栈顶储存位置的高度q，我们将p的位置也压入栈中；

    如果p小于q，我们将栈中元素弹出，纪录高度，并记录当前遍历到的矩形p与新栈顶位置之差(实际上还需要减1)，作为宽度，并更新结果。

    代码实现

    1. int largestRectangleArea(vector<int>& heights) {
    2. 	heights.push_back(0);		//插入空矩形，弹出栈中剩余矩形
    3. 	int len = heights.size(), area = 0, pre_index, height, width;
    4. 	stack<int> indices;
    5. 	for (int i = 0; i < len; i++) {
    6. 		while (!indices.empty() && heights[indices.top()] > heights[i]) {	//检查栈是否为空
    7. 			pre_index = indices.top();		//储存栈顶矩形的位置
    8. 			indices.pop();
    9. 			height = heights[pre_index];	//储存高度
    10. 			if (indices.empty()) {			//避免操作空栈
    11. 				width = i;					//若弹出至栈为空，因栈的递增性，边界可向左延伸至0
    12. 			} else {
    13. 				width = i - indices.top() - 1;		//储存宽度
    14. 			}
    15. 			area = area > (width * height) ? area : (width * height);		//更新结果
    16. 		}
    17. 		indices.push(i);
    18. 	}
    19. 	return area;
    20. }

  • 相关阅读:
    Java实现人脸识别和指纹认证
    python回调函数之获取jenkins构建结果
    vue父子组件传值：父传子、子传父
    CSS - PC / 移动端左右满屏高度布局（100% 高度 + 溢出滚动条）
    十大经典管理定律，学会轻松带团队！
    AtomicLong与LongAdder（下）
    【Kafka专题】Kafka快速实战以及基本原理详解
    学习强化学习该具备的技能和环境
    DirectX11 With Windows SDK--39 阴影技术（VSM、ESM）
    一次性看懂 C/C++ 当中的声明规则 与 const
  • 原文地址：https://blog.csdn.net/qq_32378713/article/details/126719610