C++栈顺序和链式实现及操作

顺序栈

#include<bits/stdc++.h>
typedef int Status;
typedef int SElemType;
#define OVERFLOW -1
#define ERROR 0
#define OK 1
#define MAXSIZE 100

using namespace std;
/**

顺序栈

顺序栈的基本操作：初始化、入栈、出栈、取栈顶元素
/

/* 顺序栈的存储形式 */
typedef struct {
    SElemType *base;
    SElemType *top;
    int stacksize;
} SqStack;
/* 初始化 */
Status InitSqStack(SqStack &stack) {
    // 为栈分配容量
    stack.base = new int[MAXSIZE];
    // 分配失败返回失败值
    if (!stack.base) {
        return OVERFLOW;
    }
    // 让栈顶地址初始为栈底地址
    stack.top = stack.base;
    // 初始化容量
    stack.stacksize = MAXSIZE;
    return OK;
}
/* 入栈 */
Status Push(SqStack &stack, SElemType e) {
    if (stack.top - stack.base == stack.stacksize) {
        return OVERFLOW;
    }
    *stack.top = e; // 先在top位置赋值
    stack.top++; // 将top地址++
    return OK;
}
/* 出栈 */
Status Pop(SqStack &stack) {
    // 空栈返回异常
    if (stack.top == stack.base) {
        return OVERFLOW;
    }
    stack.top–; // 栈顶地址减1
    return *stack.top; // 返回此时“栈顶”元素
}
/* 取栈顶元素 */
Status GetTop (SqStack &stack) {
    // 空栈返回异常
    if (stack.top == stack.base) {
        return OVERFLOW;
    }
    // stack.top–; // 栈顶地址减1，这是和出栈的区别
    return *(stack.top-1); // 返回此时“栈顶”元素
}
int main() {
    SqStack test;
    InitSqStack(test);
    Push(test, 10);
    Push(test, 15);
    Push(test, 20);
    cout << GetTop(test)<<" "<< GetTop(test)<<" "<< GetTop(test)<<" "<<"\n";
    cout << Pop(test)<<" "<< Pop(test)<<" "<< Pop(test)<<" "<<"\n";
}

链栈

#include<bits/stdc++.h>
typedef int Status;
typedef int SElemType;
#define OVERFLOW -1
#define ERROR 0
#define OK 1
#define MAXSIZE 100

using namespace std;
/**

链栈

链栈的基本操作：初始化、入栈、出栈、取栈顶元素
/

/* 链栈的存储形式 */
typedef struct StackNode{
    SElemType data;
    struct StackNode *next;
} StackNode, *LinkStack;
/**

初始化
不设头结点
/
Status InitLinkStack(LinkStack &stack) {
  stack = NULL; // 栈顶元素置空
  return OK;
}

/* 入栈 */
Status Push(LinkStack &stack, SElemType e) {
    // 不能用LinkStack这样声明结点变量，需要new一个内存空间
    LinkStack temp = new StackNode;
    temp->data = e;
    temp->next = stack;
    stack = temp;
    return OK;
}
/* 出栈 */
Status Pop (LinkStack &stack) {
    SElemType i = stack->data;
    stack = stack->next;
    return i;
}
/* 取栈顶元素 */
Status GetTop (LinkStack &stack) {
    return stack->data;
}
int main() {
    LinkStack test;
    InitLinkStack(test);
    Push(test, 10);
    Push(test, 15);
    Push(test, 20);
    cout << GetTop(test)<<" "<< GetTop(test)<<" "<< GetTop(test)<<" "<<"\n";
    cout << Pop(test)<<" "<< Pop(test)<<" "<< Pop(test)<<" "<<"\n";
}