スタックとは，逐次入出力が繰り返されるデータを一時的に貯えるためのデータ構造である。なお，英語でスタック(stack)とは，干草やお皿などが整然と積み重なったもののことを言う。
スタックにデータを追加することを push あるいは push down と言い，スタックからデータを取り出すことを pop あるいは pop up と言う。 スタックへのデータの追加，取り出しは次のように行われる。
スタックから一つデータを取り出すとき，それは残っているデータの中で一番最後に追加したデータである。このようなデータの追加取出しの方法を「後入れ先出し法，Last In First Out (LIFO)」 と呼ぶことがある。
スタックを用いるのは「新しい仕事が来ると，今までの仕事はひとまず置いておき，新しい仕事から片付けて行く」という方針で動くプログラムを作るときである。
次のようなコーディングで，とりあえず，スタックの機能をなすものを構築できる。
まずは，マクロ定数の定義とスタック本体の宣言である。
#define STACK_SIZE 100 /* スタックに積むことのできるデータの最大個数 */ #define SUCCESS 1 /* 成功 */ #define FAILURE 0 /* 失敗 */ typedef int data_t; /* スタックに貯えるデータの型 */ data_t stack_data[STACK_SIZE]; /* スタック本体 */ int stack_num; /* スッタク内のデータ数 */
data_t という新しい名前の型を定義しておく。以後，スタックの要素の型はすべて data_t 型とする。このようにする理由は，要素の型を変更するときに非常に都合が良いからである。
次に，データをプッシュする関数 push を定義する。
int push(data_t push_data)
{
if (stack_num < STACK_SIZE) {
stack_data[stack_num] = push_data;
stack_num ++;
return SUCCESS;
} else {
return FAILURE;
}
}
stack_num は，現在スタックに積まれているデータの個数を保持しているが，それは stack_data[0] から stack_data[stack_num - 1] までにデータが入っていることを意味している。したがって，新しいデータは stack_data[stack_num] に保存することになる。そして保存した後， stack_num の値を1増やす。
次に，データを取り出す（ポップする）関数 pop を作る。
int pop(data_t *pop_data)
{
if (stack_num > 0) {
stack_num --;
*pop_data = stack_data[stack_num];
return SUCCESS;
} else {
return FAILURE;
}
}
さて，以上で，スタックとそれを取り扱うための関数とができた。これらが働くとき，スタック上のデータがどのように変化するかを逐次見るために，スッタク内のデータを表示する関数を作っておく。
void stackPrint()
{
int i;
printf("stack [");
for (i = 0; i < stack_num; i++) {
printf("%3d", stack_data[i]);
}
printf("]\n");
}
次のようなmain関数で，これらを動かしてみよう。
main()
{
int i, p;
stack_num = 0; /* スタックのデータ数を 0 に初期化 */
for (i = 1; i<=5 ; i++) {
push(i); /* 1 から 5 までの数値を push */
printf("push %2d :", i);
stackPrint();
}
for (i = 1; i <= 3; i++) {
pop(&p); /* 3 回だけ pop */
printf("pop %2d :", p);
stackPrint();
}
for (i = 6; i <= 9; i++) {
push(i); /* 6 から 9 までの数値を push */
printf("push %2d :", i);
stackPrint();
}
while (stack_num > 0) {
pop(&p); /* スタックに残っているデータを全て pop */
printf("pop %2d :", p);
stackPrint();
}
}
push 1 :stack [ 1] push 2 :stack [ 1 2] push 3 :stack [ 1 2 3] push 4 :stack [ 1 2 3 4] push 5 :stack [ 1 2 3 4 5] pop 5 :stack [ 1 2 3 4] pop 4 :stack [ 1 2 3] pop 3 :stack [ 1 2] push 6 :stack [ 1 2 6] push 7 :stack [ 1 2 6 7] push 8 :stack [ 1 2 6 7 8] push 9 :stack [ 1 2 6 7 8 9] pop 9 :stack [ 1 2 6 7 8] pop 8 :stack [ 1 2 6 7] pop 7 :stack [ 1 2 6] pop 6 :stack [ 1 2] pop 2 :stack [ 1] pop 1 :stack []
プログラムの最初でスタックのデータ数 stack_num を 0 に初期化している。これは絶対に忘れてはならない操作である。
5 個のデータを push した後に 3回 pop すると，残りのデータは 2 個になる。それに引き続いて push した場合には，残りのデータの後ろに保存される。出力結果を良く見て欲しい。
最後に，スタックに残っているデータを全て pop して取り出しているが，ここで，スタックが空になっていないかどうかを， stack_num > 0 によって判断している。 この部分は、pop の返す値が SUCCESS である間続ける、次のような while ループに書き換えることもできる。
while (pop(&p) == SUCCESS) {
printf("pop %2d :", p);
stackPrint();
}
前節で構築したスタックには，問題点がいくつかある。それらを直していこう。
問題点の一つ目は，スタックの本体が stack_num と stack_data という二つの変数からできていることである。これら二つは密接に関連しあい一つのスタックを構成するものであるから，それらをまとめて構造体とすることにする。
#define STACK_SIZE 100 /* スタックデータ数の最大値 */
#define SUCCESS 1 /* 成功 */
#define FAILURE 0 /* 失敗 */
typedef int data_t;
typedef struct {
int num;
data_t data[STACK_SIZE];
} stack_t;
最初の部分は，定数マクロ定義と，データ型の定義である。
最後の４行は，構造体を定義する部分 struct {int num; data_t data[STACK_SIZE];} という構造体型を stack_t という新しい名前の型として定義している。
問題点の二つ目は， push や pop などの関数が，大域変数である stack_num と stack_data に対してのみ働くようになっている点である。これでは，スタックを同時に二つ動かすことができない。また，大域変数はできるだけ用いない方が良いという観点からも，これは修正すべきである。
そこで，スッタクの実体を大域変数としてあらかじめ用意するのではなく，必要なときにスタックを何個でも宣言して使えるようにする。そのためには， push や pop などの関数に引数として対象とするスタックを引き渡す必要がある。また， push や pop はそのスタックの実体に対して操作を施す必要があるので，スタックの値ではなくスタックの実体を指すポインタを引き渡さなければならない。
int push(stack_t *stk, data_t push_data)
{
if (stk->num < STACK_SIZE) {
stk->data[stk->num] = push_data;
stk->num ++;
return SUCCESS;
} else {
return FAILURE;
}
}
引数 stk は stack 型の変数を指すポインタである。stk が指す場所にある stack 型構造体のメンバ，たとえば num を参照するには， stk->num とすればよい。これは (*stk).num と同等であるが，stk->num の方が書くのも楽だし，見た目も良い。
pop, stackPrint 等の関数も定義しなおす。
int pop(stack_t *stk, data_t *pop_data)
{
if (stk->num > 0) {
stk->num --;
*pop_data = stk->data[stk->num];
return SUCCESS;
} else {
return FAILURE;
}
}
void stackPrint(stack_t *stk)
{
int i;
printf("stack [");
for (i = 0; i < stk->num; i++) {
printf("%3d", stk->data[i]);
}
printf("]\n");
}
これらの関数の使用例をあげておく。
main()
{
stack_t stk;
int i, p;
stk.num = 0; /* スタックのデータ数を 0 に初期化 */
for (i = 1; i <=4 ; i++) {
push(&stk, i); /* 1 から 4 までの数値を push */
printf("push %2d :", i);
stackPrint(&stk);
}
while (stk.num > 0) {
pop(&stk, &p); /* スタックに残っているデータを全て pop */
printf("pop %2d :", p);
stackPrint(&stk);
}
}
push や pop 等の関数にスタックを引き渡すときには， &stk として，stk を指すポインタを渡していることに注意しよう。
push 1 :stack [ 1] push 2 :stack [ 1 2] push 3 :stack [ 1 2 3] push 4 :stack [ 1 2 3 4] pop 4 :stack [ 1 2 3] pop 3 :stack [ 1 2] pop 2 :stack [ 1] pop 1 :stack []
このプログラムの最後で、スタックが空になるまでポップする部分は、 次のように書き換えることもできる。
while(pop(&stk, &d) == SUCCESS) {
printf("pop %d :", d);
stackPrint(&stk);
}
スタックの実用例
スタックが実際に使われているものの一つに，Ｃ言語における，関数呼び出しの管理がある。ローカル変数（引数を含めて）を持つ関数が呼び出される度に，それらのローカル変数の実体が，その名の通りスタックと呼ばれるメモリ領域に確保され
(push)，その関数が終了した時点，それらのローカル変数は消滅 (pop) する。
関数 f の中で関数 g が呼び出されたとき，スタック上では， f のローカル変数たちの上に g
のローカル変数たちが乗る。よって，消去される順番としては f のものたちよりも g の方が先になるが，関数 g が終了しない限り，関数 f
が終了することはないから，これで整合性がとれている。