stack数据结构讲解
时间: 2023-11-17 08:57:46 浏览: 49
栈(Stack)是一种线性数据结构,它具有后进先出(LIFO)的特点。栈的基本操作包括入栈(push)和出栈(pop),入栈操作会将元素压入栈顶,而出栈操作则会将栈顶元素弹出。
除了基本操作,栈还有一些其他的常用操作,比如获取栈顶元素(top)、判断栈是否为空(empty)等。
栈可以用数组或链表来实现。使用数组实现的栈称为顺序栈,使用链表实现的栈称为链式栈。
下面是一个使用数组实现的顺序栈的示例代码:
```c++
class Stack {
private:
int* data;
int top;
int capacity;
public:
Stack(int cap) {
data = new int[cap];
top = -1;
capacity = cap;
}
~Stack() {
delete[] data;
}
void push(int x) {
if (top == capacity - 1) {
// 栈满了
return;
}
data[++top] = x; }
void pop() {
if (top == -1) {
// 栈空了
return;
}
top--;
}
int top() {
if (top == -1) {
// 栈空了
return -1;
}
return data[top];
}
bool empty() {
return top == -1;
}
};
```