顺序栈的各种基本运算算法
时间: 2024-10-17 15:01:23 浏览: 95
顺序栈是一种基于数组或链表的数据结构,它支持的基本运算主要有四种:
压入元素(Push): 向栈顶添加一个新元素。这是最简单的操作,通常涉及将元素添加到栈底,并调整栈顶指针。
弹出元素(Pop): 删除并返回栈顶元素,然后将栈顶指针向下移动一位。如果栈为空,此操作会抛出异常或返回特定值表示空栈。
查看栈顶元素(Peek 或 Top): 不删除栈顶元素,只返回其值。如果栈为空,则返回默认值或抛出异常。
判断是否为空(IsEmpty 或 Size 或 Count): 检查栈是否包含任何元素。如果栈顶指针指向数组或链表的末尾,即为空。
获取栈的大小(Size 或 Count): 返回栈中当前元素的数量。对于数组栈,这通常是通过计算
top - bottom + 1
得出;链表栈则直接访问节点计数。清空栈(Clear 或 PopAll): 将栈内的所有元素移除,恢复成初始状态。这通常涉及到将栈顶指针置为0或指向开始位置。
在实现上,顺序栈通常需要维护一个额外的变量来跟踪栈顶的位置。以下是这些操作的伪代码示例:
Stack struct {
top; // 栈顶指针
items[]; // 存储数据的数组或链表
}
// Push
void push(Stack &s, int value) {
s.items[s.top++] = value;
}
// Pop
int pop(Stack &s) {
if (s.isEmpty()) return NULL; // 返回特殊值或抛异常
int value = s.items[s.top];
s.top--;
return value;
}
// Peek
int peek(Stack &s) {
if (s.isEmpty()) return NULL; // 返回特殊值或抛异常
return s.items[s.top];
}
// IsEmpty/Size/Count
bool isEmpty(Stack &s) { return s.top == 0; }
int size(Stack &s) { return s.top; }
// Clear/PopAll
void clear(Stack &s) {
s.top = 0;
}
相关推荐

















