栈

栈

栈是一种特殊的线性表,其插入和删除操作只允许在线性表的一端进行,允许操作的一端称为栈顶,不允许操作的一端称为栈底, 后进先出,就像一摞盘子,每次将一个个盘子摞在最上边或者从最上面取一只盘子,不能从中间插入或抽出

顺序栈

采用顺序存储结构的栈称为顺序栈

顺序栈的定义

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */
typedef struct {
    SElemType data[MAXSIZE];
    int top
}Stack;

初始化空顺序栈

Status initStack(Stack *S){
    S->top = -1;
    return OK;
}

清空顺序栈

Status clearStack(Stack *S){
    S->top = -1;
    return OK;
}

顺序栈是否为空

Status stackEmpty(Stack S){
    if (S.top == -1)
        return TRUE;
    else
        return FALSE;
}

返回顺序栈长度

int stackLength(Stack S){
    return S.top + 1;
}

获取顺序栈顶元素

Status getTop(Stack S,SElemType *e){
    if (S.top == -1)
        return ERROR;
    else
        *e = S.data[S.top];
   
    return OK;
    
}

顺序栈插入元素

插入元素e为新栈顶元素
Status pushData(Stack *S, SElemType e){

//栈已满
if (S->top == MAXSIZE -1) {
    return ERROR;
}

//栈顶指针+1;
S->top ++;
//将新插入的元素赋值给栈顶空间
S->data[S->top] = e;

return OK;

}

删除顺序栈顶元素

删除S栈顶元素,并且用e带回
Status pop(Stack *S,SElemType *e){

//空栈,则返回error;
if (S->top == -1) {
    return ERROR;
}

//将要删除的栈顶元素赋值给e
*e = S->data[S->top];
//栈顶指针--;
S->top--;

return OK;

}

顺序栈的遍历

Status stackTraverse(Stack S){
    int i = 0;
    printf("此栈中所有元素");
    while (i<=S.top) {
        printf("%d ",S.data[i++]);
    }
    printf("\n");
    return OK;
}

链式栈

采用链式存储结构的栈称为链式栈,采用单链表实现

定义

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */
typedef struct{
    SElemType data;
    struct StackNode *next;
}StackNode;
typedef StackNode* ListStackPtr;

typedef struct {
    ListStackPtr top;
    int count;
}ListStack;

链式栈初始化

Status initStack(ListStack *S){
    S->top = NULL;
    S->count = 0;
    return OK;
}

链式栈清空

Status clearStack(ListStack *S){
    ListStackPtr p = S->top;
    ListStackPtr temp;
    while (p) {
        temp = p;
        p = temp->next;
        free(temp);
        
    }
    S->count = 0;
    return OK;
}

链式栈是否为空

Status isEmpty(ListStack S){
    return S.count == 0 ? TRUE : FALSE;
}

链式栈长度

int stackLength(ListStack S){
    return S.count;
}

获取栈顶元素

Status getTop(ListStack *S,SElemType *e){
    if (S.top == NULL) {
        return ERROR;
    }else{
        *e = S.top->data;
    }
    return OK;
}

插入元素

Status push(ListStack *S,SElemType e){
    ListStackPtr temp = malloc(sizeof(StackNode));
    temp->data = e;
    temp->next = S->top;
    S->top = temp;
    S->count++;
    return OK;
}

删除元素

Status pop(ListStack *S, SElemType e){
    ListStackPtr temp;
    if (S->count == 0) {
        return ERROR;
    }
    *e = S->top->data;
    temp = S->top;
    S->top = temp->next;
    free(temp);
    S->count--;
    return OK;
}

遍历链式栈

Status travelStack(ListStack S){
    ListStackPtr temp;
    temp = S.top;
    while (temp) {
        printf(temp->data);.
        printf("\n");
        temp = temp->next;
    }
    return OK;
}