C++数据结构X篇_08_C++实现栈的顺序存储与链式存储

**C++数据结构X篇_08_C++实现栈的顺序存储与链式存储**

在前面的章节中，我们已经学习了栈的基本概念、运算以及应用。现在，我们将重点讨论如何使用C++来实现栈的顺序存储和链式存储。

**1. 栈的顺序存储**

栈的顺序存储是指在计算机内存中，使用一块连续的空间来存放栈元素。这种存储方式通常适用于小规模数据或固定大小的栈。

###1.1 顺序栈的实现

cpp#include <iostream>

class Stack {
private:
 int* elements; // 栈元素数组 int top; // 栈顶指针 int capacity; // 栈容量public:
 Stack(int capacity) : capacity(capacity), top(-1) {
 elements = new int[capacity];
 }

 ~Stack() {
 delete[] elements;
 }

 bool isEmpty() const {
 return top == -1;
 }

 bool isFull() const {
 return top == capacity -1;
 }

 void push(int element) {
 if (isFull()) {
 std::cerr << "栈已满!" << std::endl;
 return;
 }
 elements[++top] = element;
 }

 int pop() {
 if (isEmpty()) {
 std::cerr << "栈为空!" << std::endl;
 return -1; // 返回-1表示出错 }
 return elements[top--];
 }

 int peek() const {
 if (isEmpty()) {
 std::cerr << "栈为空!" << std::endl;
 return -1; // 返回-1表示出错 }
 return elements[top];
 }
};

cppint main() {
 Stack stack(5);

 stack.push(10);
 stack.push(20);
 stack.push(30);

 std::cout << "栈顶元素:" << stack.peek() << std::endl;

 int popped = stack.pop();
 std::cout << "弹出元素:" << popped << std::endl;

 return0;
}

cpp#include <iostream>

class Node {
public:
 int data;
 Node* next;

 Node(int data) : data(data), next(nullptr) {}
};

class Stack {
private:
 Node* top; // 栈顶指针public:
 Stack() : top(nullptr) {}

 ~Stack() {
 while (top != nullptr) {
 Node* temp = top;
 top = top->next;
 delete temp;
 }
 }

 bool isEmpty() const {
 return top == nullptr;
 }

 void push(int element) {
 Node* newNode = new Node(element);
 if (isEmpty()) {
 top = newNode;
 } else {
 newNode->next = top;
 top = newNode;
 }
 }

 int pop() {
 if (isEmpty()) {
 std::cerr << "栈为空!" << std::endl;
 return -1; // 返回-1表示出错 }
 Node* temp = top;
 top = top->next;
 delete temp;
 return0;
 }

 int peek() const {
 if (isEmpty()) {
 std::cerr << "栈为空!" << std::endl;
 return -1; // 返回-1表示出错 }
 return top->data;
 }
};

cppint main() {
 Stack stack;

 stack.push(10);
 stack.push(20);
 stack.push(30);

 std::cout << "栈顶元素:" << stack.peek() << std::endl;

 int popped = stack.pop();
 std::cout << "弹出元素:" << popped << std::endl;

 return0;
}