建立顺序栈和链栈；实现栈的基本操作：入栈和出栈，并输出栈找那个元素，代码

建立顺序栈和链栈主要是基于数据结构的不同存储方式：

1. **顺序栈**（数组实现）：
- 它是以数组为基础的，通过下标来访问元素，栈顶元素通常放在数组的最后一个位置。
- 入栈（push）：将新元素添加到数组的顶部，如果满了需要扩容。
- 出栈（pop）：删除并返回栈顶元素，同时调整数组下标。
- 查找元素：由于连续存储，查找特定元素的时间复杂度是O(n)。

#include <iostream>
using namespace std;

const int MAX_SIZE = 100;
int stack[MAX_SIZE];
int top = -1; // 栈顶

// 入栈
void push(int item) {
    if (top == MAX_SIZE - 1) { // 判断是否已满
        cout << "Stack overflow!" << endl;
        return;
    }
    stack[++top] = item; // 增加栈顶指针并插入元素
}

// 出栈
int pop() {
    if (top == -1) { // 判断是否为空
        cout << "Stack underflow!" << endl;
        return -1;
    }
    return stack[top--]; // 返回并移除栈顶元素
}

// 查找元素
int search(int target) {
    for (int i = 0; i <= top; ++i)
        if (stack[i] == target)
            return i;
    return -1; // 如果找不到目标，返回-1
}

int main() {
    push(1);
    push(2);
    push(3);
    cout << "Top element is: " << pop() << endl;
    cout << "Element at index 2 is: " << stack[2] << endl;
    return 0;
}

2. **链栈（链表实现）**：
- 使用链表作为基础，每个节点包含数据和指向下一个节点的指针。
- 入栈：创建一个新的节点并将它链接到栈顶。
- 出栈：移除栈顶节点，并更新栈顶指针。
- 查找元素：遍历链表寻找目标值。

#include <iostream>

struct Node {
    int data;
    Node* next;
};

class Stack {
private:
    Node* top;

public:
    void push(int item) {
        Node* newNode = new Node{item, nullptr};
        newNode->next = top;
        top = newNode;
    }

    int pop() {
        if (top == nullptr) {
            cout << "Stack is empty!" << endl;
            return -1;
        }
        int item = top->data;
        Node* temp = top;
        top = top->next;
        delete temp;
        return item;
    }

    int search(int target) {
        Node* current = top;
        while (current != nullptr) {
            if (current->data == target)
                return 1;
            current = current->next;
        }
        return 0; // 没找到目标
    }
};

int main() {
    Stack s;
    s.push(1);
    s.push(2);
    s.push(3);
    cout << "Top element is: " << s.pop() << endl;
    return 0;
}