栈数据结构
什么是栈？
栈是一种线性数据结构，其元素按照后进先出（LIFO）原则存储，即最后插入的元素最先被删除。栈是一种抽象数据类型 (ADT)，在大多数编程语言中广泛使用。它之所以被称为栈，是因为它的操作与现实世界中的栈类似，例如减一副牌或一堆盘子等。
栈被认为是一种复杂的数据结构，因为它使用其他数据结构来实现，例如数组、链表等。
栈的表示
栈只允许在一端进行所有数据操作。在任何给定时刻，我们只能访问栈的顶部元素。
下图描述了栈及其操作 −
栈可以通过数组、结构体、指针和链表来实现。栈可以是固定大小的，也可以是动态调整大小的。这里，我们将使用数组来实现栈，这使得它成为一个固定大小的栈实现。
栈的基本操作
栈操作通常用于栈ADT的初始化、使用和取消初始化。
栈ADT中最基本的操作包括：push()、pop()、peek()、isFull()、isEmpty()。这些都是内置操作，用于执行数据操作和检查堆栈状态。
堆栈使用的指针始终指向堆栈中最顶层的元素，因此称为top指针。
堆栈插入：push()
push() 操作用于将元素插入堆栈。以下算法以更简单的方式描述了 push() 操作。
算法
1. 检查堆栈是否已满。 2. 如果堆栈已满，则抛出错误并退出。 3. 如果堆栈未满，则将 top 加 1 以指向下一个 空位。 4. 将数据元素添加到 top 指向的堆栈位置。 5. 返回成功。
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* 检查堆栈是否已满 */
int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}
/* 插入堆栈的函数 */
int push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("无法插入数据，堆栈已满。
");
}
}
/* Main 主函数 */
int main(){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements:
");
// 打印堆栈数据
for(i = 0; i < 8; i++) {
printf("%d ", stack[i]);
}
return 0;
}
输出
Stack Elements: 44 10 62 123 15 0 0 0
#include <iostream>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* 检查堆栈是否已满 */
int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}
/* 插入堆栈的函数 */
int push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("无法插入数据，堆栈已满。
");
}
return data;
}
/* Main 主函数 */
int main(){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements:
");
// 打印堆栈数据
for(i = 0; i < 8; i++) {
printf("%d ", stack[i]);
}
return 0;
}
输出
Stack Elements: 44 10 62 123 15 0 0 0
public class Demo{
final static int MAXSIZE = 8;
static int stack[] = new int[MAXSIZE];
static int top = -1;
public static int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}
public static int push(int data){
if(isfull() != 1) {
top = top + 1;
stack[top] = data;
} else {
System.out.print("无法插入数据，堆栈已满。
");
}
return data;
}
public static void main(String[] args){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
System.out.print("
Stack Elements: ");
// 打印堆栈数据
for(i = 0; i < MAXSIZE; i++) {
System.out.print(stack[i] + " ");
}
}
}
输出
Stack Elements: 44 10 62 123 15 0 0 0
MAXSIZE = 8
stack = [0] * MAXSIZE
top = -1
def isfull():
if(top == MAXSIZE):
return 1
else:
return 0
def push(data):
global top
if(isfull() != 1):
top = top + 1
stack[top] = data
else:
print("无法插入数据，堆栈已满。")
return data
push(44)
push(10)
push(62)
push(123)
push(15)
print("Stack Elements: ")
for i in range(MAXSIZE):
print(stack[i], end = " ")
输出
Stack Elements: 44 10 62 123 15 0 0 0
注意 − 在 Java 中，我们使用内置方法 push() 来执行此操作。
栈删除：pop()
pop() 是一个数据操作操作，用于从栈中删除元素。以下伪代码以更简单的方式描述了 pop() 操作。
算法
1. 检查栈是否为空。 2. 如果栈为空，则抛出错误并退出。 3. 如果栈非空，则访问栈顶指向的数据元素。 4. 将栈顶的值减 1。 5. 返回成功。
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* 检查堆栈是否为空 */
int isempty(){
if(top == -1)
return 1;
else
return 0;
}
/* 检查堆栈是否已满 */
int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}
/* 从堆栈中删除的函数 */
int pop(){
int data;
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf("无法检索数据，堆栈为空。
");
}
}
/* 插入堆栈的函数 */
int push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("无法插入数据，堆栈已满。
");
}
}
/* Main 主函数 */
int main(){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements:
");
// 打印堆栈数据
for(i = 0; i < 8; i++) {
printf("%d ", stack[i]);
}
/*printf("堆栈顶部的元素： %d
" ,peek());*/
printf("
Elements popped:
");
// 打印堆栈数据
while(!isempty()) {
int data = pop();
printf("%d ",data);
}
return 0;
}
输出
Stack Elements: 44 10 62 123 15 0 0 0 Elements popped: 15 123 62 10 44
#include <iostream>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* 检查堆栈是否为空 */
int isempty(){
if(top == -1)
return 1;
else
return 0;
}
/* 检查堆栈是否已满 */
int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}
/* 从堆栈中删除的函数 */
int pop(){
int data;
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf("无法检索数据，堆栈为空。
");
}
return data;
}
/* 插入堆栈的函数 */
int push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("无法插入数据，堆栈已满。
");
}
return data;
}
/* Main 主函数 */
int main(){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements:
");
// 打印堆栈数据
for(i = 0; i < 8; i++) {
printf("%d ", stack[i]);
}
/*printf("堆栈顶部的元素： %d
" ,peek());*/
printf("
Elements popped:
");
// 打印堆栈数据
while(!isempty()) {
int data = pop();
printf("%d ",data);
}
return 0;
}
输出
Stack Elements: 44 10 62 123 15 0 0 0 Elements popped: 15 123 62 10 44
public class Demo{
final static int MAXSIZE = 8;
public static int stack[] = new int[MAXSIZE];
public static int top = -1;
/* 检查堆栈是否为空 */
public static int isempty(){
if(top == -1)
return 1;
else
return 0;
}
/* 检查堆栈是否已满 */
public static int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}
/* 从堆栈中删除的函数 */
public static int pop(){
int data = 0;
if(isempty() != 1) {
data = stack[top];
top = top - 1;
return data;
} else {
System.out.print("无法检索数据，堆栈为空。");
}
return data;
}
/* 插入堆栈的函数 */
public static int push(int data){
if(isfull() != 1) {
top = top + 1;
stack[top] = data;
} else {
System.out.print("
无法插入数据，堆栈已满。
");
}
return data;
}
/* Main 主函数 */
public static void main(String[] args){
push(44);
push(10);
push(62);
push(123);
push(15);
System.out.print("Stack Elements: ");
// 打印堆栈数据
for(int i = 0; i < MAXSIZE; i++) {
System.out.print(stack[i] + " ");
}
/*printf("堆栈顶部的元素： %d
" ,peek());*/
System.out.print("
Elements popped: ");
// 打印堆栈数据
while(isempty() != 1) {
int data = pop();
System.out.print(data + " ");
}
}
}
输出
Stack Elements: 44 10 62 123 15 0 0 0 Elements popped: 15 123 62 10 44
MAXSIZE = 8
stack = [0] * MAXSIZE
top = -1
def isempty():
if(top == -1):
return 1
else:
return 0
def isfull():
if(top == MAXSIZE):
return 1
else:
return 0
def pop():
global top
data = 0
if(isempty() != 1):
data = stack[top]
top = top - 1
return data
else:
print("无法检索数据，堆栈为空。")
return data
def push(data):
global top
if(isfull() != 1):
top = top + 1
stack[top] = data
else:
print("
无法插入数据，堆栈已满。")
return data
push(44);
push(10);
push(62);
push(123);
push(15);
print("Stack Elements: ")
for i in range (MAXSIZE):
print(stack[i], end = " ")
print("
Elements popped: ")
while(isempty() != 1):
data = pop()
print(data, end = " ")
输出
Stack Elements: 44 10 62 123 15 0 0 0 Elements popped: 15 123 62 10 44
注意 − 在 Java 中，我们使用内置方法 pop()。
从堆栈中检索最顶层元素：peek()
peek() 操作用于检索堆栈中最顶层的元素，但不删除它。此操作用于借助栈顶指针检查堆栈的状态。
算法
1. 开始 2. 返回堆栈顶部的元素 3. 结束
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* 检查堆栈是否已满 */
int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}
/* 返回堆栈最顶部元素的函数 */
int peek(){
return stack[top];
}
/* 插入堆栈的函数 */
int push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("无法插入数据，堆栈已满。
");
}
}
/* Main 主函数 */
int main(){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements:
");
// 打印堆栈数据
for(i = 0; i < 8; i++) {
printf("%d ", stack[i]);
}
printf("
堆栈顶部的元素： %d
" ,peek());
return 0;
}
输出
Stack Elements: 44 10 62 123 15 0 0 0 堆栈顶部的元素： 15
#include <iostream>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* 检查堆栈是否已满 */
int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}
/* 返回堆栈最顶部元素的函数 */
int peek(){
return stack[top];
}
/* 插入堆栈的函数 */
int push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("无法插入数据，堆栈已满。
");
}
return data;
}
/* Main 主函数 */
int main(){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements:
");
// 打印堆栈数据
for(i = 0; i < 8; i++) {
printf("%d ", stack[i]);
}
printf("
堆栈顶部的元素： %d
" ,peek());
return 0;
}
输出
Stack Elements: 44 10 62 123 15 0 0 0 堆栈顶部的元素： 15
public class Demo{
final static int MAXSIZE = 8;
public static int stack[] = new int[MAXSIZE];
public static int top = -1;
/* 检查堆栈是否已满 */
public static int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}
/* 返回堆栈最顶部元素的函数 */
public static int peek(){
return stack[top];
}
/* 插入堆栈的函数 */
public static int push(int data){
if(isfull() != 1) {
top = top + 1;
stack[top] = data;
} else {
System.out.print("无法插入数据，堆栈已满。");
}
return data;
}
/* Main 主函数 */
public static void main(String[] args){
push(44);
push(10);
push(62);
push(123);
push(15);
System.out.print("Stack Elements: ");
// 打印堆栈数据
for(int i = 0; i < MAXSIZE; i++) {
System.out.print(stack[i] + " ");
}
System.out.print("
堆栈顶部的元素： " + peek());
}
}
输出
Stack Elements: 44 10 62 123 15 0 0 0 堆栈顶部的元素： 15
MAXSIZE = 8;
stack = [0] * MAXSIZE
top = -1
def isfull():
if(top == MAXSIZE):
return 1
else:
return 0
def peek():
return stack[top]
def push(data):
global top
if(isfull() != 1):
top = top + 1
stack[top] = data
else:
print("无法插入数据，堆栈已满。")
return data
push(44);
push(10);
push(62);
push(123);
push(15);
print("Stack Elements: ")
for i in range(MAXSIZE):
print(stack[i], end = " ")
print("
堆栈顶部的元素： ", peek())
输出
Stack Elements: 44 10 62 123 15 0 0 0 堆栈顶部的元素： 15
验证堆栈是否已满：isFull()
isFull() 操作用于检查堆栈是否已满。此操作借助栈顶指针来检查堆栈的状态。
算法
1. 开始 2. 如果堆栈大小等于栈顶位置， 则堆栈已满。返回 1。 3. 否则，返回 0。 4. 结束
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* 检查堆栈是否已满 */
int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}
/* Main 主函数 */
int main(){
printf("Stack full: %s
" , isfull()?"true":"false");
return 0;
}
输出
Stack full: false
#include <iostream>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* 检查堆栈是否已满 */
int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}
/* Main 主函数 */
int main(){
printf("Stack full: %s
" , isfull()?"true":"false");
return 0;
}
输出
Stack full: false
import java.io.*;
public class StackExample {
private int arr[];
private int top;
private int capacity;
StackExample(int size) {
arr = new int[size];
capacity = size;
top = -1;
}
public boolean isEmpty() {
return top == -1;
}
public boolean isFull() {
return top == capacity - 1;
}
public void push(int key) {
if (isFull()) {
System.out.println("Stack is Full
");
return;
}
arr[++top] = key;
}
public static void main (String[] args) {
StackExample stk = new StackExample(5);
stk.push(1); // inserting 1 in the stack
stk.push(2);
stk.push(3);
stk.push(4);
stk.push(5);
System.out.println("Stack full: " + stk.isFull());
}
}
输出
Stack full: true
#python code for stack(IsFull)
MAXSIZE = 8
stack = [None] * MAXSIZE
top = -1
#Check if the stack is empty
def isfull():
if top == MAXSIZE - 1:
return True
else:
return False
#main function
print("Stack full:", isfull())
输出
Stack full: False
验证堆栈是否为空：isEmpty()
isEmpty() 操作用于验证堆栈是否为空。此操作借助栈顶指针检查堆栈状态。
算法
1. 开始 2. 如果栈顶值为 -1，则堆栈为空。返回 1。 3. 否则，返回 0。 4. 结束
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* 检查堆栈是否为空 */
int isempty() {
if(top == -1)
return 1;
else
return 0;
}
/* Main 主函数 */
int main() {
printf("Stack empty: %s
" , isempty()?"true":"false");
return 0;
}
输出
Stack empty: true
#include <iostream>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* 检查堆栈是否为空 */
int isempty(){
if(top == -1)
return 1;
else
return 0;
}
/* Main 主函数 */
int main(){
printf("Stack empty: %s
" , isempty()?"true":"false");
return 0;
}
输出
Stack empty: true
public class Demo{
final static int MAXSIZE = 8;
static int stack[] = new int[MAXSIZE];
static int top = -1;
/* 检查堆栈是否为空 */
public static int isempty(){
if(top == -1)
return 1;
else
return 0;
}
/* Main 主函数 */
public static void main(String[] args){
boolean res = isempty() == 1 ? true : false;
System.out.print("Stack empty: " + res);
}
}
输出
Stack empty: true
#python code for stack(IsFull)
MAXSIZE = 8
stack = [None] * MAXSIZE
top = -1
#Check if the stack is empty
def isempty():
if top == -1:
return True
else:
return False
#main function
print("Stack empty:", isempty())
输出
Stack empty: True
Stack 完整实现
以下是各种编程语言中 Stack 的完整实现 −
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* 检查堆栈是否为空 */
int isempty(){
if(top == -1)
return 1;
else
return 0;
}
/* 检查堆栈是否已满 */
int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}
/* 返回堆栈最顶部元素的函数 */
int peek(){
return stack[top];
}
/* 从堆栈中删除的函数 */
int pop(){
int data;
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf("无法检索数据，堆栈为空。
");
}
}
/* 插入堆栈的函数 */
int push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("无法插入数据，堆栈已满。
");
}
}
/* Main 主函数 */
int main(){
push(44);
push(10);
push(62);
push(123);
push(15);
printf("堆栈顶部的元素： %d
" ,peek());
printf("Elements:
");
// 打印堆栈数据
while(!isempty()) {
int data = pop();
printf("%d
",data);
}
printf("Stack full: %s
" , isfull()?"true":"false");
printf("Stack empty: %s
" , isempty()?"true":"false");
return 0;
}
输出
堆栈顶部的元素： 15 Elements: 15123 62 10 44 Stack full: false Stack empty: true
#include <iostream>
using namespace std;
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* 检查堆栈是否为空 */
int isempty(){
if(top == -1)
return 1;
else
return 0;
}
/* 检查堆栈是否已满 */
int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}
/* 返回堆栈最顶部元素的函数 */
int peek(){
return stack[top];
}
/* 从堆栈中删除的函数 */
int pop(){
int data;
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else
cout << "无法检索数据，堆栈为空。" << endl;
}
/* 插入堆栈的函数 */
int push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else
cout << "无法插入数据，堆栈已满。" << endl;
}
/* Main 主函数 */
int main(){
push(44);
push(10);
push(62);
push(123);
push(15);
cout << "堆栈顶部的元素： " << peek() << endl;
printf("Elements:
");
// 打印堆栈数据
while(!isempty()) {
int data = pop();
cout << data <<endl;
}
printf("Stack full: %s
" , isfull()?"true":"false");
printf("Stack empty: %s
" , isempty()?"true":"false");
return 0;
}
输出
堆栈顶部的元素： 15 Elements: 15 123 62 10 44 Stack full: false Stack empty: true
public class Demo{
final static int MAXSIZE = 8;
public static int stack[] = new int[MAXSIZE];
public static int top = -1;
/* 检查堆栈是否为空 */
public static int isempty(){
if(top == -1)
return 1;
else
return 0;
}
/* 检查堆栈是否已满 */
public static int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}
/* 返回堆栈最顶部元素的函数 */
public static int peek(){
return stack[top];
}
/* 从堆栈中删除的函数 */
public static int pop(){
int data = 0;
if(isempty() != 1) {
data = stack[top];
top = top - 1;
return data;
} else
System.out.print("无法检索数据，堆栈为空。");
return data;
}
/* 插入堆栈的函数 */
public static int push(int data){
if(isfull() != 1) {
top = top + 1;
stack[top] = data;
} else
System.out.print("无法插入数据，堆栈已满。");
return data;
}
/* Main 主函数 */
public static void main(String[] args){
push(44);
push(10);
push(62);
push(123);
push(15);
System.out.print("堆栈顶部的元素： " + peek());
System.out.print("
Elements: ");
// 打印堆栈数据
while(isempty() != 1) {
int data = pop();
System.out.print(data + " ");
}
boolean res1 = isfull() == 1 ? true : false;
boolean res2 = isempty() == 1 ? true : false;
System.out.print("
Stack full: " + res1);
System.out.print("
Stack empty: " + res2);
}
}
输出
堆栈顶部的元素： 15 Elements: 15 123 62 10 44 Stack full: false Stack empty: true
MAXSIZE = 8
stack = [0] * MAXSIZE
top = -1;
def isempty():
if(top == -1):
return 1
else:
return 0
def isfull():
if(top == MAXSIZE):
return 1
else:
return 0
def peek():
return stack[top]
def pop():
global data, top
if(isempty() != 1):
data = stack[top];
top = top - 1;
return data
else:
print("无法检索数据，堆栈为空。")
return data
def push(data):
global top
if(isfull() != 1):
top = top + 1
stack[top] = data
else:
print("无法插入数据，堆栈已满。")
return data
push(44)
push(10)
push(62)
push(123)
push(15)
print("堆栈顶部的元素： ", peek())
print("Elements: ")
while(isempty() != 1):
data = pop();
print(data, end = " ")
print("
Stack full: ",bool({True: 1, False: 0} [isfull() == 1]))
print("Stack empty: ",bool({True: 1, False: 0} [isempty() == 1]))
输出
堆栈顶部的元素： 15 Elements: 15 123 62 10 44 Stack full: False Stack empty: True
C 语言堆栈实现
点击查看C 语言堆栈程序的实现
