使用C語言實現資料結構 - 棧

概述

棧是一種資料結構，它只允許在一端進行資料操作。它只允許訪問最後插入的資料。棧也被稱為後進先出 (LIFO) 資料結構，並且入棧和出棧操作以這樣一種方式相關聯：只有最後入棧（新增到棧中）的項才能出棧（從棧中移除）。

棧的表示

在本文中，我們將使用陣列來實現棧。

基本操作

以下是棧的兩個主要操作。

• 入棧 (Push) − 將元素壓入棧頂。

• 出棧 (Pop) − 將元素彈出棧頂。

棧還支援一些其他操作，如下所示。

• 取頂 (Peek) − 獲取棧頂元素。

• 是否已滿 (isFull) − 檢查棧是否已滿。

• 是否為空 (isEmpty) − 檢查棧是否為空。

入棧操作

每當一個元素被壓入棧時，棧會將該元素儲存在儲存區的頂部，並增加頂部索引以供後續使用。如果儲存區已滿，通常會顯示錯誤訊息。

// Operation : Push
// push item on the top of the stack 
void push(int data) {
   if(!isFull()){
      // increment top by 1 and insert data 
      intArray[++top] = data;
   } else {
      printf("Cannot add data. Stack is full.\n");
   }      
}

出棧操作

每當需要從棧中彈出元素時，棧會從儲存區的頂部檢索該元素，並減少頂部索引以供後續使用。

// Operation : Pop
// pop item from the top of the stack 
int pop() {
   //retrieve data and decrement the top by 1
   return intArray[top--];        
}

示例

StackDemo.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

// size of the stack
int size = 8;       

// stack storage
int intArray[8];     

// top of the stack
int top = -1;            

// Operation : Pop
// pop item from the top of the stack 
int pop() {
   //retrieve data and decrement the top by 1
   return intArray[top--];        
}
// Operation : Peek
// view the data at top of the stack 
int peek() {       
   //retrieve data from the top
   return intArray[top];
}
//Operation : isFull
//return true if stack is full 
bool isFull(){
   return (top == size-1);
}

// Operation : isEmpty
// return true if stack is empty 
bool isEmpty(){
   return (top == -1);
}
// Operation : Push
// push item on the top of the stack 
void push(int data) {
   if(!isFull()){
      // increment top by 1 and insert data 
      intArray[++top] = data;
   } else {
      printf("Cannot add data. Stack is full.\n");
   }      
}
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");
}

輸出

如果我們編譯並執行上述程式，它將產生以下輸出：

Element at top of the stack: 15
Elements: 
15
12
1
9
5
3
Stack full: false
Stack empty: true