Ngăn xếp trong C

I. Lý thuyết :

1. Định nghĩa :

Ngăn xếp ( stack )là một kiểu danh sách tuyến đặc biệt mà phép bổ sung hoặc loại bỏ phần tử luôn thực hiện tại một đầu, gọi là đỉnh( top ). Stack thuộc và loại danh sách hoạt động dựa trên nguyên tắc LIFO (Last- in- First- Out)

2. Cách khai báo :

Khai báo stack :

typedef struct

{

int top;

int nodes[MAX];

} stack;

Kiểm tra stack rỗng :

int Empty(stack *ps)

{

if (ps ->top == -1)

return(TRUE);

return(FALSE);

}

Kiểm tra stack đầy:

int Full(stack *s)

{

if(s->top == MAX-1) return 1;

else return 0;

}

Thêm phần tử vào đỉnh stack:

void Push (stack *ps, int x)

{

if ( ps ->top == -1) {

printf(“\n stack full”);

return;

}

ps -> top = ps ->top + 1;

ps -> nodes[ps->top] = x;

}

Lấy phần từ đỉnh stack :

int Pop( stack *s)

{

if(Empty(s)){

printf("\n Stack rong");

return NULL;

}

return(s->info[s->top--]);

}

3. Ví dụ minh họa :

Viết chương trình chuyển đổi số thập phân sang nhị phân .

C1 : Cách viết không dùng stack :

#include<stdio.h>
#include<conio.h>
#define MAX 255
int main()
{
int x,i=16,matna=0x8000,j=0;//thêm biến j để chặn
printf("Nhap so: ");
scanf_s("%d",&x);
printf("\nKet qua:");
for(;i;--i)
{
if(x&matna)
{printf("1");j=1;}
else if(j)printf("0");
matna>>=1;
}
_getch();
return 0;
}

C2: Cách viết dùng stack :

// stack_chuyen_doi_co_so.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define MAX 255
void push(int *s, int *top, int x)
{
if (*top == MAX)
{
printf("\n Stack day");
_getch();
exit(0);
}
s[++(*top)] = x;
}
int pop(int *s, int *top)
{
if (*top == 0)
{
printf("\n Stack rong");
_getch();
exit(0);
}
return(s[(*top)--]);
}
int main()
{
int x, s[MAX], top = 0;
printf("\n Nhap so thap phan : ");
scanf_s("%d", &x);
do
push(s, &top, x % 2);
while (x /= 2);
printf("\n So nhi phan sao khi chuyen doi :");
for (; top;)
printf("%d", pop(s, &top));
_getch();
return 0;
}