栈是一个线性数据结构，遵循后进先出(LIFO)准则。意味着最后被插入到栈里的元素会被最先取出。

你可以把栈这种数据结构想象成一摞摞叠放在一起的盘子。

对这摞盘子来说，你可以：

• 在最上面放一个新盘子
• 拿走最上面的盘子

并且，如果你想要最下面的盘子，你必须拿走上面所有的盘子。这正是栈数据结构工作的方式。

栈的后进先出规则

从编程的角度来讲，将一个元素放入栈顶的操作被称为 “入栈（push）”，而移除一个元素的操作则被称为 “出栈（pop）”

在上面的图片中，尽管3最后一个放进来，却是最先被取出的。这就是后进先出(LIFO)的工作方式

可以在任何编程语言比如C、C++、Java、Python或者C#中实现栈，规范差不多都一样。

栈的基本操作

有一些基本操作，使我们能够对栈执行不同的动作。

• 入栈（Push）：将一个元素添加到栈顶。
• 出栈（Pop）：从栈顶移除一个元素。
• 判断是否为空（IsEmpty）：检查栈是否为空。
• 判断是否已满（IsFull）：检查栈是否已满。
• 查看栈顶元素（Peek）：获取栈顶元素的值，而不移除该元素。

栈数据结构的工作原理

这些操作的工作方式如下：

1. 使用一个名为TOP的指针来跟踪栈中的栈顶元素。
2. 在初始化栈时，我们将TOP的值设为 -1，这样就可以通过比较TOP是否等于 -1 来检查栈是否为空。
3. 入栈操作时，我们将TOP的值加 1，并把新元素放置在TOP所指向的位置。
4. 出栈操作时，我们返回TOP所指向的元素，然后将TOP的值减 1。
5. 入栈之前，我们会检查栈是否已经满了。
6. 出栈之前，我们会检查栈是否已经为空。

Python、Java、C和C++实现的栈

最常见的栈的实现方式是使用数组，但它也可以使用列表来实现。

Python

# Stack implementation in python


# Creating a stack
def create_stack():
    stack = []
    return stack


# Creating an empty stack
def check_empty(stack):
    return len(stack) == 0


# Adding items into the stack
def push(stack, item):
    stack.append(item)
    print("pushed item: " + item)


# Removing an element from the stack
def pop(stack):
    if (check_empty(stack)):
        return "stack is empty"

    return stack.pop()


stack = create_stack()
push(stack, str(1))
push(stack, str(2))
push(stack, str(3))
push(stack, str(4))
print("popped item: " + pop(stack))
print("stack after popping an element: " + str(stack))

Java

// Stack implementation in Java

class Stack {
  private int arr[];
  private int top;
  private int capacity;

  // Creating a stack
  Stack(int size) {
    arr = new int[size];
    capacity = size;
    top = -1;
  }

  // Add elements into stack
  public void push(int x) {
    if (isFull()) {
      System.out.println("OverFlow\nProgram Terminated\n");
      System.exit(1);
    }

    System.out.println("Inserting " + x);
    arr[++top] = x;
  }

  // Remove element from stack
  public int pop() {
    if (isEmpty()) {
      System.out.println("STACK EMPTY");
      System.exit(1);
    }
    return arr[top--];
  }

  // Utility function to return the size of the stack
  public int size() {
    return top + 1;
  }

  // Check if the stack is empty
  public Boolean isEmpty() {
    return top == -1;
  }

  // Check if the stack is full
  public Boolean isFull() {
    return top == capacity - 1;
  }

  public void printStack() {
    for (int i = 0; i <= top; i++) {
      System.out.println(arr[i]);
    }
  }

  public static void main(String[] args) {
    Stack stack = new Stack(5);

    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);

    stack.pop();
    System.out.println("\nAfter popping out");

    stack.printStack();

  }
}

C

// Stack implementation in C

#include <stdio.h>
#include <stdlib.h>

#define MAX 10

