在数组实现中, 堆栈是通过使用数组形成的。有关堆栈的所有操作均使用数组执行。让我们看看如何使用数组数据结构在堆栈上实现每个操作。
将元素添加到堆栈（推送操作）
【栈的数组实现】将元素添加到堆栈的顶部称为推入操作。推送操作涉及以下两个步骤。
- 递增变量Top, 以便它现在可以引用下一个内存位置。
- 在顶部递增的位置添加元素。这称为在堆栈顶部添加新元素。
算法：
begin
if top = n then stack full
top = top + 1
stack (top) : = item;
end时间复杂度：o（1）
C语言中推算法的实现
void push (int val, int n) //n is size of the stack
{
if (top == n )
printf("\n Overflow");
else
{
top = top +1;
stack[top] = val;
}
}从堆栈中删除元素（弹出操作）
从堆栈顶部删除一个元素称为弹出操作。每当从堆栈中删除一项时, 变量top的值将增加1。堆栈的最上面的元素存储在另一个变量中, 然后将最上面的元素递减1。该操作返回存储在另一个变量中的已删除值作为结果。
当我们尝试从一个已经空的堆栈中删除一个元素时, 就会发生下溢情况。
算法：
begin
if top = 0 then stack empty;
item := stack(top);
top = top - 1;
end;
时间复杂度：o（1）
使用C语言实现POP算法
int pop ()
{
if(top == -1)
{
printf("Underflow");
return 0;
}
else
{
return stack[top - - ];
}
}访问堆栈的每个元素（Peek操作）
窥视操作涉及返回存在于堆栈顶部的元素而不删除它。如果我们尝试在已经为空的堆栈中返回顶部元素, 则会发生下溢情况。
算法：
PEEK（堆栈, 顶部）
Begin
if top = -1 then stack empty
item = stack[top]
return item
End时间复杂度：o（n）
C语言中Peek算法的实现
int peek()
{
if (top == -1)
{
printf("Underflow");
return 0;
}
else
{
return stack [top];
}
}C程序
#include <
stdio.h>
int stack[100], i, j, choice=0, n, top=-1;
void push();
void pop();
void show();
void main ()
{
printf("Enter the number of elements in the stack ");
scanf("%d", &
n);
printf("*********Stack operations using array*********");
printf("\n----------------------------------------------\n");
while(choice != 4)
{
printf("Chose one from the below options...\n");
printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");
printf("\n Enter your choice \n");
scanf("%d", &
choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
show();
break;
}
case 4:
{
printf("Exiting....");
break;
}
default:
{
printf("Please Enter valid choice ");
}
};
}
} void push ()
{
int val;
if (top == n )
printf("\n Overflow");
else
{
printf("Enter the value?");
scanf("%d", &
val);
top = top +1;
stack[top] = val;
}
} void pop ()
{
if(top == -1)
printf("Underflow");
else
top = top -1;
}
void show()
{
for (i=top;
i>
=0;
i--)
{
printf("%d\n", stack[i]);
}
if(top == -1)
{
printf("Stack is empty");
}
}Java程序
import java.util.Scanner;
class Stack
{
int top;
int maxsize = 10;
int[] arr = new int[maxsize];
boolean isEmpty()
{
return (top <
0);
}
Stack()
{
top = -1;
}
boolean push (Scanner sc)
{
if(top == maxsize-1)
{
System.out.println("Overflow !!");
return false;
}
else
{
System.out.println("Enter Value");
int val = sc.nextInt();
top++;
arr[top]=val;
System.out.println("Item pushed");
return true;
}
}
boolean pop ()
{
if (top == -1)
{
System.out.println("Underflow !!");
return false;
}
else
{
top --;
System.out.println("Item popped");
return true;
}
}
void display ()
{
System.out.println("Printing stack elements .....");
for(int i = top;
i>
=0;
i--)
{
System.out.println(arr[i]);
}
}
}
public class Stack_Operations {
public static void main(String[] args) {
int choice=0;
Scanner sc = new Scanner(System.in);
Stack s = new Stack();
System.out.println("*********Stack operations using array*********\n");
System.out.println("\n------------------------------------------------\n");
while(choice != 4)
{
System.out.println("\nChose one from the below options...\n");
System.out.println("\n1.Push\n2.Pop\n3.Show\n4.Exit");
System.out.println("\n Enter your choice \n");
choice = sc.nextInt();
switch(choice)
{
case 1:
{
s.push(sc);
break;
}
case 2:
{
s.pop();
break;
}
case 3:
{
s.display();
break;
}
case 4:
{
System.out.println("Exiting....");
System.exit(0);
break;
}
default:
{
System.out.println("Please Enter valid choice ");
}
};
}
}
}C＃程序
using System;
public class Stack
{
int top;
int maxsize=10;
int[] arr = new int[10];
public static void Main()
{
Stack st = new Stack();
st.top=-1;
int choice=0;
Console.WriteLine("*********Stack operations using array*********");
Console.WriteLine("\n----------------------------------------------\n");
while(choice != 4)
{
Console.WriteLine("Chose one from the below options...\n");
Console.WriteLine("\n1.Push\n2.Pop\n3.Show\n4.Exit");
Console.WriteLine("\n Enter your choice \n");
choice = Convert.ToInt32(Console.ReadLine());
switch(choice)
{
case 1:
{
st.push();
break;
}
case 2:
{
st.pop();
break;
}
case 3:
{
st.show();
break;
}
case 4:
{
Console.WriteLine("Exiting....");
break;
}
default:
{
Console.WriteLine("Please Enter valid choice ");
break;
}
};
}
} Boolean push ()
{
int val;
if(top == maxsize-1)
{Console.WriteLine("\n Overflow");
return false;
}
else
{
Console.WriteLine("Enter the value?");
val = Convert.ToInt32(Console.ReadLine());
top = top +1;
arr[top] = val;
Console.WriteLine("Item pushed");
return true;
}
} Boolean pop ()
{
if (top == -1)
{
Console.WriteLine("Underflow");
return false;
}
else
{
top = top -1;
Console.WriteLine("Item popped");
return true;
}
}
void show()
{
for (int i=top;
i>
=0;
i--)
{
Console.WriteLine(arr[i]);
}
if(top == -1)
{
Console.WriteLine("Stack is empty");
}
}
}推荐阅读
- 数据结构（图（Graph））
- 数据结构之双链表
- 深度优先搜索（DFS）算法
- 数据结构入门介绍
- 数据结构之结构体
- 数据结构（栈（stack））
- 数据结构（队列（queue））
- 数据结构与算法中的指针
- 数据结构基本概念和主要内容