栈 数组和链表实现

stack 栈

LIFO后进先出

应用

实现递归 编辑器的撤回工作（按下ctrl z）

数组实现

// 列表的插入和删除从一端实现 那么就得到了栈
// array和linked lists//stack-Array based implementation
#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 101
int A[MAX_SIZE];
int top = -1;//空栈//插入push
void Push(int x)
{if (top == MAX_SIZE - 1){printf("Error:stack overflow\n");}A[++top] = x;
}// O（1）未溢出  
// O（n）当栈满的时候 可以要创建一个两倍的大小，并且把该栈复制到新栈
//此处若栈满未进行创建一个两倍的大小void pop()
{if (top == -1)//栈满{printf("Error:No element to pop\n");return;}top--;
}int Isempty()
{if (top == -1)return 1;return 0;
}
//Top返回栈顶元素
int Top()
{return A[top];
}void Print()
{printf("Stack:");for (int i = 0; i <= top; i++){printf("%d ", A[i]);}printf("\n");
}int main(void)
{Push(2);Push(4);Print();pop(); Print();Push(99); Push(99); pop(); Print();return 0;
}

链表实现

#include<stdlib.h>
#include<stdio.h>
//Stack Linned List implenmentation
//如果把尾部当成栈顶，尾插比较浪费时间O(N)，总是要先到达尾部
//头插 常数时间
struct Node {int data;struct Node* link;
};
struct Node* top = NULL;
void Push(int x)
{struct Node* temp =(struct Node*)malloc(sizeof(struct Node));temp->data = x;temp->link = top;top = temp;
}
void Pop()
{if (top == NULL) return;//如果栈满struct Node* temp;temp = top;top = top->link;free(temp);
}int  Top()
{return top->data;
}int IsEmpty()
{if (top == NULL)return 1;return 0;
}
int main(void)
{Push(2);Push(3);Pop();return 0;
}
//优点 不用考虑栈满
//缺点 消耗一点多余指针域内存，但是不用的结点都会释放