初级数据结构——栈

前言

数据结构栈（Stack）是一种线性的数据结构，它只允许在序列的一端（称为栈顶）进行插入和删除操作。这种特性使得栈成为许多算法和问题解决中的有力工具。以下是对栈的详细分析：

一、栈的基本概念

1.定义：栈是一种后进先出（LIFO, Last In First Out）的数据结构，即最后插入的元素将是第一个被移除的元素。

2.基本操作：
压栈（Push）：将元素添加到栈顶。
弹栈（Pop）：移除并返回栈顶的元素。
查看栈顶元素（Peek 或 Top）：返回栈顶的元素但不移除它。
检查栈是否为空（IsEmpty）：判断栈是否为空。

二、栈的实现方式

1.数组实现：
优点：实现简单，访问速度快。
缺点：需要预先分配固定大小的内存空间，可能存在内存浪费或扩容问题。

2.链表实现：
优点：内存使用灵活，不需要预先分配固定大小的内存空间。
缺点：相对数组实现，访问速度可能较慢（因为需要遍历链表）。

三、栈的性能分析

时间复杂度：
压栈（Push）：O(1)，因为只需要在栈顶添加元素。
弹栈（Pop）：O(1)，因为只需要移除栈顶元素。
查看栈顶元素（Peek 或 Top）：O(1)，因为只需要访问栈顶元素。
检查栈是否为空（IsEmpty）：O(1)，因为只需要判断栈顶指针是否为空。

空间复杂度：
数组实现：O(n)，其中n是栈的容量。
链表实现：O(m)，其中m是栈中元素的数量（动态分配内存）。

四、栈的应用场景

函数调用和递归：栈用于保存函数调用和递归调用的上下文信息。
表达式求值：栈用于解析和计算后缀表达式（逆波兰表示法）。
深度优先搜索（DFS）：在图的遍历中，栈用于实现深度优先搜索。
括号匹配：栈用于检查表达式中的括号是否匹配。
页面访问历史：在浏览器中，栈用于管理页面的访问历史。
撤销操作：在文本编辑器、图像处理软件等中，栈用于实现撤销（undo）操作。
语法分析：在编译器设计中，栈用于语法分析过程中的符号表管理和操作符优先级处理。

五、栈的变体

双栈：使用两个栈来模拟队列等数据结构。
栈的栈：栈中的元素本身也是栈，用于实现更复杂的嵌套数据结构。
多维栈：将栈扩展到多维空间，用于处理多维数据。

六、出栈入栈的动态图解

入栈：

出栈

七、代码模版

顺序栈

#include<iostream>
#include<exception>
using namespace std;

template<typename T>//定制栈里面的元素，就像vector一样
class Stack {
private:
int size;//既为栈元素个数又为栈顶位置
int capacity;
T* data;
void resize();
public:
Stack():data(new T[capacity]),size(0),capacity(10){}//构造函数，申请类型为T容量为capacity的内存空间，相当于数组
~Stack();
void push(T x);
T top() const;
T pop();
int getSize() const;
bool empty() const;
};

template<typename T>
void Stack<T>::resize() {//顺序栈扩容
int newCapacity = 2 * capacity;
T* newData = new T[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
delete[]data;
data = newData;
capacity = newCapacity;
}

template<typename T>
Stack<T>::~Stack() {
delete[]data;
}

template<typename T>
void Stack<T>::push(T x) {
if (size == capacity) {
resize();
}
data[size++] = x;
}

template<typename T>
T Stack<T>::top() const {
if (!size) {
throw std::underflow_error("Stack is empty");//如果栈为空即为非法状态，抛出异常
}
return data[size - 1];//注意栈元素序号从零开始
}

template<typename T>
T Stack<T>::pop(){
if (!size) {
throw std::underflow_error("Stack is empty");
}
return data[--size];
}

template<typename T>
int Stack<T>::getSize() const {
return size;
}

template<typename T>
bool Stack<T>::empty() const {
return size == 0 ? 1 : 0;
}

int main() {

Stack<int> s;
for (int i = 0; i < 5; i++) {
s.push(i);
}
int x=s.pop();
cout << x << " " << s.top() << endl;
cout << s.getSize() << endl;
cout << s.empty() << endl;

return 0;
}

链式栈

#include<iostream>
#include<stdexcept>
#include<stack>
using namespace std;

template<typename T>
class Stack {
private:
struct Node{
T data;
Node* next;
Node(T x):data(x),next(NULL){}
};
Node* head;
int size;
public:
Stack():size(0),head(NULL){}
~Stack();
void push(T x);
T top() const;
T pop();
bool empty();
int getSize();
};

template<typename T>
Stack<T>::~Stack() {
while (head) {
Node* t = head;
head = head->next;
delete t;
}
}

template<typename T>
void Stack<T>::push(T x) {//插入操作用头插法，即头节点为栈顶
Node* newNode = new Node(x);
newNode->next = head;
head = newNode;
size++;
}

template<typename T>
T Stack<T>::top() const {
if (!head) {
throw std::underflow_error("Stack is empty!");
}
return head->data;
}

template<typename T>
T Stack<T>::pop() {
if (!head) {
throw std::underflow_error("Stack is empty!");
}
T result = head->data;
Node* t = head;
head = head->next;
delete t;
size--;
return result;
}

template<typename T>
int Stack<T>::getSize() {
return size;
}

template<typename T>
bool Stack<T>::empty() {
return size == 0 ? 1 : 0;
}

int main() {
int n;
while (cin >> n) {
Stack<int>s;
while (n) {
s.push(n % 2);
n /= 2;
}
while (!s.empty()) {
int x = s.pop();
cout << x;
}
cout << endl;
}


return 0;
}

八、总结

栈是一种简单而强大的数据结构，它遵循后进先出的原则，并通过数组或链表等数据结构实现。栈在多种算法和场景中都有广泛应用，包括函数调用、递归、表达式求值、深度优先搜索、括号匹配等。理解栈的基本概念和操作对于掌握计算机科学和数据结构的基础知识至关重要。同时，栈的变体也为解决特定问题提供了更多可能性。

结语

下个作品我会更新有关栈的题库，进行栈的实战巩固知识，当然你也可以去力扣等相关刷题网站找题目刷题。

想看更多内容可以关注我，看我作品，关注我让我们一起学习编程，希望大家能点赞关注支持一下，让我有持续更新的动力，谢谢大家

原文地址：https://blog.csdn.net/ycs66/article/details/143779817

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！