数据结构和算法 - 堆栈内存溢出

堆栈是一种抽象数据类型 (ADT)，在大多数编程语言中广泛使用。它之所以被命名为“堆栈”，是因为它具有与现实世界中的堆栈类似的操作，例如，一副卡片或一堆盘子等。

堆栈遵循 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.

例子

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

#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");
   }
}

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

import java.io.*;
import java.util.*; // util imports the stack class
public class StackExample {
   public static void main (String[] args) {
      Stack<Integer> stk = new Stack<Integer>();
      
      // inserting elements into the stack
      stk.push(52);
      stk.push(19);
      stk.push(33);
      stk.push(14);
      stk.push(6);
      System.out.print("The stack is: " + stk);
   }
}

The stack is: [52, 19, 33, 14, 6]

class Stack:
   def __init__(self):
      self.stack = []
   def __str__(self):
      return str(self.stack)
   def push(self, data):
      if data not in self.stack:
         self.stack.append(data)
         return True
      else:
         return False
stk = Stack()
stk.push(1)
stk.push(2)
stk.push(3)
stk.push(4)
stk.push(5)
print("Stack Elements:")
print(stk)

Stack Elements:
[1, 2, 3, 4, 5]

注意- 在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.

例子

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

#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");
   }
}

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

import java.io.*;
import java.util.*; 

// util imports the stack class
public class StackExample {
   public static void main (String[] args) {
      Stack<Integer> stk = new Stack<Integer>();
      
      // Inserting elements into the stack
      stk.push(52);
      stk.push(19);
      stk.push(33);
      stk.push(14);
      stk.push(6);
      System.out.print("The stack is: " + stk);
      
      // Deletion from the stack
      System.out.print("\nThe popped element is: ");
      Integer n = (Integer) stk.pop();
      System.out.print(n);
   }
}

The stack is: [52, 19, 33, 14, 6]
The popped element is: 6

class Stack:
   def __init__(self):
      self.stack = []
   def __str__(self):
      return str(self.stack)
   def push(self, data):
      if data not in self.stack:
         self.stack.append(data)
         return True
      else:
         return False
   def remove(self):
      if len(self.stack) <= 0:
         return ("No element in the Stack")
      else:
         return self.stack.pop()
stk = Stack()
stk.push(1)
stk.push(2)
stk.push(3)
stk.push(4)
stk.push(5)
print("Stack Elements:")
print(stk)
print("----Deletion operation in stack----")
p = stk.remove()
print("The popped element is: " + str(p))
print("Updated Stack:")
print(stk)

Stack Elements:
[1, 2, 3, 4, 5]
----Deletion operation in stack----
The popped element is: 5
Updated Stack:
[1, 2, 3, 4]

注意- 在 Java 中，我们使用内置方法 pop()。

窥视（）

peek ()是一种检索堆栈中最顶层元素的操作，但不删除它。该操作用于借助栈顶指针检查堆栈的状态。

算法

1. START
2. return the element at the top of the stack
3. END

例子

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

#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");
   }
}

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

import java.io.*;
import java.util.*; 

// util imports the stack class
public class StackExample {
   public static void main (String[] args) {
      Stack<Integer> stk = new Stack<Integer>();
      
      // inserting elements into the stack
      stk.push(52);
      stk.push(19);
      stk.push(33);
      stk.push(14);
      stk.push(6);
      System.out.print("The stack is: " + stk);
      Integer pos = (Integer) stk.peek();
      System.out.print("\nThe element found is " + pos);
   }
}

The stack is: [52, 19, 33, 14, 6]
The element found is 6

class Stack:
   def __init__(self):
      self.stack = []
   def __str__(self):
      return str(self.stack)
   def push(self, data):
      if data not in self.stack:
         self.stack.append(data)
         return True
      else:
         return False
   # Use peek to look at the top of the stack
   def peek(self):
      return self.stack[-1]
stk = Stack()
stk.push(1)
stk.push(2)
stk.push(3)
stk.push(4)
stk.push(5)
print("Stack Elements:")
print(stk)
print("topmost element: ",stk.peek())

Stack Elements:
[1, 2, 3, 4, 5]
topmost element: 5

已满（）

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

例子

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

#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 ()操作验证堆栈是否为空。该操作用于借助栈顶指针来检查堆栈的状态。

算法

1. START
2. If the top value is -1, the stack is empty. Return 1.
3. Otherwise, return 0.
4. END

例子

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

#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

import java.io.*;
import java.util.*; // util imports the stack class
public class StackExample {
   public static void main (String[] args) {
      Stack<Integer> stk = new Stack<Integer>();
      
      // Inserting elements into the stack
      stk.push(52);
      stk.push(19);
      stk.push(33);
      stk.push(14);
      stk.push(6);
      System.out.println("Stack empty? "+ stk.isEmpty());
   }
}

Stack empty? false

#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

完成实施

#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

import java.io.*;
import java.util.*; // util imports the stack class
public class StackExample {
   public static void main (String[] args) {
      Stack<Integer> stk = new Stack<Integer>();
      // inserting elements into the stack
      stk.push(52);
      stk.push(19);
      stk.push(33);
      stk.push(14);
      stk.push(6);
      System.out.print("The stack is: " + stk);
      // deletion from the stack
      System.out.print("\nThe popped element is: ");
      Integer n = (Integer) stk.pop();
      System.out.print(n);
      // searching for an element in the stack
      Integer pos = (Integer) stk.search(19);
      if(pos == -1)
         System.out.print("\nThe element 19 not found in stack");
      else
         System.out.print("\nThe element 19 is found at " + pos);
   }
}

The stack is: [52, 19, 33, 14, 6]
The popped element is: 6
The element 19 is found at 3

class Stack:
   def __init__(self):
      self.stack = []
   def add(self, data):
      if data not in self.stack:
         self.stack.append(data)
         return True
      else:
         return False
# Use peek to look at the top of the stack
   def peek(self):
      return self.stack[-1]
# Use list pop method to remove element
   def remove(self):
      if len(self.stack) <= 0:
         return ("No element in the Stack")
      else:
         return self.stack.pop()
stk = Stack()
stk.add(1)
stk.add(2)
stk.add(3)
stk.add(4)
stk.add(5)
print("topmost element: ",stk.peek())
print("----Deletion operation in stack----")
stk.remove()
stk.peek()
print("topmost element after deletion: ",stk.peek())

topmost element: 5
----Deletion operation in stack----
topmost element after deletion: 4