堆栈是一种抽象数据类型(ADT),通常在大多数编程语言中使用,它被称为堆栈,因为它的行为类似于现实世界中的堆栈,如,一副纸牌或一堆盘子等。

Stack Example

实际堆栈仅允许在一端进行操作。如我们只能从堆栈顶部放置或取出数据。同样堆栈ADT仅允许在一端进行所有数据操作。在任何给定时间,我们只能访问堆栈的顶部元素。

此函数使其成为LIFO数据结构,LIFO代表后进先出。在此首先访问最后放置(插入或添加)的元素。在堆栈术语中,插入操作称为 PUSH 操作,而删除操作称为 POP 操作。

堆栈表示

下图描述了堆栈及其操作-

堆栈表示

堆栈可以通过数组,结构,指针和链表实现,堆栈可以是固定大小的堆栈,也可以具有动态调整大小的感觉。在这里,我们将使用数组来实现堆栈,这使其成为固定大小的堆栈实现。

基本操作

堆栈操作可能涉及初始化堆栈,使用堆栈然后取消初始化。除了这些基本内容,堆栈还用于以下两个主要操作-

  • push()        -  将一个元素压入堆栈。

  • pop()          -  从堆栈中删除元素。

  • peek()        -   获取堆栈的顶部数据元素,而不删除它。

  • isFull()      -   检查堆栈是否已满。

  • isEmpty()  -   检查堆栈是否为空。

peek()  -  函数的算法-

begin procedure peek
   return stack[top]
end procedure

用C编程语言实现peek()函数-

int peek() {
   return stack[top];
}

isfull()  -  函数的算法-

begin procedure isfull

   if top equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

用C编程语言实现isfull()函数-

bool isfull() {
   if(top == MAXSIZE)
      return true;
   else
      return false;
}

isempty()  -  函数的算法-

begin procedure isempty

   if top less than 1
      return true
   else
      return false
   endif
   
end procedure

用C编程语言实现isempty()函数略有不同。我们将top初始化为-1,因为数组中的索引从0开始。因此我们检查top是否小于0或-1以确定堆栈是否为空。

bool isempty() {
   if(top == -1)
      return true;
   else
      return false;
}

Push操作

将新数据元素放入堆栈的进程称为推入操作,推送操作涉及一系列步骤-

  • 步骤1   -  检查堆栈是否已满。

  • 步骤2   -  如果堆栈已满,则会产生错误并退出。

  • 步骤3   -  如果堆栈未满,则将 top 递增以指向下一个空白空间。

  • 步骤4   -  将数据元素添加到顶部指向的堆栈位置。

  • 步骤5   -  返回成功。

Stack 推送操作

如果使用链表实现堆栈,则在步骤3中,我们需要动态分配空间。

PUSH操作算法

推操作的简单算法可以得出如下-

begin procedure push: stack, data

   if stack is full
      return null
   endif
   
   top  top + 1
   stack[top]  data

end procedure

C 中实现此算法非常容易,参见以下代码-

void push(int data) {
   if(!isFull()) {
      top = top + 1;   
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}

Pop操作

在将内容从堆栈中删除的内容称为弹出操作,在pop()操作的数组实现中,实际上未删除数据元素,而是将top递减到堆栈中下一个值。但是在链表实现中,pop()实际上会删除数据元素并重新分配内存空间。

pop操作可能涉及以下步骤-

  • 步骤1   -  检查堆栈是否为空。

  • 步骤2   -  如果堆栈为空,则会产生错误并退出。

  • 步骤3   -  如果堆栈不为空,则访问 top 所指向的数据元素。

  • 步骤4   - 将top的值减小1。

  • 步骤5   - 返回成功。

Stack 弹出操作

POP算法

Pop操作的简单算法可以得出如下:

无涯教程网

链接:https://www.learnfk.comhttps://www.learnfk.com/data-structures-algorithms/stack-algorithm.html

来源:LearnFk无涯教程网

begin procedure pop: stack

   if stack is empty
      return null
   endif
   
   data  stack[top]
   top  top - 1
   return data

end procedure

此算法在C中的实现如下-

int pop(int data) {

   if(!isempty()) {
      data = stack[top];
      top = top - 1;   
      return data;
   } else {
      printf("Could not retrieve data, Stack is empty.\n");
   }
}

C语言代码实现

#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 items on to the stack 
   push(3);
   push(5);
   push(9);
   push(1);
   push(12);
   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:
15
12
1 
9 
5 
3 
Stack full: false
Stack empty: true

祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)

技术教程推荐

推荐系统三十六式 -〔刑无刀〕

程序员的数学基础课 -〔黄申〕

大规模数据处理实战 -〔蔡元楠〕

Kafka核心技术与实战 -〔胡夕〕

软件设计之美 -〔郑晔〕

用户体验设计实战课 -〔相辉〕

程序员的个人财富课 -〔王喆〕

手把手带你搭建推荐系统 -〔黄鸿波〕

AI绘画核心技术与实战 -〔南柯〕

好记忆不如烂笔头。留下您的足迹吧 :)