栈数据结构

什么是栈？

栈是一种线性数据结构，其中元素按照LIFO（后进先出）原则存储，最后一个插入的元素将是第一个被删除的元素。栈是一种抽象数据类型（ADT），在大多数编程语言中被广泛使用。它之所以被称为栈，是因为它的操作类似于现实世界的栈，例如——一副扑克牌或一堆盘子等。

栈被认为是一种复杂的数据结构，因为它使用其他数据结构来实现，例如数组、链表等。

栈表示

栈只允许在一端进行所有数据操作。在任何给定时间，我们只能访问栈的顶部元素。

下图描述了一个栈及其操作：

栈可以通过数组、结构体、指针和链表来实现。栈可以是固定大小的，也可以具有动态调整大小的功能。在这里，我们将使用数组来实现栈，这使得它成为一个固定大小的栈实现。

栈的基本操作

栈操作通常用于初始化、使用和取消初始化栈ADT。

栈ADT中最基本的操作包括：push()、pop()、peek()、isFull()、isEmpty()。这些都是内置操作，用于执行数据操作并检查栈的状态。

栈使用指针始终指向栈中最顶部的元素，因此被称为顶部指针。

栈插入：push()

push()是一种将元素插入栈的操作。以下是更简单地描述push()操作的算法。

算法

1. Checks if the stack is full.
2. If the stack is full, produces an error and exit.
3. If the stack is not full, increments top to point next 
    empty space.
4. Adds data element to the stack location, where top 
    is pointing.
5. Returns success.

示例

以下是此操作在各种编程语言中的实现：

C C++ Java Python

#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is full*/
int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}

/* Function to insert into the stack */
int push(int data){
   if(!isfull()) {
      top = top + 1;
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}

/* Main function */
int main(){
   int i;
   push(44);
   push(10);
   push(62);
   push(123);
   push(15);
   printf("Stack Elements: \n");
   
   // print stack data
   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;

/* Check if the stack is full*/
int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}

/* Function to insert into the stack */
int push(int data){
   if(!isfull()) {
      top = top + 1;
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
   return data;
}

/* Main function */
int main(){
   int i;
   push(44);
   push(10);
   push(62);
   push(123);
   push(15);
   printf("Stack Elements: \n");

   // print stack data
   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: ");
   // print stack data
   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. Checks if the stack is empty.
2. If the stack is empty, produces an error and exit.
3. If the stack is not empty, accesses the data element at 
   which top is pointing.
4. Decreases the value of top by 1.
5. Returns success.

示例

以下是此操作在各种编程语言中的实现：

C C++ Java Python

#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is empty */
int isempty(){
   if(top == -1)
      return 1;
   else
      return 0;
}

/* Check if the stack is full*/
int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}

/* Function to delete from the stack */
int pop(){
   int data;
   if(!isempty()) {
      data = stack[top];
      top = top - 1;
      return data;
   } else {
      printf("Could not retrieve data, Stack is empty.\n");
   }
}

/* Function to insert into the stack */
int push(int data){
   if(!isfull()) {
      top = top + 1;
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}

/* Main function */
int main(){
   int i;
   push(44);
   push(10);
   push(62);
   push(123);
   push(15);
   printf("Stack Elements: \n");

   // print stack data
   for(i = 0; i < 8; i++) {
      printf("%d ", stack[i]);
   }
   /*printf("Element at top of the stack: %d\n" ,peek());*/
   printf("\nElements popped: \n");

   // print stack data
   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;

/* Check if the stack is empty */
int isempty(){
   if(top == -1)
      return 1;
   else
      return 0;
}

/* Check if the stack is full*/
int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}

/* Function to delete from the stack */
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;
}

/* Function to insert into the stack */
int push(int data){
   if(!isfull()) {
      top = top + 1;
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
   return data;
}

/* Main function */
int main(){
   int i;
   push(44);
   push(10);
   push(62);
   push(123);
   push(15);
   printf("Stack Elements: \n");

   // print stack data
   for(i = 0; i < 8; i++) {
      printf("%d ", stack[i]);
   }
   
   /*printf("Element at top of the stack: %d\n" ,peek());*/
   printf("\nElements popped: \n");

   // print stack data
   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;
/* Check if the stack is empty */
public static int isempty(){
   if(top == -1)
      return 1;
   else
      return 0;
}
/* Check if the stack is full*/
public static int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}
/* Function to delete from the stack */
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;
}
/* Function to insert into the stack */
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;
}
/* Main function */
public static void main(String[] args){
   push(44);
   push(10);
   push(62);
   push(123);
   push(15);
   System.out.print("Stack Elements: ");
   // print stack data
   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: ");

   // print stack data
   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. START
2. return the element at the top of the stack
3. END

示例

以下是此操作在各种编程语言中的实现：

C C++ Java Python

#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is full */
int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}

/* Function to return the topmost element in the stack */
int peek(){
   return stack[top];
}

/* Function to insert into the stack */
int push(int data){
   if(!isfull()) {
      top = top + 1;
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}

/* Main function */
int main(){
   int i;
   push(44);
   push(10);
   push(62);
   push(123);
   push(15);
   printf("Stack Elements: \n");

   // print stack data
   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;

/* Check if the stack is full */
int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}

/* Function to return the topmost element in the stack */
int peek(){
   return stack[top];
}

/* Function to insert into the stack */
int push(int data){
   if(!isfull()) {
      top = top + 1;
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
   return data;
}

/* Main function */
int main(){
   int i;
   push(44);
   push(10);
   push(62);
   push(123);
   push(15);
   printf("Stack Elements: \n");

   // print stack data
   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;
/* Check if the stack is full */
public static int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}

/* Function to return the topmost element in the stack */
public static int peek(){
   return stack[top];
}

/* Function to insert into the stack */
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;
}

/* Main function */
public static void main(String[] args){
   push(44);
   push(10);
   push(62);
   push(123);
   push(15);
   System.out.print("Stack Elements: ");

   // print stack data
   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()操作检查栈是否已满。此操作用于通过顶部指针检查栈的状态。

算法

1. START
2. If the size of the stack is equal to the top position of the stack,
   the stack is full. Return 1.
3. Otherwise, return 0.
4. END

示例

以下是此操作在各种编程语言中的实现：

C C++ Java Python

#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is full */
int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}

/* Main function */
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;

/* Check if the stack is full */
int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}

/* Main function */
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); // 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. 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;

