栈的链式存储结构c++

栈的链式存储结构指的是使用链表实现栈的存储结构。在链栈中，每个元素都由一个节点表示，节点中包含数据元素和指向下一个节点的指针。链表的头部表示栈顶，插入和删除操作都在链表的头部进行。与顺序栈不同，链栈不存在存储空间满的情况，因此可以看作是一个无底洞。

在C语言中，我们可以使用typedef struct来定义链栈的节点结构，并使用SNode*类型来表示链栈的指针。具体代码如下所示：

typedef struct node {
StackElementType data;
struct node* next;
} SNode;

typedef SNode* LinkStack;

LinkStack top;

在链栈中，可以通过遍历链表来获取链栈的高度（长度）。我们可以使用一个指针p，将头节点的地址传给p，然后使用while循环进行累加操作，最后输出链栈的长度。具体代码如下所示：

int get_length_Stack() {
SNode* p;
int len = 0;
p = top->next;

while (p != NULL) {
len++;
p = p->next;
}

printf("链栈的长度为：%d\n", len);
return 1;
}

相关问题

设计一个栈，采用链式存储结构，完成创建、入栈或出栈，用c++代码表示

以下是一个基于链表的栈的 C 代码实现：

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 定义栈结构体
typedef struct Stack {
    Node* top;
} Stack;

// 初始化栈
void init(Stack* s) {
    s->top = NULL;
}

// 入栈
void push(Stack* s, int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = s->top;
    s->top = node;
}

// 出栈
int pop(Stack* s) {
    if (s->top == NULL) {
        printf("栈已空\n");
        return -1;
    }
    int data = s->top->data;
    Node* temp = s->top;
    s->top = s->top->next;
    free(temp);
    return data;
}

int main() {
    Stack s;
    init(&s);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    return 0;
}

这个栈采用链式存储结构，每个节点包含一个数据和一个指向下一个节点的指针。栈的顶部指针指向链表的第一个节点。入栈时，新节点插入到链表的头部，成为新的栈顶。出栈时，返回栈顶节点的数据，并将栈顶指针指向下一个节点。如果栈已空，则返回 -1。

链式存储的栈双向链表实现

链式存储的栈可以通过双向链表来实现。双向链表是一种数据结构，其中每个节点都包含一个指向前驱节点和后继节点的指针。栈是一种具有后进先出（LIFO）特性的数据结构，可以在链表的头部进行插入和删除操作。

下面是使用双向链表实现链式存储的栈的示例代码（使用C++语言）：

#include <iostream>

// 定义双向链表节点结构体
struct Node {
    int data;       // 数据
    Node* prev;     // 前驱节点指针
    Node* next;     // 后继节点指针
    
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

// 定义链式存储的栈类
class Stack {
private:
    Node* top;      // 栈顶指针
    
public:
    Stack() : top(nullptr) {}
    
    // 判断栈是否为空
    bool isEmpty() {
        return top == nullptr;
    }
    
    // 入栈操作
    void push(int val) {
        Node* newNode = new Node(val);
        
        if (isEmpty()) {
            top = newNode;
        } else {
            newNode->next = top;
            top->prev = newNode;
            top = newNode;
        }
        
        std::cout << val << " 入栈成功！" << std::endl;
    }
    
    // 出栈操作
    int pop() {
        if (isEmpty()) {
            std::cout << "栈为空，无法进行出栈操作！" << std::endl;
            return -1;  // 返回一个特殊值表示出错
        }
        
        int val = top->data;
        Node* temp = top;
        
        if (top->next != nullptr) {
            top = top->next;
            top->prev = nullptr;
        } else {
            top = nullptr;
        }
        
        delete temp;
        std::cout << val << " 出栈成功！" << std::endl;
        
        return val;
    }
    
    // 获取栈顶元素
    int getTop() {
        if (isEmpty()) {
            std::cout << "栈为空，无法获取栈顶元素！" << std::endl;
            return -1;  // 返回一个特殊值表示出错
        }
        
        return top->data;
    }
};

int main() {
    Stack stack;
    
    stack.push(10);
    stack.push(20);
    stack.push(30);
    
    std::cout << "栈顶元素为：" << stack.getTop() << std::endl;
    
    stack.pop();
    stack.pop();
    
    std::cout << "栈顶元素为：" << stack.getTop() << std::endl;
    
    stack.pop();
    
    return 0;
}

这个示例中，我们使用双向链表的头部作为栈顶，并且在入栈操作时将新节点插入链表的头部，出栈操作时删除链表的头部节点。通过双向链表的前驱和后继指针，我们可以方便地在链表头部进行插入和删除操作，并且可以随时获取栈顶元素。