陣列實現堆疊


在陣列實現中,通過使用陣列形成堆疊。 關於堆疊的所有操作都是使用陣列執行的。 下面來看看如何使用陣列資料結構在堆疊上實現每個操作。

1. 在堆疊中新增元素(推播操作)

將元素新增到堆疊頂部稱為推播操作。推播操作包括以下兩個步驟。
增加變數top,使其現在可以參照到下一個記憶體位置。
在頂部位置新增元素,這個操作稱為在堆疊頂部新增新元素。
當嘗試將一個元素插入一個完全填充的堆疊時,堆疊溢位,因此,main()函式必須始終避免堆疊溢位條件。

演算法

開始   
    if top = n 那麼堆疊滿   
    top = top + 1  
    stack (top) : = item;  
結束

時間複雜度為:o(1)

C語言中推播演算法的實現 -

void push (int val,int n) //n is size of the stack   
{  
    if (top == n ){
        printf("Overflow\n");   
    }else   
    {  
        top = top + 1;   
        stack[top] = val;   
    }   
}

2. 從堆疊中刪除元素(彈出操作)

從堆疊頂部刪除元素稱為彈出操作。 每當從堆疊中刪除一個專案時,變數top的值將增加1。 堆疊的最頂層元素儲存在另一個變數中,然後頂部遞減1。該操作返回作為結果儲存在另一個變數中的已刪除值。

當嘗試從已經空的堆疊中刪除元素時,會發生下溢情況。

演算法

開始
    if top = 0 那麼堆疊為空;   
    item := stack(top);  
    top = top ? 1;  
結束

時間複雜度為:o(1)

使用C語言實現彈出演算法

int pop ()  
{   
    if(top == -1)   
    {  
        printf("Underflow");  
        return 0;  
    }  
    else  
    {  
        return stack[top -- ];   
    }    
}

3. 存取堆疊的每個元素(Peek操作)

Peek操作涉及返回堆疊頂部存在的元素但不刪除它。如果嘗試返回已經空堆疊中的頂部元素,則可能發生下溢情況。

演算法:

開始
    if top = -1 那麼堆疊   
    item = stack[top]   
    return item  
結束

時間複雜度為:o(1)

用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");
    while (choice != 4)
    {
        printf("Chose one from the below options...\n");
        printf("1.Push\n2.Pop\n3.Show\n4.Exit");
        printf("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("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");
        while (choice != 4) {
            System.out.println("Chose one from the below options...\n");
            System.out.println("1.Push\n2.Pop\n3.Show\n4.Exit");
            System.out.println("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");  
    while(choice != 4)  
    {  
        Console.WriteLine("Chose one from the below options...\n");  
        Console.WriteLine("1.Push\n2.Pop\n3.Show\n4.Exit");  
        Console.WriteLine("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("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");  
    }  
}  
}