栈数据结构
什么是栈？
栈是一种线性数据结构，其元素按照 LIFO（Last In First Out，后进先出）原则存储，最后插入的元素将是第一个被删除的元素。栈是一种抽象数据类型（ADT），在大多数编程语言中被广泛使用。它之所以被称为栈，是因为它的操作类似于现实世界中的栈，例如一叠纸牌或一堆盘子等。
栈被认为是一种复杂的数据结构，因为它使用其他数据结构进行实现，例如 Arrays、Linked lists 等。
栈的表示
栈只允许在一端进行所有数据操作。在任何给定时间，我们只能访问栈的顶部元素。
下图描绘了栈及其操作 —
栈可以通过 Array、Structure、Pointer 和 Linked List 来实现。栈可以是固定大小的，也可以具有动态调整大小的功能。这里，我们将使用 arrays 来实现栈，这使得它成为一种固定大小的栈实现。
栈的基本操作
栈的操作通常用于栈 ADT 的初始化、使用和反初始化。
栈 ADT 中最基本操作包括：push()、pop()、peek()、isFull()、isEmpty()。这些都是内置操作，用于执行数据操作并检查栈的状态。
栈使用指针始终指向栈内的最顶层元素，因此称为top 指针。
栈插入：push()
push() 是一种将元素插入栈中的操作。以下是一个以更简单方式描述 push() 操作的算法。
算法
1. 检查栈是否已满。 2. 如果栈已满，产生错误并退出。 3. 如果栈未满，将 top 递增以指向下一个空闲位置。 4. 将数据元素添加到 top 指向的栈位置。 5. 返回成功。
示例
以下是此操作在各种编程语言中的实现 −
C
C++
Java
Python
#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("Could not insert data, Stack is full.\n");
}
}
/* 主函数 */
int main(){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements: \n");
// 打印栈数据
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("Could not insert data, Stack is full.\n");
}
return data;
}
/* 主函数 */
int main(){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements: \n");
// 打印栈数据
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("Could not insert data, Stack is full.\n");
}
return data;
}
public static void main(String[] args){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
System.out.print("\nStack 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("Could not insert data, Stack is full.")
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. 如果栈不为空，则访问 top 指针所指向的数据元素。 4. 将 top 的值减少 1。 5. 返回成功。
示例
以下是此操作在各种编程语言中的实现 −
C
C++
Java
Python
#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("Could not retrieve data, Stack is empty.\n");
}
}
/* 向栈中插入元素的函数 */
int push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}
/* 主函数 */
int main(){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements: \n");
// 打印栈数据
for(i = 0; i < 8; i++) {
printf("%d ", stack[i]);
}
/*printf("Element at top of the stack: %d\n" ,peek());*/
printf("\nElements popped: \n");
// 打印栈数据
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("Could not retrieve data, Stack is empty.\n");
}
return data;
}
/* 向栈中插入元素的函数 */
int push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
return data;
}
/* 主函数 */
int main(){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements: \n");
// 打印栈数据
for(i = 0; i < 8; i++) {
printf("%d ", stack[i]);
}
/*printf("Element at top of the stack: %d\n" ,peek());*/
printf("\nElements popped: \n");
// 打印栈数据
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("Could not retrieve data, Stack is empty.");
}
return data;
}
/* 向栈中插入元素的函数 */
public static int push(int data){
if(isfull() != 1) {
top = top + 1;
stack[top] = data;
} else {
System.out.print("\nCould not insert data, Stack is full.\n");
}
return data;
}
/* 主函数 */
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("Element at top of the stack: %d\n" ,peek());*/
System.out.print("\nElements 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("Could not retrieve data, Stack is empty.")
return data
def push(data):
global top
if(isfull() != 1):
top = top + 1
stack[top] = data
else:
print("\nCould not insert data, Stack is full.")
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("\nElements 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. 结束
示例
以下是此操作在各种编程语言中的实现 −
C
C++
Java
Python
#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("Could not insert data, Stack is full.\n");
}
}
/* 主函数 */
int main(){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements: \n");
// 打印栈数据
for(i = 0; i < 8; i++) {
printf("%d ", stack[i]);
}
printf("\nElement at top of the stack: %d\n" ,peek());
return 0;
}
输出
Stack Elements: 44 10 62 123 15 0 0 0 Element at top of the stack: 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("Could not insert data, Stack is full.\n");
}
return data;
}
/* 主函数 */
int main(){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements: \n");
// 打印栈数据
for(i = 0; i < 8; i++) {
printf("%d ", stack[i]);
}
printf("\nElement at top of the stack: %d\n" ,peek());
return 0;
}
输出
Stack Elements: 44 10 62 123 15 0 0 0 Element at top of the stack: 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("Could not insert data, Stack is full.");
}
return data;
}
/* 主函数 */
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("\nElement at top of the stack: " + peek());
}
}
输出
Stack Elements: 44 10 62 123 15 0 0 0 Element at top of the stack: 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("Could not insert data, Stack is full.")
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("\nElement at top of the stack: ", peek())
输出
Stack Elements: 44 10 62 123 15 0 0 0 Element at top of the stack: 15
验证栈是否已满：isFull()
isFull() 操作用于检查栈是否已满。此操作通过 top 指针来检查栈的状态。
算法
1. 开始 2. 如果栈的大小等于栈的 top 位置， 则栈已满。返回 1。 3. 否则，返回 0。 4. 结束
示例
以下是此操作在各种编程语言中的实现 −
C
C++
Java
Python
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* 检查栈是否已满 */
int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}
/* 主函数 */
int main(){
printf("Stack full: %s\n" , 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;
}
/* 主函数 */
int main(){
printf("Stack full: %s\n" , 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\n");
return;
}
arr[++top] = key;
}
public static void main (String[] args) {
StackExample stk = new StackExample(5);
stk.push(1); // 在栈中插入 1
stk.push(2);
stk.push(3);
stk.push(4);
stk.push(5);
System.out.println("Stack full: " + stk.isFull());
}
}
输出
Stack full: true
# Python 栈代码 (isFull)
MAXSIZE = 8
stack = [None] * MAXSIZE
top = -1
# 检查栈是否已满
def isfull():
if top == MAXSIZE - 1:
return True
else:
return False
# 主函数
print("Stack full:", isfull())
输出
Stack full: False
验证栈是否为空：isEmpty()
isEmpty() 操作用于验证栈是否为空。此操作通过 top 指针来检查栈的状态。
算法
1. START 2. If the top value is -1, the stack is empty. Return 1. 3. Otherwise, return 0. 4. END
示例
以下是此操作在各种编程语言中的实现 −
C
C++
Java
Python
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* 检查栈是否为空 */
int isempty() {
if(top == -1)
return 1;
else
return 0;
}
/* 主函数 */
int main() {
printf("Stack empty: %s\n" , 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;
}
/* 主函数 */
int main(){
printf("Stack empty: %s\n" , 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;
}
/* 主函数 */
public static void main(String[] args){
boolean res = isempty() == 1 ? true : false;
System.out.print("Stack empty: " + res);
}
}
输出
Stack empty: true
#栈的Python代码（isEmpty）
MAXSIZE = 8
stack = [None] * MAXSIZE
top = -1
#检查栈是否为空
def isempty():
if top == -1:
return True
else:
return False
#主函数
print("Stack empty:", isempty())
输出
Stack empty: True
Stack 完整实现
以下是各种编程语言中 Stack 的完整实现 −
C
C++
Java
Python
#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("Could not retrieve data, Stack is empty.\n");
}
}
/* 向栈中插入元素的函数 */
int push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}
/* 主函数 */
int main(){
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Element at top of the stack: %d\n" ,peek());
printf("Elements: \n");
// 打印栈数据
while(!isempty()) {
int data = pop();
printf("%d\n",data);
}
printf("Stack full: %s\n" , isfull()?"true":"false");
printf("Stack empty: %s\n" , isempty()?"true":"false");
return 0;
}
输出
Element at top of the stack: 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 << "Could not retrieve data, Stack is empty." << endl;
}
/* 向栈中插入元素的函数 */
int push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else
cout << "Could not insert data, Stack is full." << endl;
}
/* 主函数 */
int main(){
push(44);
push(10);
push(62);
push(123);
push(15);
cout << "Element at top of the stack: " << peek() << endl;
printf("Elements: \n");
// 打印栈数据
while(!isempty()) {
int data = pop();
cout << data <<endl;
}
printf("Stack full: %s\n" , isfull()?"true":"false");
printf("Stack empty: %s\n" , isempty()?"true":"false");
return 0;
}
输出
Element at top of the stack: 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("Could not retrieve data, Stack is empty.");
return data;
}
/* 向栈中插入元素的函数 */
public static int push(int data){
if(isfull() != 1) {
top = top + 1;
stack[top] = data;
} else
System.out.print("Could not insert data, Stack is full.");
return data;
}
/* 主函数 */
public static void main(String[] args){
push(44);
push(10);
push(62);
push(123);
push(15);
System.out.print("Element at top of the stack: " + peek());
System.out.print("\nElements: ");
// 打印栈数据
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("\nStack full: " + res1);
System.out.print("\nStack empty: " + res2);
}
}
输出
Element at top of the stack: 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("Could not retrieve data, Stack is empty.")
return data
def push(data):
global top
if(isfull() != 1):
top = top + 1
stack[top] = data
else:
print("Could not insert data, Stack is full.")
return data
push(44)
push(10)
push(62)
push(123)
push(15)
print("Element at top of the stack: ", peek())
print("Elements: ")
while(isempty() != 1):
data = pop();
print(data, end = " ")
print("\nStack full: ",bool({True: 1, False: 0} [isfull() == 1]))
print("Stack empty: ",bool({True: 1, False: 0} [isempty() == 1]))
输出
Element at top of the stack: 15 Elements: 15 123 62 10 44 Stack full: False Stack empty: True
C 语言中的栈实现
点击查看使用 C 实现的栈程序