棧的多種C語言實現

標題：棧的多種C語言實現

內容：棧是一種後進先出（LIFO）的數據結構，C語言中可以使用數組、全局變量、指針傳參、引用傳參等方法實現。

作者：MilkCu

概念

棧的定義

我們可以使用下面的結構體來定義棧：

typedef struct stack {
int top;
int key[M];
} stack;

棧的屬性

以棧s為例討論。

s.top指向最新插入的元素。
當棧中包含的元素為s.key[1..s.top]，其中s.key[1]是棧底元素，s.key[s.top]是棧頂元素。

棧的操作

壓入（push）：將數據放在棧頂；

彈出（pop）：返回彈出值，並刪除元素。

棧的狀態

s.top = 0時，棧中不包含任何元素，即棧是空的。

實現

普通數組實現

最簡單的實現方法，不會涉及到結構體的參數傳遞問題。

使用s[0]表示s.top。

# include <stdio.h>
# define M 100
int stackEmpty(int s[]);
void push(int s[], int x);
int pop(int s[]);
int main(void)
{
int s[M];
s[0] = 0;
printf("stackEmpty - %d\n", stackEmpty(s));
push(s, 2);
push(s, 5);
printf("stackEmpty - %d\n", stackEmpty(s));
printf("pop - %d\n", pop(s));
return 0;
}
int stackEmpty(int s[])
{
if(s[0] == 0) {
return 1;
} else {
return 0;
}
}
void push(int s[], int x)
{
s[0]++;
s[s[0]] = x;
}
int pop(int s[])
{
if(s[0] == 0) {
return -1;
} else {
return s[s[0]--];
}
}

指針傳參實現

傳遞參數的時候要用指針，否則不能改變參數的值！

# include <stdio.h>
# define M 100
typedef struct stack {
int top;
int key[M];
} stack;
int stackEmpty(stack s);
void push(stack * s, int x);
int pop(stack * s);
int main(void)
{
stack s;
s.top = 0;
/* 測試代碼 */
push(&s, 2);
push(&s, 3);
printf("pop - %d\n", pop(&s));
printf("stackEmpty - %d", stackEmpty(s));
}
int stackEmpty(stack s)
{
if(s.top == 0) {
return 1;
} else {
return 0;
}
}
void push(stack * sp, int x)
{
sp -> top += 1;
sp -> key[sp -> top] = x;
}
int pop(stack * sp)
{
if(sp -> top == 0) {
return -1;
} else {
sp -> top--;
return sp -> key[sp -> top + 1];
}
}