“栈”和“堆”是两个不同的概念。栈是一种特殊的数据结构，在中断处理特别是重要数据的现场保护有着重要意义。
栈存储数据的方式跟数组一样，都是将元素排成一行。只不过它还有以下3条约束。
1、只能在末尾插入数据。
2、只能读取末尾的数据。
3、只能移除末尾的数据。
一般情况都把栈的末尾称为栈顶，把栈的开头称为栈底。
往栈里插入数据，也叫作压栈，可以想象为一个碟子压在其他碟子上的画面。从栈顶移除数据叫作出栈。
顺序可以是 LIFO（后进先出）或 FILO（先进后出）。最后入栈的元素，会最先出栈。
二、操作可以使用数组或链表实现栈。
Push：在堆栈中添加一个项目。 如果堆栈已满，则称其为溢出条件。
Pop：从堆栈中删除一个项目。 这些项目以它们被推送的相反顺序弹出。 如果堆栈为空，则称其为下溢条件。
Peek 或 Top：返回堆栈的顶部元素。
isEmpty：如果堆栈为空，则返回 true，否则返回 false。
堆栈操作的时间复杂度：
push()、pop()、isEmpty() 和 peek() 都需要 O(1) 时间。 我们不会在任何这些操作中运行任何循环。
三、理解栈堆栈有许多现实生活中的例子。 考虑一个简单的例子，在食堂里，盘子相互叠放。 位于顶部的板是第一个被移除的板，即已放置在最底部位置的板在堆栈中保留的时间最长。 因此，可以简单地看出遵循 LIFO/FILO 的顺序。
许多地方的重做撤消功能，如编辑器、Photoshop。
Web 浏览器中的前进和后退功能
用于许多算法，如河内塔、树遍历、股票跨度问题、直方图问题。
在内存管理中，任何现代计算机都使用堆栈作为运行目的的主要管理。在计算机系统中运行的每个程序都有自己的内存分配字符串反转也是栈的另一个应用。在这里，每个字符被一个一个地插入到堆栈中。所以字符串的第一个字符在栈底，而字符串的最后一个元素在栈顶。在堆栈上执行弹出操作后，我们以相反的顺序得到一个字符串。
四、实现栈这里使用java代码进行实现。
1、使用数组
class Stack {
static final int MAX = 1000;
int top;
int a[] = new int[MAX]; // Maximum size of Stack
boolean isEmpty()
{
return (top < 0);
}
Stack()
{
top = -1;
}
boolean push(int x)
{
if (top >= (MAX - 1)) {
System.out.println("Stack Overflow");
return false;
}
else {
a[++top] = x;
System.out.println(x + " pushed into stack");
return true;
}
}
int pop()
{
if (top < 0) {
System.out.println("Stack Underflow");
return 0;
}
else {
int x = a[top--];
return x;
}
}
int peek()
{
if (top < 0) {
System.out.println("Stack Underflow");
return 0;
}
else {
int x = a[top];
return x;
}
}
void print(){
for(int i = top;i>-1;i--){
System.out.print(" "+ a[i]);
}
}
}
// Driver code
class Main {
public static void main(String args[])
{
Stack s = new Stack();
s.push(10);
s.push(20);
s.push(30);
System.out.println(s.pop() + " Popped from stack");
System.out.println("Top element is :" + s.peek());
System.out.print("Elements present in stack :");
s.print();
}
}
缺点，不是动态的，它不会根据运行时的需要而增长和缩小。
2、使用链表// Java Code for linked List Implementation
public class StackAslinkedList {
StackNode root;
static class StackNode {
int data;
StackNode next;
StackNode(int data) { this.data = data; }
}
public boolean isEmpty()
{
if (root == null) {
return true;
}
else
return false;
}
public void push(int data)
{
StackNode newNode = new StackNode(data);
if (root == null) {
root = newNode;
}
else {
StackNode temp = root;
root = newNode;
newNode.next = temp;
}
System.out.println(data + " pushed to stack");
}
public int pop()
{
int popped = Integer.MIN_VALUE;
if (root == null) {
System.out.println("Stack is Empty");
}
else {
popped = root.data;
root = root.next;
}
return popped;
}
public int peek()
{
if (root == null) {
System.out.println("Stack is empty");
return Integer.MIN_VALUE;
}
else {
return root.data;
}
}
// Driver code
public static void main(String[] args)
{
StackAslinkedList sll = new StackAslinkedList();
sll.push(10);
sll.push(20);
sll.push(30);
System.out.println(sll.pop()
+ " popped from stack");
System.out.println("Top element is " + sll.peek());
}
}
缺点：由于涉及指针，需要额外的内存。