int count = 0;

// Creating a stack
struct stack {
  int items[MAX];
  int top;
};
typedef struct stack st;

void createEmptyStack(st *s) {
  s->top = -1;
}

// Check if the stack is full
int isfull(st *s) {
  if (s->top == MAX - 1)
    return 1;
  else
    return 0;
}

// Check if the stack is empty
int isempty(st *s) {
  if (s->top == -1)
    return 1;
  else
    return 0;
}

// Add elements into stack
void push(st *s, int newitem) {
  if (isfull(s)) {
    printf("STACK FULL");
  } else {
    s->top++;
    s->items[s->top] = newitem;
  }
  count++;
}

// Remove element from stack
void pop(st *s) {
  if (isempty(s)) {
    printf("\n STACK EMPTY \n");
  } else {
    printf("Item popped= %d", s->items[s->top]);
    s->top--;
  }
  count--;
  printf("\n");
}

// Print elements of stack
void printStack(st *s) {
  printf("Stack: ");
  for (int i = 0; i < count; i++) {
    printf("%d ", s->items[i]);
  }
  printf("\n");
}

// Driver code
int main() {
  int ch;
  st *s = (st *)malloc(sizeof(st));

  createEmptyStack(s);

  push(s, 1);
  push(s, 2);
  push(s, 3);
  push(s, 4);

  printStack(s);

  pop(s);

  printf("\nAfter popping out\n");
  printStack(s);
}

C++

// Stack implementation in C++

#include <stdlib.h>
#include <iostream>

using namespace std;

#define MAX 10
int size = 0;

// Creating a stack
struct stack {
  int items[MAX];
  int top;
};
typedef struct stack st;

void createEmptyStack(st *s) {
  s->top = -1;
}

// Check if the stack is full
int isfull(st *s) {
  if (s->top == MAX - 1)
    return 1;
  else
    return 0;
}

// Check if the stack is empty
int isempty(st *s) {
  if (s->top == -1)
    return 1;
  else
    return 0;
}

// Add elements into stack
void push(st *s, int newitem) {
  if (isfull(s)) {
    cout << "STACK FULL";
  } else {
    s->top++;
    s->items[s->top] = newitem;
  }
  size++;
}

// Remove element from stack
void pop(st *s) {
  if (isempty(s)) {
    cout << "\n STACK EMPTY \n";
  } else {
    cout << "Item popped= " << s->items[s->top];
    s->top--;
  }
  size--;
  cout << endl;
}

// Print elements of stack
void printStack(st *s) {
  printf("Stack: ");
  for (int i = 0; i < size; i++) {
    cout << s->items[i] << " ";
  }
  cout << endl;
}

// Driver code
int main() {
  int ch;
  st *s = (st *)malloc(sizeof(st));

  createEmptyStack(s);

  push(s, 1);
  push(s, 2);
  push(s, 3);
  push(s, 4);

  printStack(s);

  pop(s);

  cout << "\nAfter popping out\n";
  printStack(s);
}

栈的时间复杂度

对于基于数组实现的栈，入栈（push）和出栈（pop）操作所花费的时间是固定的，也就是时间复杂度为 O(1)

栈数据结构的应用

尽管栈实现起来很简单，但很有用。最常见的栈的使用如下：

• 单词反转：将一个单词中的所有字母放入栈中，然后再将它们弹出。由于栈具有后进先出（LIFO）的顺序特点，这样你得到的字母顺序就是原来单词字母顺序的逆序。
• 在编译器中：编译器使用栈来计算像 “2 + 4 / 5 * (7 - 9)” 这样的表达式的值，方法是将表达式转换为前缀形式或后缀形式。
• 在浏览器中：浏览器的 “后退” 按钮会将你之前访问过的所有网址存储在一个栈中。每次访问一个新页面时，该页面的网址就会被添加到栈顶。当你按下 “后退” 按钮时，当前的网址会从栈中移除，然后访问栈中的前一个网址。