使用数组实现栈的代码,并说明数组栈的特点。
时间: 2024-10-20 16:09:23 浏览: 22
使用数组实现栈的简单代码示例如下,这里以Python为例:
```python
class ArrayStack:
def __init__(self, capacity):
self.stack = [0] * capacity
self.top = -1
def is_empty(self):
return self.top == -1
def push(self, item):
if not self.is_full():
self.top += 1
self.stack[self.top] = item
def pop(self):
if not self.is_empty():
item = self.stack[self.top]
self.top -= 1
return item
else:
raise IndexError("Pop from an empty stack")
def is_full(self):
return self.top == len(self.stack) - 1
# 使用示例
s = ArrayStack(5)
s.push(1)
s.push(2)
print(s.pop()) # 输出2
```
数组栈的特点包括:
1. **高效插入和删除**:由于数组的随机访问特性,常数时间内可以完成元素的压入(push)和弹出(pop)操作。
2. **容量固定**:初始化时需要指定栈的最大容量,一旦满载就无法再添加元素,此时可能会引发异常。
3. **空间效率**:连续存储元素,不需要额外的指针指向每个元素。
4. **线性时间复杂度**:对于某些操作如查找某个位置的元素,其时间复杂度为O(n),因为在最坏的情况下需要遍历整个栈。
阅读全文