|
在本教程中，您将学习栈数据结构及其在Python，Java，C和C++中的实现。
堆栈是编程中有用的数据结构。就像一堆板子彼此叠放。
堆栈表示类似于一堆盘子
想一想用这样一堆盘子可以做的事情
如果要将板放在底部，则必须先卸下顶部的所有板。这种安排称为“ 后进先出” -放置的最后一个项目是第一个要出去的项目。
LIFO堆栈原理
用编程术语来说，将一个项目放在堆栈的顶部称为“推”，而将一个项目删除则称为“弹出”。
堆栈推入和弹出操作
在上图中，尽管项目2保留在最后，但它首先被移除-因此它遵循后进先出(LIFO)原则。
我们可以用任何编程语言(例如C，C++，Java， Python或C＃)实现堆栈，但规范几乎相同。
堆栈的基本操作
堆栈是一个对象，或更具体地说，是一个允许执行以下操作的抽象数据结构(ADT)：
堆栈数据结构的工作
操作如下：
称为TOP的指针用于跟踪堆栈中的顶部元素。 在初始化堆栈时大数据堆栈，我们将其值设置为-1，以便我们可以通过比较TOP == -1来检查堆栈是否为空。 推入元素时，我们增加TOP的值并将新元素放置在TOP指向的位置。 弹出元素时，我们返回TOP指向的元素并减小其值。 推入之前，我们检查堆栈是否已满弹出之前，我们检查堆栈是否已为空
堆栈数据结构的工作 Python，Java，C和C++中的堆栈实现
最常见的堆栈实现是使用数组，但是也可以使用列表来实现。
Python
爪哇
C
C +
# 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))
// 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();
}
}
// Stack implementation in C
#include
#include
#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);
}
// Stack implementation in C++
#include
#include
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)) {
printf("STACK FULL");
} else {
s->top++;
s->items[s->top] = newitem;
}
size++;
}
// 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--;
}
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);
}
堆栈时间复杂度
对于基于数组的堆栈实现，推入和弹出操作需要恒定的时间，即O(1)因为在两种情况下都只有指针移动。
堆栈数据结构的应用
尽管堆栈是一个易于实现的简单数据结构，但它非常强大。堆栈最常见的用途是：
（编辑：拼字网 - 核心网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
