数据结构：栈(linked-stack & array-stack)

末蓝、 2022-08-08 05:23 65阅读 0赞

栈是一种特别的线性表。在栈中，只能在数据的一端（即栈顶）进行操作。最经典的解释这个策略的例子就是叠盘子。盘子只能一个一个不断放在之前的盘子堆上，拿盘子的时候也只能从上往下一个一个拿。这两个操作，在stack中分别对于push和pop，即压栈和出栈。这体现了栈的后进先出(LIFO)特性。

![栈][20160417121546266]

![压栈（push）][push]

![出栈（pop）][pop]

# 2. 栈的实现 #

stack的实现分为两种，一种是使用数组来模拟栈，另外一种是使用链表来模拟栈。

## 2 .1 数组实现（array stack） ##

首先，先来看使用数组的方法。

栈的结构为
    #define MAX_SIZE 20 //栈内最多有几个元素
    typedef int StackEntry;
    typedef struct stack {
          StackEntry entry[MAX_SIZE];
          int top; 
    } Stack ;

用数组实现的栈使用连续的内存地址，为了能够知道栈顶位置，需要使用一个变量标记。

看起来，数组的实现方式十分的简单！So easy！当向栈中压入数据时，需要将top的值加1；出栈时，top的值减1。Too young，too naive！考虑两个极端的情况：在栈满时压栈，在栈空时出栈。因此在进行push和pop操作之前需要检查栈的情况，避免溢出。

