抽象數據類型(ADT)是C程序員不可或缺的工具，這類ADT有鏈表、堆棧、隊列和樹等，前面我們已經討論過了鏈表，接下來我們來學習堆棧、隊列和樹。

所有的ADT都需要確定一件事情–如何獲取內存來存儲值，這裡有三種方案：

1) 靜態數組
2）動態內存分配
3）動態鏈表存儲

本章主要通過動態數組方式來講解堆棧的操作方式，並用上述三種方式分別來實現堆棧的操作。

棧的特點：後進先出(Last in First out –LIFO)
例如向倉庫裡堆放貨品，後放進去的靠近門口，因此也會先拿出去

棧操作：

入棧(push):

將數據保存到棧頂的操作。進入棧操作前，先修改棧頂指針，使其向上移動一個元素位置，然後將數據保存到棧頂指針所指的位置。

出棧(pop)：

將棧頂數據彈出操作，通過修改棧頂指針，使其指向棧中的下一個元素。

棧實現：

1)動態數組操作：

動態數組堆棧在運行時才決定數組的長度,而且需要的話，你可以通過分配一個新的、更大的數組，吧原來數組的元素複製到新數組中，然後刪除原來的數組，從而達到動態數組改變長度的目的。

在你決定使用動態數組時，你需要在由此增加的複雜性和隨之產生的靈活性之間做一番權衡。如果你的數據很少，那麼建議你使用靜態數組，不容易出錯；如果你使用的數組量很大，那麼建議使用動態數組，減少堆內存的不必要浪費。

示例：

stack.h

#ifndef STACK_H
#define STACK_H
#include 
#include 
/*創建棧*/ 

void create_stack(size_t size);
/*創建棧*/
void destory_stack(void);
/*入棧*/
void push(int value);
/*出棧*/
int pop(void);
/*返回棧頂指針*/
int top(void);
/*棧是否為空： TRUE-棧為空; FALSE--棧不為空*/
int is_empty(void);
/*棧是否已滿，TRUE--棧滿; FALSE--棧不滿*/
int is_full(void);
#endif

stack.c

#include "stack.h"
static int *stack;
static size_t stack_size;
static int top_element = -1;
/*創建棧*/
void create_stack(size_t size)
{
 stack_size = size;
 stack = malloc(stack_size * sizeof(int));
 if (stack == NULL)
 {
 printf("create_stack fail\n");
 return;
 }
}
/*銷燬棧*/
void destory_stack(void)
{
 if (stack_size >0)
 {
 stack_size = 0;
 }
 free(stack);
}
/*入棧*/
void push(int value) 

{
 top_element += 1;
 stack[top_element] = value;
}
/*出棧*/
int pop(void)
{
 if(is_empty())
 {
 return -1;
 }
 int temp;
 temp = stack[top_element];
 top_element -= 1;
 return temp;
}
/*返回棧頂指針*/
int top(void)
{
 return stack[top_element];
}
/*棧是否為空： TRUE-棧為空; FALSE--棧不為空*/
int is_empty(void)
{
 return (top_element == -1);
}
/*棧是否已滿，TRUE--棧滿; FALSE--棧不滿*/
int is_full(void)
{
 return top_element == stack_size -1;
}
int main(void)
{
 create_stack(100); /*創建堆棧*/
 push(10); /*入棧*/
 push(11);
 int temp = pop(); /*出棧*/
 printf("temp = %d\n",temp);
 destory_stack(); /*銷燬棧*/
 return 0;
}

輸出：

temp = 11

閱讀更多 大貓玩程序 的文章

關鍵字: C語言 程序員 堆棧