【数据结构C/C++】链式存储与顺序存储结构栈

骑猪看日落 2024-02-23 07:22 70阅读 0赞

#### 文章目录 ####

*  链式存储结构
 *  顺序存储结构

下面这篇文章是我大二时候写的比较详细的实现过程，再这篇文章我也会再一次比较简单的再次简述一下链式与顺序存储结构的实现方式。  
[链式存储结构与顺序存储结构详解][Link 1]  
这里我就不使用C++再一次实现这两个栈了，有兴趣的也可以使用C++的STL库中的stack直接实现。

实现思路如下：

首先，我们定义了一个节点结构Node，每个节点包含一个整数数据和指向下一个节点的指针。  
然后，我们定义了栈结构Stack，其中包括一个指向栈顶节点的指针top和一个表示栈大小的整数size。  
初始化栈时，将top指针设置为NULL，表示栈为空，同时将size设置为0。  
入栈操作(push)创建一个新节点，将数据存储在新节点中，然后将新节点插入到栈顶，并更新top和size。  
出栈操作(pop)从栈顶移除一个节点，返回其数据，并释放节点内存，同时更新top和size。  
查看栈顶元素操作(peek)返回栈顶节点的数据，不修改栈的状态。  
打印栈中元素操作(printStack)遍历栈中的节点，打印每个节点的数据。  
主函数中使用一个循环来接收用户输入的选项，然后调用相应的栈操作，以实现增删改查功能。

## 链式存储结构 ##

#include <stdio.h>
    #include <stdlib.h>
    
    // 定义节点结构
    typedef struct Node {
        
        int data;
        struct Node *next;
    } Node;
    
    // 定义栈结构
    typedef struct Stack {
        
        Node *top;
        int size;
    } Stack;
    
    // 初始化栈
    void initStack(Stack *stack) {
        
        stack->top = NULL;
        stack->size = 0;
    }
    
    // 入栈操作
    void push(Stack *stack, int data) {
        
        Node *newNode = (Node *)malloc(sizeof(Node));
        if (newNode == NULL) {
        
            printf("内存分配失败\n");
            exit(1);
        }
        newNode->data = data;
        newNode->next = stack->top;
        stack->top = newNode;
        stack->size++;
    }
    
    // 出栈操作
    int pop(Stack *stack) {
        
        if (stack->top == NULL) {
        
            printf("栈为空\n");
            return -1; // 返回一个特殊值表示栈为空
        }
        Node *temp = stack->top;
        int data = temp->data;
        stack->top = temp->next;
        free(temp);
        stack->size--;
        return data;
    }
    
    // 查看栈顶元素
    int peek(Stack *stack) {
        
        if (stack->top == NULL) {
        
            printf("栈为空\n");
            return -1; // 返回一个特殊值表示栈为空
        }
        return stack->top->data;
    }
    
    // 打印栈中的元素
    void printStack(Stack *stack) {
        
        Node *current = stack->top;
        printf("栈中的元素: ");
        while (current != NULL) {
        
            printf("%d ", current->data);
            current = current->next;
        }
        printf("\n");
    }
    
    int main() {
        
        Stack stack;
        initStack(&stack);
    
        int choice, data;
    
        while (1) {
        
            printf("1. 入栈  2. 出栈  3. 查看栈顶元素  4. 打印栈  5. 退出\n");
            printf("请输入选项: ");
            scanf("%d", &choice);
    
            switch (choice) {
        
                case 1:
                    printf("请输入要入栈的数据: ");
                    scanf("%d", &data);
                    push(&stack, data);
                    break;
                case 2:
                    data = pop(&stack);
                    if (data != -1)
                        printf("出栈的元素是: %d\n", data);
                    break;
                case 3:
                    data = peek(&stack);
                    if (data != -1)
                        printf("栈顶元素是: %d\n", data);
                    break;
                case 4:
                    printStack(&stack);
                    break;
                case 5:
                    exit(0);
                default:
                    printf("无效选项\n");
            }
        }
    
        return 0;
    }

## 顺序存储结构 ##

实现思路如下：

首先，我们定义了一个栈结构Stack，其中包括一个指向整数数组的指针array，栈的容量capacity，栈顶索引top，和当前栈中的元素个数size。  
初始化栈时，分配内存并初始化Stack结构的字段，包括分配内存给array数组，将top初始化为-1表示栈为空，将size初始化为0。  
入栈操作(push)检查栈是否已满，如果没有满，将数据存储在数组中，并更新top和size。  
出栈操作(pop)检查栈是否为空，如果不为空，从数组中取出元素，更新top和size，并返回出栈的元素。  
查看栈顶元素操作(peek)检查栈是否为空，如果不为空，返回栈顶元素。  
打印栈中元素操作(printStack)遍历数组中的元素，打印每个元素。  
主函数中使用一个循环来接收用户输入的选项，然后调用相应的栈操作，以实现增删改查功能。

#include <stdio.h>
    #include <stdlib.h>
    
    // 定义栈结构
    typedef struct Stack {
        
        int *array;  // 用于存储栈元素的数组
        int capacity; // 栈的容量
        int top;      // 栈顶索引
        int size;     // 当前栈中的元素个数
    } Stack;
    
    // 初始化栈
    Stack* initStack(int capacity) {
        
        Stack *stack = (Stack *)malloc(sizeof(Stack));
        if (stack == NULL) {
        
            printf("内存分配失败\n");
            exit(1);
        }
        stack->capacity = capacity;
        stack->array = (int *)malloc(sizeof(int) * capacity);
        if (stack->array == NULL) {
        
            printf("内存分配失败\n");
            exit(1);
        }
        stack->top = -1; // 初始化栈顶索引为-1，表示栈为空
        stack->size = 0; // 初始化栈中元素个数为0
        return stack;
    }
    
    // 入栈操作
    void push(Stack *stack, int data) {
        
        if (stack->size >= stack->capacity) {
        
            printf("栈已满\n");
            return;
        }
        stack->array[++stack->top] = data;
        stack->size++;
    }
    
    // 出栈操作
    int pop(Stack *stack) {
        
        if (stack->size <= 0) {
        
            printf("栈为空\n");
            return -1; // 返回一个特殊值表示栈为空
        }
        int data = stack->array[stack->top--];
        stack->size--;
        return data;
    }
    
    // 查看栈顶元素
    int peek(Stack *stack) {
        
        if (stack->size <= 0) {
        
            printf("栈为空\n");
            return -1; // 返回一个特殊值表示栈为空
        }
        return stack->array[stack->top];
    }
    
    // 打印栈中的元素
    void printStack(Stack *stack) {
        
        if (stack->size == 0) {
        
            printf("栈为空\n");
            return;
        }
        printf("栈中的元素: ");
        for (int i = 0; i <= stack->top; i++) {
        
            printf("%d ", stack->array[i]);
        }
        printf("\n");
    }
    
    int main() {
        
        int capacity;
        printf("请输入栈的容量: ");
        scanf("%d", &capacity);
    
        Stack *stack = initStack(capacity);
    
        int choice, data;
    
        while (1) {
        
            printf("1. 入栈  2. 出栈  3. 查看栈顶元素  4. 打印栈  5. 退出\n");
            printf("请输入选项: ");
            scanf("%d", &choice);
    
            switch (choice) {
        
                case 1:
                    printf("请输入要入栈的数据: ");
                    scanf("%d", &data);
                    push(stack, data);
                    break;
                case 2:
                    data = pop(stack);
                    if (data != -1)
                        printf("出栈的元素是: %d\n", data);
                    break;
                case 3:
                    data = peek(stack);
                    if (data != -1)
                        printf("栈顶元素是: %d\n", data);
                    break;
                case 4:
                    printStack(stack);
                    break;
                case 5:
                    free(stack->array);
                    free(stack);
                    exit(0);
                default:
                    printf("无效选项\n");
            }
        }
    
        return 0;
    }

下面是使用C++的stack库实现的栈，这个相当于没有实现任何功能，考研可不推荐这样子玩，当然如果考察的重点不是栈，而是使用栈解决某个问题，那么可以使用stack

#include <iostream>
    #include <stack>
    
    using namespace std;
    
    int main() {
        
        stack<int> myStack;
        
        while (true) {
        
            int choice, data;
            
            cout << "1. 入栈  2. 出栈  3. 查看栈顶元素  4. 打印栈  5. 退出" << endl;
            cout << "请输入选项: ";
            cin >> choice;
    
            switch (choice) {
        
                case 1:
                    cout << "请输入要入栈的数据: ";
                    cin >> data;
                    myStack.push(data);
                    break;
                case 2:
                    if (!myStack.empty()) {
        
                        cout << "出栈的元素是: " << myStack.top() << endl;
                        myStack.pop();
                    } else {
        
                        cout << "栈为空" << endl;
                    }
                    break;
                case 3:
                    if (!myStack.empty()) {
        
                        cout << "栈顶元素是: " << myStack.top() << endl;
                    } else {
        
                        cout << "栈为空" << endl;
                    }
                    break;
                case 4:
                    if (!myStack.empty()) {
        
                        cout << "栈中的元素: ";
                        stack<int> tempStack = myStack;
                        while (!tempStack.empty()) {
        
                            cout << tempStack.top() << " ";
                            tempStack.pop();
                        }
                        cout << endl;
                    } else {
        
                        cout << "栈为空" << endl;
                    }
                    break;
                case 5:
                    return 0;
                default:
                    cout << "无效选项" << endl;
            }
        }
    
        return 0;
    }

[Link 1]: https://blog.csdn.net/Zhangsama1/article/details/119581560?utm_source%20=%20uc_fansmsg