[数据结构与算法][数据结构] 五.详解栈以及两种存储结构的C语言实现

目录

认识栈

三种物理结构

1.顺序储存结构

2.链式储存结构

3.共享栈

出栈顺序的特点

C语言实现

顺序栈

链式栈

共享栈

认识栈

栈也是一种线性的逻辑结构, 和顺序表与普通链表不同的是他的操作(运算)不同

复习一下数据结构的三要素: 逻辑结构, 物理(储存结构), 操作(运算)

栈有两端: 栈顶和栈底, 只能在栈顶进行增加(入栈)和删除(出栈)

所以栈可以看成是一种操作受限的线性表

栈的特点是先进后出

三种物理结构

1.顺序储存结构

用一个数组实现栈, 用一个额外的指针指向栈顶(一般把栈底固定)

2.链式储存结构

用链表实现栈, 链表的第一个节点表示栈顶, 最后一个节点表示栈底, 只在链表的头部进行删除和增加

3.共享栈

用一个长为n数组a实现两个栈, 这两个栈的栈顶分别在a[-1]和a[n](指向栈底说明是空栈), 栈顶向中间延伸, 只有当两个栈顶相距为1时栈才满, 更好地利用了空间

出栈顺序的特点

栈方面的考察点经常是给出入栈顺序, 判断某个出栈顺序是否存在

一般这样考虑:

例如入栈为1,2,3,4....n

• 如果第1个出栈元素是n, 那么不用想了, 它是先全部入栈, 再全部出栈, 出栈顺序是n,n-1,n-2....1
• 如果第2个出栈元素是n, 那么第1个出栈元素可以是任意一个, 但是第3个出栈元素只能是n-1或者n-2
• 如果第3个出栈元素是n, 那么第1个和第2个出栈元素可以是任意一个, 但是第4个出栈元素只能是n-1,n-2,n-3
• 以此类推...

C语言实现

顺序栈

/**
 * @file sequence_stack.c
 * @author xiaoxiao (you@domain.com)
 * @brief 顺序栈
 * @version 0.1
 * @date 2022-03-05
 * 
 * @copyright Copyright (c) 2022
 * 
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MaxSize 10

typedef struct Stack {
    int* pData; // 数据
    int top; // 栈顶位置(-1表示空栈, 0表示当前栈有一个元素)
}Stack;

typedef Stack* PStack;

/**
 * @brief 初始化一个栈
 * 
 * @return PStack 栈指针
 */
PStack initailStack(){
    PStack pStack = (PStack) malloc (sizeof(PStack));
    if(pStack == NULL){
        printf("no more momery");
        exit(1);
    }
    pStack -> pData = (int*) malloc (MaxSize * sizeof(int));
    if(pStack -> pData == NULL){
        printf("no more momery");
        exit(1);
    }
    pStack -> top = -1; // 空栈
    return pStack;
}

/**
 * @brief 元素入栈
 * 
 * @param pStack 栈指针
 * @param data 入栈元素
 * @return true 入栈成功
 * @return false 入栈失败
 */
bool push(PStack pStack, int data){
    if(pStack -> top == MaxSize - 1){
        printf("栈已满, 无法进栈\n");
        return false;
    }
    pStack -> pData[pStack -> top ++ + 1] = data;
    return true;
}

/**
 * @brief 元素出栈
 * 
 * @param pStack 栈指针
 * @return int 出栈元素
 */
int pop(PStack pStack){
    if(pStack -> top == -1){
        printf("空栈不能出栈");
        return false;
    }
    return pStack -> pData[-- pStack -> top + 1];
}

/**
 * @brief 打印栈中元素
 * 
 * @param pStack 栈指针 
 * @return true 非空栈,可以打印
 * @return false 不是空栈
 */
bool printStack(PStack pStack){
    if(pStack -> top == -1){
        printf("空栈不能打印\n");
        return false;
    }
    printf("自栈底打印元素: ");
    for(int i = 0; i <= pStack -> top; i ++){
        printf("%d ", pStack -> pData[i]);
    }
    printf("\n");
    return true;
}

/**
 * @brief 销毁栈, 并释放栈空间
 * 
 * @param pStack 
 */
void destoryStack(PStack pStack){
    free(pStack -> pData);
    free(pStack);
}

int main(){
    printf("--------------------\n");
    PStack pStack = initailStack();
    push(pStack, 1);
    push(pStack, 10);
    push(pStack, 4);
    printStack(pStack);
    destoryStack(pStack);
    printf("--------------------");
    return 0;
}

链式栈

链式栈这里引用了我以前的写的链表的linked_list.h头文件

/**
 * @file linked_stack.c
 * @author xiaoxiao (you@domain.com)
 * @brief 链式栈
 * @version 0.1
 * @date 2022-03-05
 * 
 * @copyright Copyright (c) 2022
 * 
 */

#include <stdio.h>
#include "linked_list.h"

/**
 * @brief 初始化一个链式栈
 * 
 * @return PNode 头结点
 */
PNode initailStack(){
    return initalList();
}

/**
 * @brief 元素入栈
 * 
 * @param pStack 栈指针
 * @param data 入栈元素
 * @return true 入栈成功
 * @return false 入栈失败
 */
