「C與指針心得」32. 抽象數據類型-堆棧(動態數組操作)

抽象數據類型(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與指針心得」32. 抽象數據類型-堆棧(動態數組操作)


分享到:


相關文章: