棧是限定僅在表尾進行插入或刪除的操作.因此,對於棧來說,表尾端有其特殊的含義,稱為棧頂(top),相應的表頭端稱為棧底(bottom).不含元素的空表稱為空棧.
棧的修改是按照後進先出的原則進行的,又成為LIFO結構.插入元素的操作稱為入棧,刪除棧頂元素的操作成為出棧.
使用一組連續的存儲單元依次存放自棧底到棧頂的數據元素,同時附設指針top指示棧頂元素在順序棧中的位置.
一般實現方法:
先為 棧分配一個基本容量,然後在應用過程中,當棧的空間不夠使用時在逐段增大.
順序棧的定義如下:
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}
其中stacksize指示棧的當前可使用的最大容量,base稱為棧底指針,始終指向棧底位置.top為棧頂指針,當top=base時,棧為空.當base=NULL時,棧結構不存在.
鏈式棧就是一個特殊的只能對第一個結點進行操作的單鏈表.這裡不在做過多的論述
基本上參考嚴蔚敏老師的《數據結構》（c語言版）代碼實現
/* 接口的定義文件 */
/* stack 順序存儲的結構定義和接口聲明 */
/* 存儲空間的初始分配量 */
#define STACK_INIT_SIZE 100
/* 存儲空間分配增量 */
#define STACKINCREMENT 10
#define true 1
#define false 0
/* 定義數據類型 */
typedef int datatype;
/* 棧的數據結構定義 */
typedef struct{
/* 在構造之前和銷毀之後base的值為NULL */
datatype *base;
/* 棧頂指針 */
datatype *top;
/* 當前已分配的存儲空間 */
int stacksize;
}stack,*sp_stack;
/* 基本操作的函數原型說明 */
/* 構造一個空棧s */
sp_stack stack_init(sp_stack s);
/* 銷毀棧s,s不再存在 */
void stack_destroy(sp_stack s);
/* 置棧為空 */
void stack_clear(sp_stack s);
/* 判斷棧是否為空
* 若為空,返回true
* 否則返回false
*/
int stack_empty(sp_stack s);
/* 返回棧中元素的個數 */
int stack_length(sp_stack s);
/* 若棧不空
* 用e返回s的棧頂元素,並返回true
* 否則返回false
*/
int get_top(sp_stack s, datatype *e);
/* 插入元素e為新的棧頂元素 */
void push(sp_stack s, datatype e);
/* 若棧不空
* 刪除棧頂元素,用e返回其值,並返回true
* 否則返回false
*/
int pop(sp_stack s, datatype *e);
/* 從棧底到棧頂依次對棧中每個元素調用visit()函數.
* 一旦visit()失敗,則操作失敗
*/
void stack_traverse(sp_stack s, void(*visit)(sp_stack));
/* 遍歷處理函數 */
void visit(sp_stack s);
/* 接口的實現文件 */
#include
#include
#include"sp_stack.h"
sp_stack stack_init(sp_stack s)
{
/* 申請內存空間 */
s -> base = (datatype *)malloc(sizeof(datatype) * STACK_INIT_SIZE);
/* 申請內存失敗 */
if (!s -> base)
exit(0);
s -> stacksize = STACK_INIT_SIZE;
s -> top = s -> base;
return s;
}
void stack_destory(sp_stack s)
{
free(s -> base);
free(s);
s = NULL;
}
void stack_clear(sp_stack s)
{
s -> top = s -> base;
}
int stack_length(sp_stack s)
{
int l = s -> top - s -> base;
return l;
}
int get_top(sp_stack s, datatype *e)
{
if (s -> top == s -> base)
return false;
*e = *(s -> top);
return true;
}
void push(sp_stack s, datatype e)
{
/* 內存已滿 */
if ( (s -> top - s -> base) >= s -> stacksize)
{
s -> base = (datatype *) realloc(s -> base, (s -> stacksize + STACKINCREMENT) * sizeof(datatype));
/* 申請內存失敗 */
if (!s -> base)
exit(0);
s -> top = s -> base + s -> stacksize;
s -> stacksize = s -> stacksize + STACKINCREMENT;
}
s -> top = s -> top + 1;
*s -> top = e;
}
int pop(sp_stack s, datatype *e)
{
/* 棧為空 */
if(s -> top == s -> base)
return false;
*e = *s -> top;
s -> top = s -> top - 1;
return true;
}
void stack_traverse(sp_stack s, void (*visit)(sp_stack s))
{
visit(s);
}
void visit(sp_stack s)
{
datatype *temp = s -> base + 1;
while(true)
{
if(temp <= s -> top)
{
printf("%d ", *temp);
temp = temp + 1;
}
else
{
printf("\n");
break;
}
}
}
int main()
{
sp_stack s = (sp_stack)malloc(sizeof(stack));
s = stack_init(s);
printf("length:%d\n", stack_length(s));
push(s, 1);
printf("length:%d\n", stack_length(s));
push(s, 2);
printf("length:%d\n", stack_length(s));
push(s, 3);
printf("length:%d\n", stack_length(s));
stack_traverse(s, visit);
datatype *e;
get_top(s, e);
printf("get_top:%d\n", *e);
stack_traverse(s, visit);
pop(s, e);
printf("pop:%d\n", *e);
stack_clear(s);
printf("length:%d\n", stack_length(s));
stack_traverse(s, visit);
}
參考嚴蔚敏老師的《數據結構》（c語言版）的接口，接口的實現有自己完成。
/* 接口的定義文件 */
/* stack 鏈式存儲的結構定義和接口聲明 */
#define true 1
#define false 0
/* 定義數據類型 */
typedef int datatype;
/* 棧的數據結構定義 */
typedef struct stack{
/* 數據域 */
datatype data;
/* 指針域 */
struct stack *next;
}stack,*lp_stack;
/* 基本操作的函數原型說明 */
/* 構造一個空棧s */
lp_stack stack_init(lp_stack s);
/* 銷毀棧s,s不再存在 */
void stack_destroy(lp_stack s);
/* 置棧為空 */
void stack_clear(lp_stack s);
/* 判斷棧是否為空
* 若為空,返回true
* 否則返回false
*/
int stack_empty(lp_stack s);
/* 返回棧中元素的個數 */
int stack_length(lp_stack s);
/* 若棧不空
* 用e返回s的棧頂元素,並返回true
* 否則返回false
*/
int get_top(lp_stack s, datatype *e);
/* 插入元素e為新的棧頂元素 */
void push(lp_stack s, datatype e);
/* 若棧不空
* 刪除棧頂元素,用e返回其值,並返回true
* 否則返回false
*/
int pop(lp_stack s, datatype *e);
/* 從棧底到棧頂依次對棧中每個元素調用visit()函數.
* 一旦visit()失敗,則操作失敗
*/
void stack_traverse(lp_stack s, void(*visit)(lp_stack));
/* 遍歷處理函數 */
void visit(lp_stack s);
/* 接口的實現文件 */
#include
#include
#include"lp_stack.h"
lp_stack stack_init(lp_stack s)
{
s -> next = NULL;
return s;
}
void stack_destroy(lp_stack s)
{
lp_stack temp = s;
while(s)
{
s = s -> next;
free(temp);
temp = s;
}
}
void stack_clear(lp_stack s)
{
lp_stack temp = s -> next;
while(s -> next)
{
s -> next = s -> next -> next;
free(temp);
temp = s -> next;
}
}
int stack_empty(lp_stack s)
{
if(s -> next = NULL)
return true;
return false;
}
int stack_length(lp_stack s)
{
/* 棧的當前結點 */
lp_stack top = s -> next;
/* 計數器 */
int count = 0;
while(top)
{
count += 1;
top = top -> next;
}
return count;
}
int get_top(lp_stack s, datatype *e)
{
if (s -> next == NULL)
return false;
*e = s -> next -> data;
return true;
}
void push(lp_stack s, datatype e)
{
lp_stack new_node = (lp_stack)malloc(sizeof(stack));
new_node -> data = e;
new_node -> next = s -> next;
s -> next = new_node;
}
int pop(lp_stack s, datatype *e)
{
if(s -> next == NULL)
return false;
*e = s -> next -> data;
lp_stack node = s -> next;
s -> next = s -> next -> next;
free(node);
return true;
}
void stack_traverse(lp_stack s, void (*visit)(lp_stack))
{
visit(s);
}
void visit(lp_stack s)
{
lp_stack node = s -> next;
while(node)
{
printf("%d ",node -> data);
node = node -> next;
}
}
int main()
{
lp_stack s = (lp_stack)malloc(sizeof(stack));
s = stack_init(s);
printf("length:%d\n", stack_length(s));
push(s, 1);
printf("length:%d\n", stack_length(s));
push(s, 2);
printf("length:%d\n", stack_length(s));
push(s, 3);
printf("length:%d\n", stack_length(s));
stack_traverse(s, visit);
datatype *e;
get_top(s, e);
printf("get_top:%d\n", *e);
stack_traverse(s, visit);
pop(s, e);
printf("pop:%d\n", *e);
stack_traverse(s, visit);
stack_clear(s);
printf("length:%d\n", stack_length(s));
stack_traverse(s, visit);
}
