算法高薪算法+计算机职称考试数据结构与算法

数据结构-栈

2019-04-23  本文已影响3人  1江春水

特性:后进先出 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;
    }
}
顺序栈、链栈的比较
上一篇 下一篇

猜你喜欢

热点阅读