栈的实现及基本操作
时间: 2023-10-11 13:08:19 浏览: 43
栈是一种基于先进后出(LIFO)原则的数据结构,常用于实现函数调用、表达式求值、括号匹配等应用场景。栈的实现可以通过数组或链表来实现,以下是栈的基本操作:
1. push:将元素压入栈顶
2. pop:将栈顶元素弹出并返回其值
3. peek/top:返回栈顶元素的值,但不弹出
4. isEmpty:判断栈是否为空
5. isFull:判断栈是否已满(仅适用于数组实现)
数组实现的栈,需要维护一个栈顶指针,指向栈顶元素的位置;链表实现的栈,需要维护一个头节点,每次插入元素时,将其插入头节点之后,成为新的头节点。
以下是一个用数组实现的栈的示例代码(C++):
```c++
class Stack {
private:
int* arr; // 栈的数组
int top; // 栈顶指针
int size; // 栈的最大容量
public:
Stack(int s) {
size = s;
arr = new int[size];
top = -1;
}
~Stack() {
delete[] arr;
}
void push(int value) {
if (top == size - 1) {
cout << "Stack overflow!" << endl;
return;
}
arr[++top] = value;
}
int pop() {
if (top == -1) {
cout << "Stack underflow!" << endl;
return -1;
}
return arr[top--];
}
int peek() {
if (top == -1) {
cout << "Stack is empty!" << endl;
return -1;
}
return arr[top];
}
bool isEmpty() {
return top == -1;
}
bool isFull() {
return top == size - 1;
}
};
```