💡Author：信安2002钱泽枢(ShiQuLiZhi)
🚀欢迎访问我的作业合集：https://sxhthreo.github.io/categories/%E4%BD%9C%E4%B8%9A/
第一题
请给出栈的实现策略，使得入栈、出栈与求最小值都能在O(1)内完成，请进行相应的算法分析。
1.1 算法分析
本题我采用的是顺序存储栈(链式存储同理)。入栈、出栈在O(1)内完成是栈的特性，通过栈的基本操作即可实现。我通过设置min栈，当min栈中没有元素(即第一次入栈)或当前元素小于等于min的栈顶，对min进行压栈；当S出栈的元素与min栈的元素相同，则也将min栈栈顶弹出。当想知道栈中最小的元素时，仅需调用getMin函数，返回min栈的栈顶。
1.2 代码实现
// 设计一种策略,使得对于栈的出栈、入栈及求最小的操作时间性能均为O(1).
#include<iostream>
using namespace std;
#define MaxSize 10
#define ElemType int
typedef struct
{
ElemType data[MaxSize]; //静态数组存放栈中元素
int top;
}SqStack;
class Stack {
public:
bool Push(ElemType x)
{
if (S.top == MaxSize - 1)
return false;
S.data[++S.top] = x;
cout << "将要入栈的元素是" << S.data[S.top] << endl;
if (min.top == -1 || S.data[S.top] <= min.data[min.top]) //如果当前元素小于min的栈顶,对min压栈
min.data[++min.top] = x;
return true;
}
bool Pop()
{
if (S.top == -1)
return false;
cout << "将要出栈的元素是" << S.data[S.top] << endl;
if (S.top == min.top)
{
S.top--;
min.top--;
}
return true;
}
void Init()
{
S.top = min.top = -1;
}
ElemType getMin()
{
return min.data[min.top];
}
private:
SqStack S, min;
};
int main()
{
Stack stack;
stack.Init();
stack.Push(2);
stack.Push(3);
stack.Push(4);
stack.Pop();
stack.Push(1);
stack.Push(100);
stack.Push(0);
cout << "最小值为:" << stack.getMin() << endl;
return 0;
}1.3 运行截图
多次测试，本程序符合题目预期。
第二题
请给出策略如最多使用一个辅助栈，实现关键字系列的排序（默认正序），并进行相应的算法分析。
2.1 算法分析
本题我采用的是顺序存储栈(链式存储同理)。通过addElement函数将关键字读入，然后调用sort函数进行排序。栈S是原栈，Sorted是辅助栈，存放排好次序的元素序列。当S中仍存在元素时，对S中的元素进行弹出，并通过循环，每当当前弹出的元素比排好序的辅助栈的栈顶元素大时，需要将排好序的辅助栈的元素弹出，进入原栈，待辅助栈中的元素有序时，将剩下的元素出原栈并进入辅助栈(其中将用count记录有多少元素弹出)。经过以上循环，S中的元素会有序存放在Sorted栈中。
2.2 代码实现
// 设计一个基于栈的排序方法(这里升序,降序同理)
#include<iostream>
using namespace std;
#define MaxSize 10
#define ElemType int
typedef struct
{
ElemType data[MaxSize]; //静态数组存放栈中元素
int top;
}SqStack;
class Stack {
public:
bool Push(SqStack &st,ElemType x)
{
if (st.top == MaxSize - 1)
return false;
st.data[++st.top] = x;
return true;
}
bool Pop(SqStack &st,ElemType &element)
{
if (st.top == -1)
return false;
element = st.data[st.top];
st.top--;
return true;
}
void addElement(ElemType element) //增加元素
{
Push(S, element);
}
void removeElement() //删除元素
{
int element;
Pop(S,element);
}
bool sort()
{
if (S.top == -1)
return false;
int element,linshi;
while (S.top != -1)
{
Pop(S, element);
int count = 0; //记录当前有多少个元素出栈
while (true)
{
if (Sorted.top == -1 || element <= Sorted.data[Sorted.top])
{
break;
}
else
{
Pop(Sorted, linshi); //将元素出排序栈
Push(S, linshi); //进入原栈
count++;
}
}
Push(Sorted, element); //将元素进排序栈
while (count > 0)
{
Pop(S, linshi); //将元素出原栈
Push(Sorted, linshi); //进入排序栈
count--;
}
}
return true;
}
void PrintStack()
{
cout << "排序结果为:";
for (int i = Sorted.top; i >= 0; i--)
{
cout << Sorted.data[i] << " ";
}
cout << endl;
}
void Init()
{
S.top = -1;
Sorted.top = -1;
}
private:
SqStack S,Sorted;
};
int main()
{
Stack stack;
stack.Init();
stack.addElement(4);
stack.addElement(5);
stack.addElement(1);
stack.addElement(3);
stack.addElement(10);
stack.addElement(0);
stack.removeElement();
stack.sort();
stack.PrintStack();
return 0;
}2.3 运行截图
输入以下元素：
stack.addElement(4);
stack.addElement(5);
stack.addElement(1);
stack.addElement(3);
stack.addElement(10);
stack.addElement(0);
stack.removeElement(); //弹出0运行截图如下：
多次测试，本程序符合题目预期。
