棧資料結構

上一頁
下一頁

什麼是棧？

棧是一種線性資料結構，其中元素按照LIFO（後進先出）原則儲存，最後一個插入的元素將是第一個被刪除的元素。棧是一種抽象資料型別（ADT），在大多數程式語言中被廣泛使用。它之所以被稱為棧，是因為它的操作類似於現實世界的棧，例如——一副撲克牌或一堆盤子等。

stack example

棧被認為是一種複雜的資料結構，因為它使用其他資料結構來實現，例如陣列、連結串列等。

棧表示

棧只允許在一端進行所有資料操作。在任何給定時間，我們只能訪問棧的頂部元素。

下圖描述了一個棧及其操作：

Stack Representation

棧可以透過陣列、結構體、指標和連結串列來實現。棧可以是固定大小的，也可以具有動態調整大小的功能。在這裡，我們將使用陣列來實現棧，這使得它成為一個固定大小的棧實現。

棧的基本操作

棧操作通常用於初始化、使用和取消初始化棧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.

示例

以下是此操作在各種程式語言中的實現：

C C++ Java Python
#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");
   }
   return data;
}

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

public class Demo{
final static int MAXSIZE = 8;
static int stack[] = new int[MAXSIZE];
static int top = -1;
public static int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}
public static int push(int data){
   if(isfull() != 1) {
      top = top + 1;
      stack[top] = data;
   } else {
      System.out.print("Could not insert data, Stack is full.\n");
   }
   return data;
}
public static void main(String[] args){
   int i;
   push(44);
   push(10);
   push(62);
   push(123);
   push(15);
   System.out.print("\nStack Elements: ");
   // print stack data
   for(i = 0; i < MAXSIZE; i++) {
      System.out.print(stack[i] + " ");
   }
  }
}

輸出

Stack Elements: 44 10 62 123 15 0 0 0 

MAXSIZE = 8
stack = [0] * MAXSIZE
top = -1
def isfull():
    if(top == MAXSIZE):
        return 1
    else:
        return 0
def push(data):
    global top
    if(isfull() != 1):
        top = top + 1
        stack[top] = data
    else:
        print("Could not insert data, Stack is full.")
    return data
push(44)
push(10)
push(62)
push(123)
push(15)
print("Stack Elements: ")
for i in range(MAXSIZE):
    print(stack[i], end = " ")

輸出

Stack Elements: 
44 10 62 123 15 0 0 0

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

示例

以下是此操作在各種程式語言中的實現：

C C++ Java Python
#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");
   }
   return data;
}

/* 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");
   }
   return data;
}

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

public class Demo{
final static int MAXSIZE = 8;
public static int stack[] = new int[MAXSIZE];
public static int top = -1;
/* Check if the stack is empty */
public static int isempty(){
   if(top == -1)
      return 1;
   else
      return 0;
}
/* Check if the stack is full*/
public static int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}
/* Function to delete from the stack */
public static int pop(){
   int data = 0;
   if(isempty() != 1) {
      data = stack[top];
      top = top - 1;
      return data;
   } else {
      System.out.print("Could not retrieve data, Stack is empty.");
   }
   return data;
}
/* Function to insert into the stack */
public static int push(int data){
   if(isfull() != 1) {
      top = top + 1;
      stack[top] = data;
   } else {
      System.out.print("\nCould not insert data, Stack is full.\n");
   }
   return data;
}
/* Main function */
public static void main(String[] args){
   push(44);
   push(10);
   push(62);
   push(123);
   push(15);
   System.out.print("Stack Elements: ");
   // print stack data
   for(int i = 0; i < MAXSIZE; i++) {
      System.out.print(stack[i] + " ");
   }
   
   /*printf("Element at top of the stack: %d\n" ,peek());*/
   System.out.print("\nElements popped: ");

   // print stack data
   while(isempty() != 1) {
      int data = pop();
      System.out.print(data + " ");
   }
  }
}

輸出

Stack Elements: 44 10 62 123 15 0 0 0 
Elements popped: 15 123 62 10 44 

MAXSIZE = 8
stack = [0] * MAXSIZE
top = -1
def isempty():
    if(top == -1):
        return 1
    else:
        return 0
def isfull():
    if(top == MAXSIZE):
        return 1
    else:
        return 0
def pop():
    global top
    data = 0
    if(isempty() != 1):
        data = stack[top]
        top = top - 1
        return data
    else:
        print("Could not retrieve data, Stack is empty.")
    return data
def push(data):
    global top
    if(isfull() != 1):
        top = top + 1
        stack[top] = data
    else:
        print("\nCould not insert data, Stack is full.")
    return data
push(44);
push(10);
push(62);
push(123);
push(15);
print("Stack Elements: ")
for i in range (MAXSIZE):
    print(stack[i], end = " ")
print("\nElements popped: ")
while(isempty() != 1):
    data = pop()
    print(data, end = " ")

輸出

Stack Elements: 
44 10 62 123 15 0 0 0 
Elements popped: 
15 123 62 10 44

注意 - 在Java中，我們使用內建方法pop()。

從棧中檢索最頂部的元素：peek()

peek()是一種操作，用於檢索棧中最頂部的元素，而無需將其刪除。此操作用於透過頂部指標檢查棧的狀態。

演算法

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

示例

以下是此操作在各種程式語言中的實現：

