跳到主要内容

栈数据结构

提示
  1. 后进先出原则：栈是一种遵循后进先出（LIFO）原则的线性数据结构，最后插入的元素会首先被移除。
  2. 基本操作：栈的主要操作包括压栈（添加元素到栈顶）、弹栈（移除栈顶元素）、检查栈是否为空或已满，以及查看栈顶元素但不移除。
  3. 实现方式：栈可以通过数组或列表在各种编程语言中实现，其操作的时间复杂度通常为O(1)，广泛应用于数据反转、编译器、浏览器历史记录等领域。

栈是一种线性数据结构，遵循**后进先出（LIFO, Last In First Out）**原则。这意味着最后插入栈中的元素会首先被移除。

你可以将栈数据结构想象成一堆叠在一起的盘子。

栈中的元素从顶部添加并从顶部移除，就像一堆盘子

在这里，你可以：

  • 在顶部放一个新盘子
  • 移除顶部的盘子

如果你想要底部的盘子，你必须先移除上面所有的盘子。这正是栈数据结构的工作方式。

栈的后进先出原则​

在编程术语中，将一个项目放在栈顶被称为压栈（push），移除一个项目被称为弹栈（pop）。

使用压栈和弹栈操作表示后进先出原则

在上图中，尽管项目3最后被放置，但它最先被移除。这正是后进先出（LIFO, Last In First Out）原则的工作方式。

我们可以使用 C、C++、Java、Python 或 C# 等任何编程语言实现栈，但规范基本相同。

栈的基本操作​

栈允许我们执行不同操作的一些基本操作包括：

  • 压栈（Push）：向栈顶添加一个元素
  • 弹栈（Pop）：移除栈顶的一个元素
  • IsEmpty：检查栈是否为空
  • IsFull：检查栈是否已满
  • Peek：获取栈顶元素的值，而不移除它

栈数据结构的工作原理​

操作如下进行：

  1. 使用一个名为 TOP 的指针来跟踪栈中的顶部元素。
  2. 初始化栈时，我们将其值设置为 -1，这样我们可以通过比较 TOP == -1 来检查栈是否为空。
  3. 压栈一个元素时，我们增加 TOP 的值，并将新元素放置在 TOP 指向的位置。
  4. 弹栈一个元素时，我们返回 TOP 指向的元素并减小其值。
  5. 压栈前，我们检查栈是否已满
  6. 弹栈前，我们检查栈是否已空

向栈顶添加元素和从栈顶移除元素

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

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

Python Java C C++

# Python 中的栈实现


# 创建一个栈
def create_stack():
    stack = []
    return stack


# 创建一个空栈
def check_empty(stack):
    return len(stack) == 0


# 向栈中添加项目
def push(stack, item):
    stack.append(item)
    print("压栈的项目: " + item)


# 从栈中移除一个元素
def pop(stack):
    if (check_empty(stack)):
        return "栈为空"

    return stack.pop()


stack = create_stack()
push(stack, str(1))
push(stack, str(2))
push(stack, str(3))
push(stack, str(4))
print("弹栈的项目: " + pop(stack))
print("弹栈后的栈: " + str(stack))

// Java 中的栈实现

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

  // 创建一个栈
  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 语言中栈的实现

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

#define MAX 10

int count = 0;

// 创建一个栈
struct stack {
  int items[MAX];
  int top;
};
typedef struct stack st;

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

// 检查栈是否已满
int isfull(st *s) {
  if (s->top == MAX - 1)
    return 1;
  else
    return 0;
}

// 检查栈是否为空
int isempty(st *s) {
  if (s->top == -1)
    return 1;
  else
    return 0;
}

// 向栈中添加元素
void push(st *s, int newitem) {
  if (isfull(s)) {
    printf("栈已满");
  } else {
    s->top++;
    s->items[s->top] = newitem;
  }
  count++;
}

// 从栈中移除元素
void pop(st *s) {
  if (isempty(s)) {
    printf("\n 栈为空 \n");
  } else {
    printf("弹出的元素= %d", s->items[s->top]);
    s->top--;
  }
  count--;
  printf("\n");
}

// 打印栈中的元素
void printStack(st *s) {
  printf("栈: ");
  for (int i = 0; i < count; i++) {
    printf("%d ", s->items[i]);
  }
  printf("\n");
}

// 主函数
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("\n弹出后\n");
  printStack(s);
}
// C++ 中栈的实现

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

using namespace std;

#define MAX 10
int size = 0;

// 创建一个栈
struct stack {
  int items[MAX];
  int top;
};
typedef struct stack st;

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

// 检查栈是否已满
int isfull(st *s) {
  if (s->top == MAX - 1)
    return 1;
  else
    return 0;
}

// 检查栈是否为空
int isempty(st *s) {
  if (s->top == -1)
    return 1;
  else
    return 0;
}

// 向栈中添加元素
void push(st *s, int newitem) {
  if (isfull(s)) {
    cout << "栈已满";
  } else {
    s->top++;
    s->items[s->top] = newitem;
  }
  size++;
}

// 从栈中移除元素
void pop(st *s) {
  if (isempty(s)) {
    cout << "\n 栈为空 \n";
  } else {
    cout << "弹出的元素= " << s->items[s->top];
    s->top--;
  }
  size--;
  cout << endl;
}

// 打印栈中的元素
void printStack(st *s) {
  printf("栈: ");
  for (int i = 0; i < size; i++) {
    cout << s->items[i] << " ";
  }
  cout << endl;
}

// 主函数
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 << "\n弹出后\n";
  printStack(s);
}

栈的时间复杂度​

对于基于数组的栈实现，压栈（push）和弹栈（pop）操作都是常数时间，即 O(1)。

栈数据结构的应用​

尽管栈是一个简单的数据结构，但它非常强大。栈最常见的用途包括：

  • 反转单词 - 将所有字母放入栈中，然后弹出。由于栈的后进先出顺序，你将以相反的顺序获得字母。
  • 在编译器中 - 编译器使用栈来计算诸如 2 + 4 / 5 * (7 - 9) 这样的表达式的值，方法是将表达式转换为前缀或后缀形式。
  • 在浏览器中 - 浏览器的后退按钮将你之前访问过的所有 URL 保存在一个栈中。每次你访问一个新页面，它就被添加到栈顶。当你按下后退按钮时，当前的 URL 从栈中移除，访问前一个 URL。
最后于 更新