/* Check if the stack is empty */
int isempty() {
   if(top == -1)
      return 1;
   else
      return 0;
}

/* Main function */
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;

/* Check if the stack is empty */
int isempty(){
   if(top == -1)
      return 1;
   else
      return 0;
}

/* Main function */
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;

/* Check if the stack is empty */
public static int isempty(){
   if(top == -1)
      return 1;
   else
      return 0;
}

/* Main function */
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

栈完整实现

以下是栈在各种编程语言中的完整实现：

C C++ Java Python

#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* Check if the stack is empty */
int isempty(){
   if(top == -1)
      return 1;
   else
      return 0;
}
/* Check if the stack is full */
int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}

/* Function to return the topmost element in the stack */
int peek(){
   return stack[top];
}

/* Function to delete from the stack */
int pop(){
   int data;
   if(!isempty()) {
      data = stack[top];
      top = top - 1;
      return data;
   } else {
      printf("Could not retrieve data, Stack is empty.\n");
   }
}

/* Function to insert into the stack */
int push(int data){
   if(!isfull()) {
      top = top + 1;
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}
/* Main function */
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");
   // print stack data
   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;
/* Check if the stack is empty */
int isempty(){
   if(top == -1)
      return 1;
   else
      return 0;
}
/* Check if the stack is full */
int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}
/* Function to return the topmost element in the stack */
int peek(){
   return stack[top];
}
/* Function to delete from the stack */
int pop(){
   int data;
   if(!isempty()) {
      data = stack[top];
      top = top - 1;
      return data;
   } else
      cout << "Could not retrieve data, Stack is empty." << endl;
}
/* Function to insert into the stack */
int push(int data){
   if(!isfull()) {
      top = top + 1;
      stack[top] = data;
   } else
      cout << "Could not insert data, Stack is full." << endl;
}
/* Main function */
int main(){
   push(44);
   push(10);
   push(62);
   push(123);
   push(15);
   cout << "Element at top of the stack: " << peek() << endl;
   printf("Elements: \n");
   // print stack data
   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;
/* Check if the stack is empty */
public static int isempty(){
   if(top == -1)
      return 1;
   else
      return 0;
}
/* Check if the stack is full */
public static int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}
/* Function to return the topmost element in the stack */
public static int peek(){
   return stack[top];
}
/* Function to delete from the stack */
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;
}
/* Function to insert into the stack */
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;
}
/* Main function */
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: ");
   // print stack data
   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语言实现的栈程序的实现

打印页面