顺序表实现手写栈模版可背诵用于算法竞赛

全部代码

#include<iostream> 
usingnamespacestd;
typedefint eT; 

structStack {
int* data;
int size, cap;

    Stack() : data(newint[5]), size(0), cap(5) {}

    ~Stack() {
delete[] data;
    }

    Stack(const Stack&) = delete;
    Stack& operator=(const Stack&) = delete;

boolempty()const{
return size == 0;
    }

voidpush(int x){
if (size == cap) {
int ncap = cap * 2;
int* nd = newint[ncap];
for (int i = 0; i < size; ++i) nd[i] = data[i];
delete[] data;
            data = nd;
            cap = ncap;
        }
        data[size++] = x;
    }

inttop()const{
return data[size - 1];
    }

voidpop(){
        --size;
    }
};

intmain()
{
 Stack s;
 s.push(10);
 s.push(20);
 s.push(30);
cout << s.top() << endl;
 s.pop();
cout << s.top() << endl;
return0;
}

代码解析

这段代码实现了一个动态扩容的整数栈（Stack），下面逐部分分析：

整体结构

这是一个基于动态数组实现的栈，支持自动扩容，遵循后进先出（LIFO）原则。

成员变量

关键函数解析

构造函数

Stack() : data(newint[5]), size(0), cap(5) {}

初始分配容量为 5 的数组，栈为空。

析构函数

~Stack() { delete[] data; }

释放动态分配的内存，防止内存泄漏。

禁用拷贝 初学者可以先不考虑这一段

Stack(const Stack&) = delete;
Stack& operator=(const Stack&) = delete;

删除了拷贝构造和拷贝赋值，防止浅拷贝导致的双重释放（double free）问题。

push（入栈）

voidpush(int x){
if (size == cap) {           // 容量满时扩容
int ncap = cap * 2;      // 容量翻倍
int* nd = newint[ncap];
for (int i = 0; i < size; ++i) nd[i] = data[i];
delete[] data;           // 释放旧数组
        data = nd;               // 指向新数组
        cap = ncap;
    }
    data[size++] = x;
}

当栈满时，容量翻倍（5 → 10 → 20 → …），将旧数据拷贝到新数组，再释放旧数组。这是经典的倍增策略，均摊时间复杂度为 O(1)。

top（查看栈顶）

inttop()const{ return data[size - 1]; }

返回栈顶元素，但没有做空栈检查，如果栈为空会导致越界访问。

pop（出栈）

voidpop(){ --size; }

仅将 size 减 1，没有实际删除数据（逻辑删除），也没有做下溢检查。

main 函数执行流程

Stack s;           // 创建栈，cap=5, size=0
s.push(10);        // 栈：[10]
s.push(20);        // 栈：[10, 20]
s.push(30);        // 栈：[10, 20, 30]
cout << s.top();   // 输出 30
s.pop();           // 栈：[10, 20]
cout << s.top();   // 输出 20

输出结果：

30
20

可改进之处

• top() 和 pop() 缺少边界检查：空栈时调用会引发未定义行为，建议加入断言或抛出异常。
• typedef int eT; 未被使用：定义了类型别名但代码中未用到。
• 没有 shrink 机制：只扩容不缩容，如果大量 pop 后内存不会回收。
• 异常安全：push 中 new 失败时，旧 data 已被释放但新内存未分配成功，会导致数据丢失。更安全的做法是先分配再释放。