bool push(PNode pHead, int data){
    return insertByIndex(pHead, 1, data);
}

/**
 * @brief 元素出栈
 * 
 * @param pStack 栈指针
 * @return int 出栈元素
 */
int pop(PNode pHead){
    int x;
    if(pHead -> next != NULL){
        x = pHead -> next -> data;
        deleteByIndex(pHead, 1);
        return x;
    }
    printf("空栈无法出栈\n");
    return -1;
}

/**
 * @brief 打印栈中元素
 * 
 * @param pStack 栈指针 
 * @return true 非空栈,可以打印
 * @return false 不是空栈
 */
bool printStack(PNode pHead){
    if(pHead -> next == NULL){
        printf("空栈不能打印\n");
        return false;
    }
    PNode pCurrent = pHead;
    printf("自栈底打印元素: ");
    int l = getLength(pHead);
    int* data = (int*) malloc (l * sizeof(int)); 
    int i = 0;
    while (pCurrent -> next != NULL) {
        data[i ++] = pCurrent -> next -> data;
        pCurrent = pCurrent -> next;
    }
    for(i = 1; i <= l; i++)
        printf("%d ", data[l - i]);
    printf("\n");
    return true;
}

/**
 * @brief 销毁栈, 并释放栈空间
 * 
 * @param pStack
 */
void destoryStack(PNode pHead){
    destroyList(pHead);
}

int main(){
    printf("-----------------\n");
    PNode pHead = initailStack();
    push(pHead, 1);
    push(pHead, 4);
    pop(pHead);
    printStack(pHead);
    destoryStack(pHead);
    printf("-----------------");
    return 0;
}

共享栈

/**
 * @file shared_stack.c
 * @author xiaoxiao (you@domain.com)
 * @brief 共享栈
 * @version 0.1
 * @date 2022-03-06
 *
 * @copyright Copyright (c) 2022
 *
 */

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

#define MaxSize 20  // 总栈长

typedef struct Stack {
    int* pData;    // 数据
    int leftTop;   // 左栈顶(-1表示空栈, 0表示当前栈有一个元素)
    int rightTop;  // 右栈顶
} Stack;

typedef Stack* PStack;

/**
 * @brief 初始化一个栈
 *
 * @return PStack 栈指针
 */
PStack initailStack() {
    PStack pStack = (PStack)malloc(sizeof(PStack));
    if (pStack == NULL) {
        printf("no more momery");
        exit(1);
    }
    pStack->pData = (int*)malloc(MaxSize * sizeof(int));
    if (pStack->pData == NULL) {
        printf("no more momery");
        exit(1);
    }
    pStack->leftTop = -1;        // 左栈顶
    pStack->rightTop = MaxSize;  // 右栈顶
    return pStack;
}

/**
 * @brief 元素入栈
 *
 * @param pStack 栈指针
 * @param data 入栈元素,非负数就是向左入栈,负数就是向后入栈
 * @return true 入栈成功
 * @return false 入栈失败
 */
bool push(PStack pStack, int data) {
    if (pStack->leftTop + 1 == pStack->rightTop) {
        printf("栈已满, 无法进栈\n");
        return false;
    }
    if (data >= 0)
        pStack->pData[pStack->leftTop++ + 1] = data;
    else
        pStack->pData[pStack->rightTop-- - 1] = abs(data);
    return true;
}

/**
 * @brief 元素出栈
 *
 * @param pStack 栈指针
 * @param side 哪一侧的元素,true:左侧,false:右侧
 * @return int 出栈元素
 */
int pop(PStack pStack, bool side) {
    if (side) {
        if (pStack->leftTop == -1) {
            printf("空栈不能出栈\n");
            return -1;
        }
        return pStack->pData[pStack->leftTop--];
    } 
    else {
        if (pStack->rightTop == MaxSize) {
            printf("空栈不能出栈\n");
            return -1;
        }
        return pStack->pData[pStack->rightTop++];
    }
}

/**
 * @brief 打印栈中元素
 *
 * @param pStack 栈指针
 * @return true 非空栈,可以打印
 * @return false 不是空栈
 */
void printStack(PStack pStack) {
    if (pStack->leftTop == -1)
        printf("左栈为空,不能打印\n");
    else {
        printf("自左栈底打印元素: ");
        for (int i = 0; i <= pStack->leftTop; i++) {
            printf("%d ", pStack->pData[i]);
        }
        printf("\n");
    }
    if (pStack->rightTop == MaxSize)
        printf("右栈为空,不能打印\n");
    else {
        printf("自右栈底打印元素: ");
        for (int i = MaxSize - 1; i >= pStack->leftTop; i--) {
            printf("%d ", pStack->pData[i]);
        }
        printf("\n");
    }
}

/**
 * @brief 销毁栈, 并释放栈空间
 *
 * @param pStack
 */
void destoryStack(PStack pStack) {
    free(pStack->pData);
    free(pStack);
}

int main() {
    printf("--------------------\n");
    PStack pStack = initailStack();
    push(pStack, 1);
    push(pStack, -10);
    push(pStack, 4);
    printStack(pStack);
    destoryStack(pStack);
    printf("--------------------");
    return 0;
}