Introduction
堆疊是一種後進先出的資料結構，常使用陣列或鏈結串列實現，並且堆疊的push以及pop操作都是從top執行。
所謂的後進先出指的是
💡
LAST IN FIRST OUT
就像以下的圖示那樣
Methods
以下為堆疊常見的操作
Push：加入資料到堆疊裡Pop：刪除top變數所指的值isEmpty：檢查堆疊是否是空的Peek：取得top變數所指的值
Time Complexity
| Operation | Time Complexity | Worst Time Complexity | Space Complexity |
| Push | O(1) | O(n) | O(1) |
| Pop | O(1) | O(n) | O(1) |
| Peek | O(1) | O(1) | O(1) |
| isempty | O(1) | O(1) | O(1) |
Stack Errors
有兩種情況會導致堆疊發生錯誤
Underflow：當要pop資料的堆疊是一個空堆疊的話，就會發生Underflow錯誤，應該要用
isEmpty()函數來確保空堆疊不會執行刪除的動作Overflow：如果用陣列實作的話，會因為指定了有限大小，而導致記憶體不足發生Overflow錯誤
Stack Implementation
陣列實作：在最壞的情況下陣列的速度較慢，但如果不在乎每個操作的時間，那麼陣列的整體性能更好
鏈結串列實作：鏈結串列在最壞的情況下會更好，但由於執行的分配數量，整體運行時可能更差
Array Implementation of the Stacks
堆疊的結構定義
Push()
判斷堆疊是否已滿
如果未滿就先把top++，因為top預設為-1
如果以滿則顯示訊息
Pop()
先判斷堆疊是否已空
如果有資料就利用
top--刪除資料如果是空的就顯示訊息
isEmpty()
如果top等於-1代表堆疊為空
Peek()
如果堆疊為空顯示訊息否則回傳top值
完整程式碼
#include <stdio.h>
#include <time.h>
#define MAX 10
void pushFunction(void); /* 新增函數 */
void popFunction(void); /* 刪除函數 */
void listFunction(void); /* 輸出函數 */
int isEmpty(void);
int clear();
int isfull();
void peek();
void add();
void sub();
void mult();
int item[MAX]; /* 堆疊陣列 */
int top = -1; /* top的起始值為-1 */
// 函數開始執行的時間
clock_t start;
// 函數結束執行的時間
clock_t end;
int main()
{
int option;
while (1) {
printf("\n *****************************\n");
printf(" <1> insert (push)\n");
printf(" <2> delete (pop)\n");
printf(" <3> list\n");
printf(" <4> empty\n");
printf(" <5> clear\n");
printf(" <6> peek\n");
printf(" <7> full\n");
printf(" <8> add\n");
printf(" <9> sub\n");
printf(" <10> mult\n");
printf(" <11> quit\n");
printf(" *****************************\n");
printf(" Please enter your choice...");
scanf_s("%d", &option);
switch (option) {
case 1:
pushFunction();
break;
case 2:
popFunction();
break;
case 3:
listFunction();
break;
case 4:
printf("Is stack empty?: %s\n", isEmpty() ? "Yes" : "No");
break;
case 5:
clear();
printf("Stack is now empty.\n");
break;
case 6:
peek();
break;
case 7:
if (isfull())
printf("Stack is full\n");
else
printf("Stack is not full\n");
break;
case 8:
add();
break;
case 9:
sub();
break;
case 10:
mult();
break;
case 11:
printf("\n");
return 0;
}
}
}
void pushFunction()
{
if (top >= MAX - 1) /* 當堆疊已滿，則顯示錯誤 */
printf("\n\nStack is full !\n");
else {
top++;
printf("\n\n Please enter item to insert: ");
scanf_s("%d", &item[top]);
}
}
void popFunction(void)
{
start = clock();
if (top < 0) /* 當堆疊沒有資料存在，則顯示錯誤 */
printf("\n\n No item, stack is empty !\n");
else {
printf("\n\n Item %d deleted\n", item[top]);
item[top--];
}
end = clock();
double cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Function execution time: %f seconds\n", cpu_time_used);
}
void listFunction(void)
{
start = clock();
int count = 0, i;
if (top < 0)
printf("\n\n No item, stack is empty\n");
else {
printf("\n\n ITEM\n");
printf(" ------------------\n");
for (i = 0; i <= top; i++) {
printf(" %-20d\n", item[i]);
count++;
}
printf(" ------------------\n");
printf(" Total item: %d\n", count);
}
end = clock();
double cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Function execution time: %f seconds\n", cpu_time_used);
}
int isEmpty(void) {
start = clock();
if (top == -1)
{
return 1;
}
else
{
return 0;
}
end = clock();
double cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Function execution time: %f seconds\n", cpu_time_used);
}
int clear() {
start = clock();
return top = -1;
end = clock();
double cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Function execution time: %f seconds\n", cpu_time_used);
}
int isfull() {
start = clock();
if (top == MAX - 1)
{
return 1;
}
else
{
return 0;
}
end = clock();
double cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Function execution time: %f seconds\n", cpu_time_used);
}
void peek() {
start = clock();
if (isEmpty())
{
printf("\nStack is empty\n");
return;
}
else
{
printf("\nTop element is: %d", item[top]);
}
end = clock();
double cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Function execution time: %f seconds\n", cpu_time_used);
}
void add() {
start = clock();
if (isEmpty())
{
printf("\nStack is empty\n");
return;
}
else
{
int a = item[top--];
int b = item[top--];
int c = a + b;
item[++top] = c;
printf("\n c is: %d", item[top]);
}
end = clock();
double cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("\nFunction execution time: %f seconds\n", cpu_time_used);
}
void sub() {
start = clock();
if (isEmpty())
{
printf("\nStack is empty\n");
return;
}
else
{
int a = item[top--];
int b = item[top--];
int c = a - b;
item[++top] = c;
printf("\n c is: %d", item[top]);
}
end = clock();
double cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("\nFunction execution time: %f seconds\n", cpu_time_used);
}
void mult() {
start = clock();
if (isEmpty())
{
printf("\nStack is empty\n");
return;
}
else
{
int a = item[top--];
int b = item[top--];
int c = a * b;
item[++top] = c;
printf("\n c is: %d", item[top]);
}
end = clock();
double cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("\nFunction execution time: %f seconds\n", cpu_time_used);
}
Linked list Implementation of the Stacks
堆疊的結構定義
Push()
Pop()
isEmpty()
Peek()
完整的程式碼
#include <stdio.h>
#include <stdlib.h>
struct stack
{
int data;
struct stack* next;
};
struct stack* top = NULL;
void push(int data) {
struct stack* ptr = (struct stack*)malloc(sizeof(struct stack));
ptr->data = data;
ptr->next = top;
top = ptr;
}
void pop() {
if (top == NULL)
{
printf("\nStack is empty\n");
return;
}
int data = top->data;
top = top->next;
printf("\n%d is popped from stack\n", data);
}
void display() {
if (top == NULL)
{
printf("\nStack is empty\n");
return;
}
struct stack* temp = top;
printf("\nStack is: ");
while (temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int peek() {
if (top == NULL)
{
printf("\nStack is empty\n");
}
else
{
return top->data;
}
}
int count() {
struct stack* temp = top;
int count = 0;
while (temp != NULL)
{
count++;
temp = temp->next;
}
return count;
}
void removeMiddle(int mid, int counter) {
if (counter == mid)
{
printf("\n Delete middle element : %d", peek());
// Delete middle node
pop();
}
else if (counter < mid && top != NULL)
{
// When stack not empty and counter is less than middle position
// Get top element
int element = peek();
// Remove top element
pop();
// Recursively finding the middle element
removeMiddle(mid, counter + 1);
// Add element in stack
push(element);
}
}
void deleteMiddle() {
if (top == NULL)
{
printf("\n Stack Is Empty \n");
}
else
{
int mid = count() / 2;
removeMiddle(mid, 0);
}
}
void deleteNodes(int element) {
struct stack* auxiliary;
int data = 0;
// Executing the loop until when actual stack element are not empty
while (top != NULL)
{
// Get the top element of actual stack
data = peek();
// Remove top of current actual stack
pop();
if (data != element)
{
// Add data to auxiliary stack
push(data);
}
}
}
void deleteEven() {
if (top != NULL)
{
// When stack not empty
// Get top element
int element = peek();
// Remove top element
pop();
deleteEven();
if (element % 2 != 0)
{
// Add odd element in stack
push(element);
}
}
}
int main() {
int choice;
while (1)
{
printf("\n1. Push");
printf("\n2. Pop");
printf("\n3. Display");
printf("\n4. Peek");
printf("\n5. Count");
printf("\n6. Delete middle");
printf("\n7. Delete all even");
printf("\n8. Exit");
printf("\n\nEnter your choice: ");
scanf_s("%d", &choice);
switch (choice)
{
case 1:
printf("\nEnter data: ");
int data;
scanf_s("%d", &data);
push(data);
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
printf("\nTop element is: %d", peek());
break;
case 5:
printf("\nCount is: %d", count());
break;
case 6:
deleteMiddle();
break;
case 7:
deleteEven();
break;
case 8:
return 0;
default:
break;
}
}
}
堆疊的優點：
簡單易懂：堆疊的操作相對簡單，只需要關注頂端元素即可，因此易於理解和實現。
快速操作：push和pop操作的時間複雜度都是O(1)，即使在大型堆疊中，這些操作也非常快速。
支持遞迴：堆疊結構在遞迴演算法的實現中起著關鍵作用，遞迴函式的呼叫和返回可以使用堆疊來管理。
堆疊的缺點：
容量有限：堆疊的容量有限，當元素個數超過容量時，可能會出現stack overflow的錯誤。
不允許隨機存取：堆疊只能在頂端進行push和pop操作，無法直接訪問或修改其他位置的元素。若需要存取堆疊中間的元素，必須先將其pop至所需位置，然後再重新push。