栈
定义
栈：只能在表的一端（栈顶）进行插入和删除运算的线性表
逻辑结构： 与线性表相同，任然是一对一关系
存储结构： 用顺序栈或链栈存储都可以。
运算规则： 只能在栈顶运算，且访问结点时依照后进先出或者先进后出的原则。
实现方式： 关键是编写入栈和出栈的函数。
顺序栈的表示：
#define MAXSIZE 100
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
// 初始化
Status InitStack( SqStack &S ){
S.base =new SElemType[MAXSIZE]；
if( !S.base ) return OVERFLOW;
S.top = S.base;
S.stackSize = MAXSIZE;
return OK;
}
// 顺序栈是否为空
bool StackEmpty( SqStack S ){
if(S.top == S.base) return true;
else return false;
}
// 顺序栈的长度
int StackLength( SqStack S ){
return S.top – S.base;
}
// 清空顺序栈
Status ClearStack( SqStack S ){
if( S.base ) S.top = S.base;
return OK;
}
// 销毁顺序栈
Status DestroyStack( SqStack &S ){
if( S.base )
{
delete S.base ;
S.stacksize = 0;
S.base = S.top = NULL;
}
return OK;
}
// 顺序栈进站
// (1)判断是否栈满，若满则出错
// (2)元素e压入栈顶
// (3)栈顶指针加1
Status Push( SqStack &S, SElemType e){
if( S.top - S.base== S.stacksize ) // 栈满
return ERROR;
*S.top++=e;
return OK;
}
// 顺序进站
// (1)判断是否栈空，若空则出错
// (2)获取栈顶元素e
// (3)栈顶指针减1
Status Pop( SqStack &S, SElemType &e)
{
if( S.top == S.base ) // 栈空
return ERROR;
e＝ *--S.top;
return OK;
}
// 取顺序栈栈顶元素
// 判断是否空栈，若空则返回错误
// 否则通过栈顶指针获取栈顶元素
Status GetTop( SqStack S, SElemType &e) {
if( S.top == S.base ) return ERROR; // 栈空
e = *( S.top – 1 );
return OK;
}
顺序栈的操作
c语言
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct Stack{
int *data; // 数据
int capacity;// 最大容量
int top;// 栈顶
};
// 判断栈满
int isFull(const struct Stack *ps){
// 满就是top是否与capacity相同
return ps->top == ps->capacity;
}
// 判断栈空
int isEmpty(const struct Stack *ps){
// top为0是空栈
return ps->top == 0;
}
//
int top(const struct Stack *ps){
if(isEmpty(ps)) return 0;
else{
*ps = ps->data[--(ps->top-1)];
return 1;
}
}
// init
void init(struct Stack *ps,int capacity){
ps->capacity = capacity; // 初始化容量
ps->data = (int *)malloc( sizeof(capacity));
// ps->top = -1; // 总是指向最高元素
ps->top = 0; // 总是指向最高元素的上面的空格
}
// 压栈
int push(struct Stack *ps, int x){
// 判断栈满
if(isFull(ps)) return 0;
else{
// 进行压栈
ps->data[ps->top++]=x;
return 1;
}
}
// 弹栈
int pop(struct Stack *ps, int x){
if(isEmpty(ps)) return 0;
else{
*ps = ps->data[--(ps->top)];
return 1;
}
}
// 销毁
void destory(struct *ps){
free(ps->data);
}
int main(void) {
struct Stack st;
init(&st，5); // 改变st的内容，所以需要st地址 &st
push(&st, 11); // 压栈
push(&st, 121); // 压栈
push(&st, 111); // 压栈
push(&st, 131); // 压栈
int x;
pop(&st, &x); // 弹栈 并把弹出的数据返回
destory(&st);
return 0;
}
C++
#include <iostream>
#include <stack>
using namespace std;
int main(int argc,const char * args[]){
stack<int> st;
st.push(11);
st.push(12);
int x = st.top();
st.pop()//弹栈
st.empty();
cout << st.size() << endl;
return 0;
}
java
public class ArrayStackDemo {
public static void main(String[] args) {
//测试
ArrayStack stack =new ArrayStack(4);
String key="";
boolean loop = true;
Scanner scanner = new Scanner(System.in);
while(loop) {
System.out.println("show:表示显示栈");
System.out.println("exit:退出程序");
System.out.println("push:表示添加数据到栈（入栈）");
System.out.println("pop:表示从栈取出数据（出栈）");
System.out.println("请输入你的选择");
key = scanner.next();
switch(key) {
case "show":
stack.list();
break;
case "push":
System.out.println("请输入一个数");
int value = scanner.nextInt();
stack.push(value);
break;
case "pop":
try {
int res = stack.pop();
System.out.printf("出栈的语句是%d\n", res);
}catch(Exception e) {
System.out.println(e.getMessage());
}
break;
case "exit":
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出");
}
}
class ArrayStack{
private int maxSize;
private int[] stack;
private int top = -1;
public ArrayStack(int maxSize) {
this.maxSize=maxSize;
stack = new int[this.maxSize];
}
//栈满
public boolean isFull() {
return top == maxSize -1;
}
//栈空
public boolean isEmpty() {
return top == -1;
}
//出栈
public void push(int value) {
if(isFull()) {
System.out.println("栈满");
}
top++;
stack[top] =value;
}
//出栈
public int pop() {
if(isEmpty()) {
throw new RuntimeException("栈空");
}
int value = stack[top];
top--;
return value;
}
//遍历栈
public void list() {
if(isEmpty()) {
System.out.println("栈空，没有数据");
return;
}
for(int i = top;i>=0;i--) {
System.out.printf("stack[%d]=%d\n",i,stack[i]);
}
}
python
st = list()
st.append(11)
st.append(22)
st.append(33)
x = st.pop(1) // 弹出1号元素
st.pop() // 弹出最后一个进栈的
后缀式求值
后缀式 3 5 2 1 - * + 思路 就是需要一个栈
class Solution:
def cal(x,y,op):
if op=='+':
return x+y
elif op == '-':
return x-y
elif op == '*':
return x*y
elif op == '/':
return x/y
def evalRPN(self, tokens: List[str]) -> int:
"""
:type tokens: List[str]
:rtype: int
"""
for i in tokens:
if i in '+-*/':
b = tokens.pop()
a = tokens.pop()
tokens.append(cal(a,b,i))
else:
tokens.append(float(i))
print('%.1f' % tokens.pop())
class Solution {
public int evalRPN(String[] tokens) {
String operators = "+-*/";
Stack<Object> stack = new Stack<>();
for(int i=0;i<tokens.length;i++){
String op = tokens[i];//取出一个操作
if(operators.contains(op)){
//如果是操作符
int n2 = (int) stack.pop();
int n1 = (int) stack.pop();
int value = 0;
switch (op){
case "+":value = n1 + n2;break;
case "-":value = n1 - n2;break;
case "*":value = n1 * n2;break;
case "/":value = n1 / n2;
}
stack.push(value);//把值送入栈
}
else {
//如果是操作数
stack.push(Integer.valueOf(op));//操作数入栈
}
}
return (int) stack.pop();//最后栈顶的操作数就是运算结果了
}
}
转载：https://blog.csdn.net/qq_37256896/article/details/117067980
查看评论