堆栈数据结构

在本教程中，您将了解堆栈数据结构以及使用 Python、Java 和 C/C++ 实现堆栈。

堆栈是遵循**后进先出 (LIFO)**原则的线性数据结构。这意味最后插入堆栈中的元素会被最先删除。

您可以将堆栈数据结构视为堆叠在另一个盘子上的盘子。

堆栈上的元素像一堆盘子一样被添加到顶部并从顶部移除
堆栈上的元素像一堆盘子一样被添加到顶部并从顶部移除

在这里，您可以：

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

而且，如果你想要底部的盘子，你必须首先移除顶部的所有盘子。这正是堆栈数据结构的工作原理。

堆栈的 LIFO 原则

在编程术语中，将项目放在堆栈顶部称为 push，删除项目称为 pop。

使用push和pop操作表示LIFO原理
堆栈 push 和 pop 操作

在上图中，虽然项目 3 被保留在最后，但它首先被删除。这正是 LIFO（后进先出）原则的工作原理。

我们可以使用任何编程语言（如 C、C++、Java、Python 或 C#）实现堆栈，但规范几乎相同。

堆栈的基本操作

有一些基本操作允许我们在堆栈上执行不同的操作。

  • Push : 将一个元素添加到栈顶
  • Pop : 从栈顶移除一个元素
  • IsEmpty : 检查堆栈是否为空
  • IsFull : 检查堆栈是否已满
  • Peek：获取顶部元素的值而不删除它

堆栈数据结构的工作原理

操作如下：

  1. 一个称为 TOP 的指针用于跟踪堆栈中的顶部元素。
  2. 初始化堆栈时，我们将其值设置为 -1，以便我们可以通过比较 TOP == -1 来检查堆栈是否为空。
  3. 在添加一个元素时，我们增加了 TOP 的值并将新元素放置在 TOP 指向的位置。
  4. 在删除一个元素时，我们返回 TOP 指向的元素，并减少 TOP 的值。
  5. 在添加之前，我们检查堆栈是否已满。
  6. 在删除之前，我们检查堆栈是否为空。

将元素添加到栈顶并从栈顶移除元素
堆栈数据结构的工作原理

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

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

使用 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 实现堆栈

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 实现堆栈

#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++ 实现堆栈

#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)。
  • 在浏览器中 - 浏览器中的后退按钮将您之前访问过的所有 URL 保存在堆栈中。每次访问新页面时，它都会添加到堆栈顶部。当您按下后退按钮时，当前 URL 将从堆栈中删除，并访问前一个 URL。
算法的渐进效率分析 队列数据结构