int IsFull(Stack *s) {
        return (s->top >= MAX_SIZE);
     }
    
     int IsEmpty(Stack *s) {
        return (s->top <= 0);
     }
    
    void Push(StackEntry item, Stack* s) {
      if（IsFull(s)）
        return;
      else
        s->entry[s->top++] = item;
    }
    
    void Pop(Stack* s) {
       if(IsEmpty(s)）
          return;
       else
          s->top--;
    }
    
    StackEntry Top(Stack* s) {
       if(!IsEmpty(s)）
          return s->entry[s->top-1];
       else 
          return -1;
    }

## 2.2. 链式实现（linked stack） ##

链式栈使用链表的存储形式实现，其存储是不连续的。我们首先定义stack的结构如下：

typedef struct node {
      StackEntry val;
      struct node *next;
    } Node;

一般来说，很多人会自然而然的想到在stack中将心的元素加入到linked stack的末尾。但是要考虑到，对于stack，我们经常在其末尾进行操作，如果将元素插入到link的末尾，那么每次操作都要先从头到达末尾才能操作，所以我们需要换另外一种方法，采用前插的方式，将新的元素插入到列表的前面。这样每次进行push和pop操作的时候就可以直接通过top指针操作。

![后插][20160417124953076]

![前插][20160417125013529]

//push a new node onto the top of the stack (the front of the list),
    //and return whether successful
    int Push (int val, Node* stack) {
    
        Node* addNode = (Node*)malloc(sizeof(Node));
    
        if (addNode == NULL) {
            printf("out of memory!\n");
            return 0;
        }
    
        addNode->val = val;
        addNode->next = stack->next;
        stack->next = addNode;
    
        return 1;
    }
    
    
    //pop the top node from the stack
    int Pop (Node* stack) {
    
        if (IsEmpty(stack)) {
            printf("the stack is empty!\n");
            return 0;
        }
    
        Node *tmpNode = stack->next;
        stack->next = tmpNode->next;
        free(tmpNode);
    
        return 1;
    }
    
    
    //check whether the stack is empty
    int IsEmpty (Node* stack) {
    
        return (stack->next == NULL);
    }
    
    
    //get the top value of the stack
    int Top (Node* stack) {
    
        if (IsEmpty(stack)) {
            printf("the stack is empty!\n");
            return -1;
        }
    
        return (stack->next->val);
    }

综合所有操作

### 数组实现 ###

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAX_SIZE 20 //栈内最多有几个元素
    
    typedef int StackEntry;
    typedef struct stack {
          StackEntry entry[MAX_SIZE];
          int top;
    } Stack;
    
    int IsFull(Stack *s) {
        return (s->top >= MAX_SIZE);
     }
    
    int IsEmpty(Stack *s) {
        return (s->top <= 0);
     }
    
    void Push(StackEntry item, Stack* s) {
      if (IsFull(s))
        return;
      else
        s->entry[s->top++] = item;
    }
    
    void Pop(Stack* s) {
       if (IsEmpty(s))
          return;
       else
          s->top--;
    }
    
    StackEntry Top(Stack* s) {
       if (!IsEmpty(s))
          return s->entry[s->top-1];
            else
                return -1;
    }
    
    int main () {
    
        Stack *s = (Stack*)malloc(sizeof(Stack));
        s->top = 0;
    
        Push(1, s);
    
        Push(2, s);
    
        Push(3, s);
    
        //get 3
        int temp = Top(s);
        printf("%d ", temp);
    
        //pop 3
        Pop(s);
        temp = Top(s);
        printf("%d ", temp);
    
        Push(4, s);
        temp = Top(s);
        printf("%d ", temp);
    
        //pop 4
        Pop(s);
        temp = Top(s); // top is 2
        printf("%d ", temp);
    
        //pop 2
        Pop(s);
        temp = Top(s); //top is 1
        printf("%d ", temp);
    
        //pop 1
        Pop(s);
        temp = Top(s); //error get top element from empty stack
        printf("%d ", temp);
    
        return 0;
    }

> 输出：3 2 4 2 1 -1

### 链式实现 ###

#include <stdio.h>
    #include <stdlib.h>
    
    
    typedef struct node
    {
        int val;
        struct node *next;
    } Node;
    
    
    Node* CreateEmptyStack ();
    int Push (int val, Node* stack);
    int Pop (Node* stack);
    int IsEmpty (Node* stack);
    int Top (Node* stack);
    
    
    int main () {
    
        Node *s = CreateEmptyStack();
    
        Push(1, s);
    
        Push(2, s);
    
        Push(3, s);
    
        int temp = Top(s); //top is 3
        printf("%d ", temp);
    
        Pop(s); //pop 3
        temp = Top(s); //top is 2
        printf("%d ", temp);
    
        Push(4, s);
        temp = Top(s); //top is 4
        printf("%d ", temp);
    
        Pop(s); //pop 4
        temp = Top(s); //top is 2
        printf("%d ", temp);
    
        Pop(s); //pop 2
        temp = Top(s); //top is 1
        printf("%d ", temp);
    
        Pop(s); //pop 1
        temp = Top(s); //error, get top element from empty stack
        printf("%d ", temp);
    
    
    
    
    
        return 0;
    }
    
    
    //create a empty stack and return the address
    Node* CreateEmptyStack () {
    
        Node* stack = (Node*)malloc(sizeof(Node));
    
        if (stack == NULL) {
            printf("out of memory!\n");
            return NULL;
        }
    
        stack->val = 0;
        stack->next = NULL;
    
        return stack;
    }
    
    
    //push a new node onto the top of the stack (the front of the list),
    //and return whether successful
    int Push (int val, Node* stack) {
    
        Node* addNode = (Node*)malloc(sizeof(Node));
    
        if (addNode == NULL) {
            printf("out of memory!\n");
            return 0;
        }
    
        addNode->val = val;
        addNode->next = stack->next;
        stack->next = addNode;
    
        return 1;
    }
    
    
    //pop the top node from the stack
    int Pop (Node* stack) {
    
        if (IsEmpty(stack)) {
            printf("the stack is empty!\n");
            return 0;
        }
    
        Node *tmpNode = stack->next;
        stack->next = tmpNode->next;
        free(tmpNode);
    
        return 1;
    }
    
    
    //check whether the stack is empty
    int IsEmpty (Node* stack) {
    
        return (stack->next == NULL);
    }
    
    
    //get the top value of the stack
    int Top (Node* stack) {
    
        if (IsEmpty(stack)) {
            printf("the stack is empty!\n");
            return -1;
        }
    
        return (stack->next->val);
    }

> 输出：3 2 4 2 1 the stack is empty!  
> \-1

[20160417121546266]: /images/20220805/072ed05f74d24eb79fc31a1847ffd2a5.png
[push]: /images/20220805/2888b9cb849944989b348c5f87dbcf89.png
[pop]: /images/20220805/0da807b0a96f426d8d2c8b79e10fa985.png
[20160417124953076]: /images/20220805/e301b144d9c74ac4adde5b534112e918.png
[20160417125013529]: /images/20220805/bc154c8995b840f39395df5f361f1059.png