算法与数据结构系列之[栈]

栈是一种限定仅在表尾进行插入和删除操作的线性表，其最大的特点就是后进先出(Last In First Out),简称LIFO结构。栈可以用动态数组实现，也可以使用链表实现。由于栈比较简单，这里不再详述，仅贴出代码。
C语言代码：
1.Stack.c

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

#define STACK_INIT_SIZE 100   //初始分配的存储空间大小
#define INCREMENT 10     //存储空间分配增量
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0

typedef int SElemType;
typedef int Status;

//顺序栈的实现
typedef struct{
    SElemType *data;  //声明了一个名为data的长度不确定的数组，也叫“动态数组”
    int top;  //用于栈顶指针
    int size;  //栈空间大小  用于语义明确
}Stack;

/**
* 初始化顺序栈
* @param S
* @return OK
*/
Status InitStack(Stack *S){
    S->data =(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if(!S->data) exit(-1);
    S->top = -1;  //表示空栈
    S->size = 0;
    return OK;
}

/**
* 获取栈的大小
* @return size
*/
int GetSize(Stack stack){
    return stack.size;
}

/**
* 判断是否为空栈
* @param stack
* @return
*/
int IsEmpty(Stack stack){
    if(stack.size == 0)
        return TRUE;
    return FALSE;
}

/**
* 获取栈顶元素
* @param stack
* @return
*/
int Peek(Stack stack){
    if(IsEmpty(stack))
        return ERROR;
    return stack.data[stack.top];
}

/**
* 入栈
* @param S
* @param e
* @return
*/
Status Push(Stack *S,SElemType e){
    if(S->size == STACK_INIT_SIZE)  //栈已满，扩容
        S->data =(SElemType *)realloc(S->data,(S->size + INCREMENT) * sizeof(SElemType));
    S->top++;
    S->data[S->top] = e;
    S->size++;
    return OK;
}

/**
* 出栈
* @param S
* @param e
* @return
*/
Status Pop(Stack *S,SElemType *e){
    if(S->size == 0) //空栈
        return ERROR;
    *e = S->data[S->top];
    S->top--;
    S->size--;
    return OK;
}

/**
* 遍历并打印输出顺序栈的元素
* @param stack
*/
void DisplayStack(Stack stack){
    if(IsEmpty(stack))
        printf("该栈为空");
    for (int i = 0; i < stack.size; ++i) {
        printf("%d ",stack.data[i]);
    }
    printf("\n");
}

//链栈的实现
typedef struct StackNode{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStackPtr;


typedef struct LinkStack{
    LinkStackPtr top;
    int size;
}LinkStack;

/**
* 初始化链栈
* @param L
* @return
*/
Status InitLinkStack(LinkStack *L){
    L->top = (LinkStackPtr)malloc(sizeof(StackNode));
    //L = (LinkStack *) malloc(sizeof(LinkStack));
    L->top = NULL;
    L->size = 0;
}

/**
* 获取链栈的长度
* @param linkStack
* @return
*/
int GetLinkStackSize(LinkStack linkStack){
    return linkStack.size;
}

/**
* 判断链栈是否为空
* @param linkStack
* @return
*/
int IsLinkStackEmpty(LinkStack linkStack){
    if(linkStack.size == 0)
        return TRUE;
    return FALSE;
}

/**
* 链栈入栈
* @param L
* @param e
* @return
*/
Status PushLinkStack(LinkStack *L,SElemType e){
    LinkStackPtr  s =(LinkStackPtr) malloc(sizeof(StackNode));
    s->data = e;
    s->next = L->top;
    L->top = s;
    L->size++;
    return OK;
}

/**
* 链栈出栈
* @param L
* @param e
* @return
*/
Status PopLinkStack(LinkStack *L,SElemType *e){
    LinkStackPtr  p;
    if(IsLinkStackEmpty(*L))
        return ERROR;
    *e = L->top->data;
    p = L->top;
    L->top = L->top->next;
    free(p);
    L->size--;
    return OK;
}

/**
* 获取链栈的栈顶元素
* @param linkStack
* @return
*/
int PeekLinkStack(LinkStack linkStack){
    return linkStack.top->data;
}

/**
* 遍历链栈的所有元素
* @param stack
*/
void DisplayLinkStack(LinkStack stack){
    if(IsLinkStackEmpty(stack))
        printf("该栈为空");
    while (stack.top){
        printf("%d",stack.top->data);
        stack.top = stack.top->next;
    }
    printf("\n");
}

2.Stack.h

#ifndef TEST_STACK_H
#define TEST_STACK_H


#define STACK_INIT_SIZE 100   //初始分配的存储空间大小
#define INCREMENT 10     //存储空间分配增量
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0

typedef int SElemType;
typedef int Status;

//顺序栈的实现
typedef struct{
    SElemType *data;  //声明了一个名为data的长度不确定的数组，也叫“动态数组”
    int top;  //用于栈顶指针
    int size;  //栈空间大小  用于语义明确
}Stack;

//初始化顺序栈
Status InitStack(Stack *S);
//获取栈的大小
int GetSize(Stack stack);
//判断栈是否为空
int IsEmpty(Stack stack);
//获取栈顶元素
int Peek(Stack stack);
//入栈
Status Push(Stack *S,SElemType e);
//出栈
Status Pop(Stack *S,SElemType *e);
//遍历并打印输出顺序栈的元素
void DisplayStack(Stack stack);

//链栈的实现
typedef struct StackNode{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStackPtr;

typedef struct LinkStack{
    LinkStackPtr top;
    int size;
}LinkStack;

//初始化一个链栈
Status InitLinkStack(LinkStack *L);
//获取链栈长度
int GetLinkStackSize(LinkStack linkStack);
//判断链栈是否为空
int IsLinkStackEmpty(LinkStack linkStack);
//链栈入栈
Status PushLinkStack(LinkStack *L,SElemType e);
//链栈出栈
Status PopLinkStack(LinkStack *L,SElemType *e);
//获取链栈栈顶元素
int PeekLinkStack(LinkStack linkStack);
//遍历并打印输出链栈的元素
void DisplayLinkStack(LinkStack stack);

3.main.c

//顺序栈
//初始化一个空栈
Stack stack;
InitStack(&stack);
DisplayStack(stack);
//入栈操作
Push(&stack,6);
Push(&stack,7);
Push(&stack,8);
DisplayStack(stack);
//打印栈的长度
printf("%d",GetSize(stack));
printf("\n");
//判断该栈是否为空
printf("%d",IsEmpty(stack));
printf("\n");
//获取栈顶元素
printf("%d",Peek(stack));
printf("\n");
//出栈
int num;
int *n = #
Pop(&stack,n);
DisplayStack(stack);
printf("------------------------------------------");

//链栈
//初始化一个链栈
LinkStack linkStack;
InitLinkStack(&linkStack);
printf("\n");
DisplayLinkStack(linkStack);
//入栈操作
PushLinkStack(&linkStack,4);
PushLinkStack(&linkStack,5);
PushLinkStack(&linkStack,6);
DisplayLinkStack(linkStack);
//打印链栈长度
printf("%d",GetLinkStackSize(linkStack));
printf("\n");
//打印链栈栈顶元素
printf("%d",PeekLinkStack(linkStack));
printf("\n");
//入栈
PushLinkStack(&linkStack,7);
DisplayLinkStack(linkStack);
//出栈
int element;
int *e = &element;
PopLinkStack(&linkStack,e);
DisplayLinkStack(linkStack);

4.运行结果：

该栈为空
6 7 8
3
0
8
6 7
------------------------------------------
该栈为空
654
3
6
7654
654

java代码：
1.Stack.java

public interface Stack<E> {
    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peek();
}

2.ArrayStack.java

/**
* 用动态数组实现栈
* @param <E>
*/
public class ArrayStack<E> implements Stack<E> {


    private Array<E> array; //声明数组


    public ArrayStack(int capacity){
        array = new Array<>(capacity);
    }


    public ArrayStack(){
        array = new Array<>();
    }
    //获取栈的大小
    @Override
    public int getSize() {
        return array.getSize();
    }
    //判断栈是否为空
    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }
    //入栈
    @Override
    public void push(E e) {
        array.add(e);
    }
    //出栈
    @Override
    public E pop() {
        return array.remove(array.getSize()-1);
    }
    //查看栈顶元素
    @Override
    public E peek() {
        return array.get(array.getSize()-1);
    }


    @Override
    public String toString() {
       StringBuilder res = new StringBuilder();
       res.append("Stack: ");
       res.append("[");
        for (int i = 0; i <array.getSize() ; i++) {
            res.append(array.get(i));
            if(i != array.getSize()-1){
                res.append(",");
            }
        }
        res.append("]");
        return res.toString();
    }


    public static void main(String[] args) {
        ArrayStack<Integer> stack = new ArrayStack<>();
        for (int i = 0; i < 5; i++) {
            stack.push(i);
            System.out.println(stack);
        }
        stack.pop();
        System.out.println(stack);
    }
}

3.LinkedListStack.java

public class LinkedListStack<E> implements Stack<E> {
    private LinkedList<E> linkedList;

    public LinkedListStack(){
        linkedList = new LinkedList<>();
    }

    @Override
    public int getSize() {
        return linkedList.getSize();
    }

    @Override
    public boolean isEmpty() {
        return linkedList.isEmpty();
    }

    @Override
    public void push(E e) {
        linkedList.addFirst(e);
    }

    @Override
    public E pop() {
        return linkedList.removeFirst();
    }

    @Override
    public E peek() {
        return linkedList.getFirst();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Stack top  ");
        res.append(linkedList);
        return res.toString();
    }

    public static void main(String[] args) {
        LinkedListStack<Integer> stack = new LinkedListStack<>();
        for (int i = 0; i < 5; i++) {
            stack.push(i);
            System.out.println(stack);
        }
        stack.pop();
        System.out.println(stack);

    }
}