C C++ Java Python
#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");
   }
   return data;
}

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

public class Demo{
final static int MAXSIZE = 8;
public static int stack[] = new int[MAXSIZE];
public static int top = -1;
/* Check if the stack is full */
public static int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}

/* Function to return the topmost element in the stack */
public static int peek(){
   return stack[top];
}

/* Function to insert into the stack */
public static int push(int data){
   if(isfull() != 1) {
      top = top + 1;
      stack[top] = data;
   } else {
      System.out.print("Could not insert data, Stack is full.");
   }
   return data;
}

/* Main function */
public static void main(String[] args){
   push(44);
   push(10);
   push(62);
   push(123);
   push(15);
   System.out.print("Stack Elements: ");

   // print stack data
   for(int i = 0; i < MAXSIZE; i++) {
      System.out.print(stack[i] + " ");
   }
   System.out.print("\nElement at top of the stack: " + peek());
  }
}

輸出

Stack Elements: 44 10 62 123 15 0 0 0 
Element at top of the stack: 15

MAXSIZE = 8;
stack = [0] * MAXSIZE
top = -1
def isfull():
    if(top == MAXSIZE):
        return 1
    else:
        return 0
def peek():
    return stack[top]
def push(data):
    global top
    if(isfull() != 1):
        top = top + 1
        stack[top] = data
    else:
        print("Could not insert data, Stack is full.")
    return data
push(44);
push(10);
push(62);
push(123);
push(15);
print("Stack Elements: ")
for i in range(MAXSIZE):
    print(stack[i], end = " ")
print("\nElement at top of the stack: ", peek())

輸出

Stack Elements: 
44 10 62 123 15 0 0 0 
Element at top of the stack:  15

驗證棧是否已滿：isFull()

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

示例

以下是此操作在各種程式語言中的實現：

C C++ Java Python
#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()

isEmpty()操作驗證棧是否為空。此操作用於透過頂部指標檢查棧的狀態。

演算法

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

示例

以下是此操作在各種程式語言中的實現：

C C++ Java Python
#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

public class Demo{
final static int MAXSIZE = 8;
static int stack[] = new int[MAXSIZE];
static int top = -1;

/* Check if the stack is empty */
public static int isempty(){
   if(top == -1)
      return 1;
   else
      return 0;
}

/* Main function */
public static void main(String[] args){
    boolean res = isempty() == 1 ? true : false;
    System.out.print("Stack empty: " + res);
 }
}

輸出

Stack empty: true

#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

棧完整實現

以下是棧在各種程式語言中的完整實現：

C C++ Java Python
#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

public class Demo{
final static int MAXSIZE = 8;
public static int stack[] = new int[MAXSIZE];
public static int top = -1;
/* Check if the stack is empty */
public static int isempty(){
   if(top == -1)
      return 1;
   else
      return 0;
}
/* Check if the stack is full */
public static int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}
/* Function to return the topmost element in the stack */
public static int peek(){
   return stack[top];
}
/* Function to delete from the stack */
public static int pop(){
   int data = 0;
   if(isempty() != 1) {
      data = stack[top];
      top = top - 1;
      return data;
   } else
      System.out.print("Could not retrieve data, Stack is empty.");
    return data;
}
/* Function to insert into the stack */
public static int push(int data){
   if(isfull() != 1) {
      top = top + 1;
      stack[top] = data;
   } else
      System.out.print("Could not insert data, Stack is full.");
    return data;
}
/* Main function */
public static void main(String[] args){
   push(44);
   push(10);
   push(62);
   push(123);
   push(15);
   System.out.print("Element at top of the stack: " + peek());
   System.out.print("\nElements: ");
   // print stack data
   while(isempty() != 1) {
      int data = pop();
      System.out.print(data + " ");
   }
   boolean res1 = isfull() == 1 ? true : false;
   boolean res2 = isempty() == 1 ? true : false;
   System.out.print("\nStack full: " + res1);
   System.out.print("\nStack empty: " + res2);
   }
}

輸出

Element at top of the stack: 15
Elements: 15 123 62 10 44 
Stack full: false
Stack empty: true

MAXSIZE = 8
stack = [0] * MAXSIZE
top = -1;
def isempty():
    if(top == -1):
        return 1
    else:
        return 0
def isfull():
    if(top == MAXSIZE):
        return 1
    else:
        return 0
def peek():
    return stack[top]
def pop():
    global data, top
    if(isempty() != 1):
        data = stack[top];
        top = top - 1;
        return data
    else:
        print("Could not retrieve data, Stack is empty.")
    return data
def push(data):
    global top
    if(isfull() != 1):
        top = top + 1
        stack[top] = data
    else:
        print("Could not insert data, Stack is full.")
    return data
push(44)
push(10)
push(62)
push(123)
push(15)
print("Element at top of the stack: ", peek())
print("Elements: ")
while(isempty() != 1):
    data = pop();
    print(data, end = " ")
print("\nStack full: ",bool({True: 1, False: 0} [isfull() == 1]))
print("Stack empty: ",bool({True: 1, False: 0} [isempty() == 1]))

輸出

Element at top of the stack:  15
Elements: 
15 123 62 10 44 
Stack full:  False
Stack empty:  True

C語言中的棧實現

點選檢視使用C語言實現的棧程式的實現

列印頁面
上一頁
下一頁
廣告