栈的设计与实现

什么是栈

栈（Stack）是一种特殊的线性表，它只能在表尾进行插入和删除操作，就像下面这样：

我们一般只在一端进行插入和删除，依次插入1，2，3，4后，如果进行删除操作，将会是4，3，2，1的顺序进行删除：

底部称为栈底，顶部成为栈顶，所有操作只能在栈顶进行，先进后出，下面的元素想要进行操作需要让上面的元素先出去
接着我们要来讲下栈的两个操作：

• pop：出栈操作，从栈顶取出一个元素。
• push：入栈操作，向栈中压入一个新的元素。
  我们先按照顺序表(也可以用链表)来编写：

typedef int E;

struct Stack {
    E * array;
    int capacity;
    int top;   //这里使用top来表示当前的栈顶位置，存的是栈顶元素的下标
};

typedef struct Stack * ArrayStack;  //起个别名

接着我们需要一个初始化方法：

_Bool initStack(ArrayStack stack){
    stack->array = malloc(sizeof(E) * 10);
    if(stack->array == NULL) return 0;
    stack->capacity = 10;   //容量还是10
    stack->top = -1;   //由于栈内没有元素，那么栈顶默认就为-1
    return 1;
}

int main(){
    struct Stack stack;
    initStack(&stack);
}

顺序栈的操作：

入栈操作

_Bool pushStack(ArrayStack stack, E element){
    //入栈操作只需要给元素就可以，不需要index，因为只能从尾部入栈
}

入栈只能在尾部插入：

_Bool pushStack(ArrayStack stack, E element){
    stack->array[stack->top + 1] = element;   //直接设定栈顶元素
    stack->top++;   //栈顶top变量记得自增
    return 1;
}

打印栈中元素:

void printStack(ArrayStack stack){ 
	printf("| ");
	for (int i = 0; i < stack->top + 1; ++i) {
		printf("%d, ", stack->array[i]);
	}
	 printf("\n"); 
}

但是我们此时此刻要面临着一个问题，就是该顺序栈可能会被塞满，所以我们可以添加扩容操作:

_Bool pushStack(ArrayStack stack, E element){
    if(stack->top + 1 == stack->capacity) {  //栈顶+1如果等于容量的话，那么说明已经塞满了
        int newCapacity = stack->capacity + (stack->capacity >> 1);   //大体操作和顺序表一致
        E * newArray = realloc(stack->array, newCapacity * sizeof(E));
        if(newArray == NULL) return 0;
        stack->array = newArray;
        stack->capacity = newCapacity;
    }
    stack->array[stack->top + 1] = element;
    stack->top++;
    return 1;
}

出栈操作

出栈操作比较简单，只需要输出当前栈顶元素即可;

_Bool isEmpty(ArrayStack stack){   //在出栈之前，我们还需要使用isEmpty判断一下栈是否为空，空栈元素都没有出个毛
    return stack->top == -1;   
}

E popStack(ArrayStack stack){
    return stack->array[stack->top--];   //直接返回栈顶元素，注意多加一个自减操作
}

单链栈的操作

前面我们演示了使用顺序表实现栈，我们接着来看如何使用链表来实现栈，实际上使用链表会更加的方便，我们可以直接将头结点指向栈顶结点，而栈顶结点连接后续的栈内结点：

typedef int E;

struct ListNode {
    E element;
    struct ListNode * next;
};

typedef struct ListNode * Node;

void initStack(Node head){
    head->next = NULL;
}

int main(){
    struct ListNode head;
    initStack(&head);
}

入栈操作

当有新的元素入栈，只需要在链表头部插入新的结点即可，我们来尝试编写一下
接着我们来编写一下入栈操作：

_Bool pushStack(Node head, E element){
    Node node = malloc(sizeof(struct ListNode));   //创建新的结点
    if(node == NULL) return 0;   //失败就返回0
    node->next = head->next;   //将当前结点的下一个设定为头结点的下一个
    node->element = element;   //设置元素
    head->next = node;   //将头结点的下一个设定为当前结点
    return 1;
}

出栈操作

同理得，移除第一个结点：

_Bool isEmpty(Node head){
    return head->next == NULL;   //判断栈是否为空只需要看头结点下一个是否为NULL即可
}

E popStack(Node head){
    Node top = head->next;
    head->next = head->next->next;
    E e = top->element;
    free(top);  //别忘了释放结点的内存
    return e;   //返回出栈元素
}