栈的数组实现

在数组实现中, 堆栈是通过使用数组形成的。有关堆栈的所有操作均使用数组执行。让我们看看如何使用数组数据结构在堆栈上实现每个操作。

将元素添加到堆栈（推送操作）

将元素添加到堆栈的顶部称为推入操作。推送操作涉及以下两个步骤。

1. 递增变量Top, 以便它现在可以引用下一个内存位置。
2. 在顶部递增的位置添加元素。这称为在堆栈顶部添加新元素。

当我们尝试将一个元素插入一个完全填充的堆栈中时, 堆栈溢出了, 因此, 我们的main函数必须始终避免堆栈溢出的情况。

算法：

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