栈

stack.png

特性：后进先出 LIFO

基本概念

• 栈是运算受限的线性表，插入和删除限定在表的一端进行操作；
• 栈顶：允许插入删除的一端称为栈顶，另一端称为栈底；
• 栈顶元素：处于栈顶位置的元素称为栈顶元素；
• 空栈：不含任何数据元素的栈称为空栈；

栈的基本运算

1. 初始化：构造一个空栈
2. 判栈空
3. 进栈：将元素x插入栈中，使x成为栈顶元素
4. 出栈：删除栈顶元素
5. 取栈顶元素：返回栈顶元素

栈的顺序存储结构和链式存储结构

顺序存储

栈的顺序存储结构是使用一组连续的存储单元依次存放栈中的每个元素，并用始端作为栈底，称为顺序栈；通常使用一维数组和一个记录栈顶的变量来实现。

C语言实现

const int maxsize = 10;//最大栈容量
typedef struct {
    int top;
    int data[maxsize]; //数据类型为int
}SeqStack;


//初始化
SeqStack * initStack(void) {
    SeqStack *stack = (SeqStack *)malloc(sizeof(SeqStack));
    stack->top = 0;
    return stack;
}

//判栈空
int emptyStack(SeqStack *s) {
    if (s->top == 0) {
        return 1;
    }
    return 0;
}

//进栈
void push(SeqStack *s,int x) {
    if (s->top < maxsize-1) {
        s->data[s->top+1] = x;
        s->top++;
    } else {
        printf("栈已满");
    }
}

//出栈
void pop(SeqStack *s) {
    if (emptyStack(s)) {
        printf("已是空栈");
    } else {
        s->top--;
    }
}

//取栈顶元素
int getTop(SeqStack *s) {
    if (emptyStack(s)) {
        return -1;
    }
    return s->data[s->top];
}

OC实现

.h文件

@interface Stack : NSObject
- (void)push:(int)x;
- (void)pop;
- (int)getTop;
- (BOOL)emptyStack;
@end

.m文件

- (instancetype)init {
    self = [super init];
    if (self) {
        _data = [NSMutableArray array];
    }
    return self;
}

- (void)push:(int)x {
    NSNumber *n = [NSNumber numberWithInt:x];
    if (n) {
        [self.data addObject:n];
    }
}

- (void)pop {
    [self.data removeLastObject];
}

- (BOOL)emptyStack {
    if (self.data.count) {
        return NO;
    }
    return YES;
}

- (int)getTop {
    return [[self.data lastObject] intValue];
}

栈的链式存储

C语言实现

typedef struct node {
    int data;//数据类型
    struct node *next;
}LinkStack;

//初始化
LinkStack *initLinkStack() {
    LinkStack *ls = (LinkStack *)malloc(sizeof(LinkStack));
    ls->next = NULL;
    return ls;
}

//判空
int emptyStack(LinkStack *s) {
    if (s->next == NULL) {
        return 1;
    }
    return 0;
}
//进栈
void push(LinkStack *s,int x) {
    LinkStack *temp = (LinkStack *)malloc(sizeof(LinkStack));
    temp->data = x;
    temp->next = s->next;
    s->next = temp;
}

//出栈
void pop(LinkStack *s) {
    if (emptyStack(s)) {
        printf("空栈");
    } else {
        LinkStack *pre = s->next;
        s->next = pre->next;
        free(pre);
    }
}
//获取栈顶元素
int getTop(LinkStack *s) {
    if (!emptyStack(s)) {
        return s->next->data;
    }
    return -1;
}

简单应用-链表反转

void reverseList(linkList head) {
    LinkStack *stack = initLinkStack();
    Node *pre = head->next;
    while (pre != NULL) {
        push(stack, pre->data);
        pre = pre->next;
    }
    
    pre = head->next;
    while (!emptyStack(stack)) {
        pre->data = getTop(stack);
        pop(stack);
        pre = pre->next;
    }
}

顺序栈、链栈的比较

• 顺序栈需要提前指定栈的大小，链栈不需要
• 顺序栈有 上溢(数据个数超出了最大值) 和 下溢(空栈时出栈) 概念
• 链栈没有上溢限制
• 链栈不需要附加头结点