数据结构-栈

作者: 1江春水 | 来源:发表于2019-04-23 17:58 被阅读3次

栈和队列
004 go语言实现栈
java高级知识点
栈和堆以及栈区和堆区的区别
栈
2019-07-11—栈
什么是堆栈？
05--栈递归
18-04-21 python3 算法笔记 002基本数据结构
数据结构

栈

特性：后进先出 LIFO

基本概念

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

栈的基本运算

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

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

顺序存储

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

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;
    }
}