堆栈数据结构
在本教程中,您将了解堆栈数据结构以及使用 Python、Java 和 C/C++ 实现堆栈。
堆栈是遵循**后进先出 (LIFO)**原则的线性数据结构。这意味最后插入堆栈中的元素会被最先删除。
您可以将堆栈数据结构视为堆叠在另一个盘子上的盘子。
在这里,您可以:
- 在最上面放一个新盘子
- 从最上面拿走一个盘子
而且,如果你想要底部的盘子,你必须首先移除顶部的所有盘子。这正是堆栈数据结构的工作原理。
堆栈的 LIFO 原则
在编程术语中,将项目放在堆栈顶部称为 push,删除项目称为 pop。
在上图中,虽然项目 3 被保留在最后,但它首先被删除。这正是 LIFO(后进先出)原则的工作原理。
我们可以使用任何编程语言(如 C、C++、Java、Python 或 C#)实现堆栈,但规范几乎相同。
堆栈的基本操作
有一些基本操作允许我们在堆栈上执行不同的操作。
- Push : 将一个元素添加到栈顶
- Pop : 从栈顶移除一个元素
- IsEmpty : 检查堆栈是否为空
- IsFull : 检查堆栈是否已满
- Peek:获取顶部元素的值而不删除它
堆栈数据结构的工作原理
操作如下:
- 一个称为
TOP
的指针用于跟踪堆栈中的顶部元素。 - 初始化堆栈时,我们将其值设置为
-1
,以便我们可以通过比较TOP == -1
来检查堆栈是否为空。 - 在添加一个元素时,我们增加了
TOP
的值并将新元素放置在TOP
指向的位置。 - 在删除一个元素时,我们返回
TOP
指向的元素,并减少TOP
的值。 - 在添加之前,我们检查堆栈是否已满。
- 在删除之前,我们检查堆栈是否为空。
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。