算法设计题:设计一个算法,利用顺序栈的基本运算删除栈中所有元素e而保持其他元素次序不变。
时间: 2023-05-29 09:05:21 浏览: 81
算法思路:
1. 初始化一个辅助栈;
2. 从原栈中依次弹出元素,如果不是要删除的元素e,则将其压入辅助栈中;
3. 循环结束后,将辅助栈中的元素全部压回原栈中。
算法实现:
```
void deleteElement(SeqStack *S, ElemType e) {
SeqStack S2;
InitStack(&S2);
while (!StackEmpty(S)) {
ElemType x;
Pop(S, &x);
if (x != e) {
Push(&S2, x);
}
}
while (!StackEmpty(&S2)) {
ElemType x;
Pop(&S2, &x);
Push(S, x);
}
}
```
时间复杂度为O(n),空间复杂度为O(n)。
相关问题
设计一个算法:利用顺序栈的基本运算删除栈中所有元素e而保持其他元素次序不变。
1. 初始化一个空栈S2。
2. 从栈S1中依次出栈元素,如果元素值不为e,则将其压入栈S2中。
3. 当栈S1为空时,将栈S2中的元素全部出栈并压入栈S1中。此时栈S1中的元素次序不变,而所有值为e的元素均已被删除。
设计一个算法,利用顺序栈的基本运算删除栈中所有元素e而保持其他元素次序不变。
1. 初始化一个空的辅助栈tempStack。
2. 从原栈中循环取出元素,如果元素不等于e,则将元素压入辅助栈tempStack。
3. 将辅助栈tempStack中的元素依次弹出,并压入原栈中。
4. 原栈中所有等于e的元素已被删除,其他元素次序不变。
算法实现:
```
void deleteElement(SeqStack &s, ElemType e) {
SeqStack tempStack;
InitStack(tempStack); // 初始化辅助栈tempStack
while (!StackEmpty(s)) {
ElemType elem;
Pop(s, elem); // 从原栈中取出元素
if (elem != e) {
Push(tempStack, elem); // 如果元素不等于e,则将元素压入辅助栈tempStack
}
}
while (!StackEmpty(tempStack)) {
ElemType elem;
Pop(tempStack, elem);
Push(s, elem); // 将辅助栈tempStack中的元素依次弹出,并压入原栈中
}
}
```