使用c++数组实现栈的代码,并说明数组栈的特点。
时间: 2024-10-20 10:09:20 浏览: 18
基于动态数组的栈
在C++中,可以使用一维数组作为基本数据结构来实现栈。下面是一个简单的基于数组的栈实现:
```cpp
#include <iostream>
class ArrayStack {
private:
int capacity; // 栈的容量
int top; // 栈顶指针
// 数组用于存储栈元素
int* stack;
public:
// 构造函数,初始化栈为空
ArrayStack(int size) : capacity(size), top(-1), stack(new int[capacity]) {}
~ArrayStack() { // 析构函数,释放内存
delete[] stack;
}
// 入栈操作
void push(int value) {
if (top == capacity - 1) {
std::cout << "Stack is full.\n";
return;
}
stack[++top] = value;
}
// 出栈操作
int pop() {
if (top == -1) {
std::cout << "Stack is empty.\n";
return -1;
}
return stack[top--];
}
// 查看栈顶元素
int peek() const {
if (top == -1) {
std::cout << "Stack is empty.\n";
return -1;
}
return stack[top];
}
// 判断栈是否为空
bool isEmpty() const {
return top == -1;
}
// 返回当前栈大小
int size() const {
return top + 1;
}
};
int main() {
ArrayStack s(5);
s.push(10);
s.push(20);
s.push(30);
std::cout << "Top element is: " << s.peek() << "\n";
std::cout << "Stack size is: " << s.size() << "\n";
s.pop();
s.pop();
return 0;
}
```
**特点:**
1. **简单直接**:数组栈实现简单直观,只需要一个数组和两个指针(栈底和栈顶)。
2. **空间效率高**:它不需要额外的空间来存储指向内部元素的引用,只需要预先分配的固定大小空间。
3. **插入和删除速度较快**:对于大多数操作(如入栈、出栈),时间复杂度都是O(1),因为只涉及数组下标的变化。
4. **动态性较差**:由于数组容量固定,当栈满时不能再添加元素,需要预估栈的最大容量。
阅读全文