Lập trình C: Bài 15 – Cài đặt ngăn xếp (Stack)
Ngăn xếp (Stack) là một danh sách có thứ tự mà phép chèn và xóa được thực hiện tại đầu cuối của danh sách và người ta gọi đầu cuối này là đỉnh (top) của stack
Trong bài này chúng ta tìm hiểu cách cài đặt Stack trên mảng và trên con trỏ
Nội dung
1. Stack cài đặt trên mảng
#define Max 100 //so phan tu toi da cua Stack
typedef int item; //kieu du lieu cua Stack
struct Stack
{
int Top; //Dinh Top
item Data[Max]; //Mang cac phan tu
};
1.1 Khởi tạo danh sách rỗng, kiểm tra danh sách rỗng, đầy
void Init (Stack &S) //khoi tao Stack rong
{
S.Top = 0; //Stack rong khi Top la 0
}
int Isempty(Stack S) //kiem tra Stack rong
{
return (S.Top == 0);
}
int Isfull(Stack S) //kiem tra Stack day
{
return (S.Top == Max); //
}
1.2 Thêm phần tử vào Stack (Push)
Để chèn thêm phần tử vào Stack ta chèn vào vị trí Top, và tang Top lên 1 đơn vị
void Push(Stack &S, item x) //them phan tu vao Stack
{
if (!Isfull(S))
{
S.Data[S.Top] = x; //Gan du lieu
S.Top ++; //Tang Top len 1
}
}
1.3 Lấy dữ liệu tại Top nhưng không xóa (Peak)
int Peak(Stack S) //Lay phan tu o dau Stack nhung khong xoa
{
return S.Data[S.Top-1]; //Lay du lieu tai Top
}
1.4 Xóa và lấy dữ liệu tại Top (Pop)
int Pop(Stack &S) //Loai bo phan tu khoi Stack
{
if (!Isempty(S))
{
S.Top --; //Giam Top
return S.Data[S.Top]; //Lay du lieu tai Top
}
}
1.5 Code toàn bộ chương trình (full)
#include <stdlib.h>
#include <stdio.h>
#define Max 100 //so phan tu toi da cua Stack
typedef int item; //kieu du lieu cua Stack
struct Stack
{
int Top; //Dinh Top
item Data[Max]; //Mang cac phan tu
};
void Init (Stack &S); //khoi tao Stack rong
int Isempty(Stack S); //kiem tra Stack rong
int Isfull(Stack S); //kiem tra Stack day
void Push(Stack &S, item x); //them phan tu vao Stack
int Peak(Stack S); //Lay phan tu o dau Stack nhung khong xoa
int Pop(Stack &S); //Loai bo phan tu khoi Stack
void Input (Stack &S); //Nhap Stack
void Output(Stack S); //Xuat Stack
void Init (Stack &S) //khoi tao Stack rong
{
S.Top = 0; //Stack rong khi Top la 0
}
int Isempty(Stack S) //kiem tra Stack rong
{
return (S.Top == 0);
}
int Isfull(Stack S) //kiem tra Stack day
{
return (S.Top == Max); //
}
void Push(Stack &S, item x) //them phan tu vao Stack
{
if (!Isfull(S))
{
S.Data[S.Top] = x; //Gan du lieu
S.Top ++; //Tang Top len 1
}
}
int Peak(Stack S) //Lay phan tu o dau Stack nhung khong xoa
{
return S.Data[S.Top-1]; //Lay du lieu tai Top
}
int Pop(Stack &S) //Loai bo phan tu khoi Stack
{
if (!Isempty(S))
{
S.Top --; //Giam Top
return S.Data[S.Top]; //Lay du lieu tai Top
}
}
void Input (Stack &S)
{
int n;
item x;
do
{
printf("Nhap so phan tu cua Stack (<%d) :",Max);
scanf("%d",&n);
} while (n>Max || n<1);
for (int i=0; i<n; i++)
{
printf("Nhap phan tu thu %d : ", i+1);
scanf("%d",&x);
Push(S,x);
}
}
void Output(Stack S)
{
for (int i=S.Top-1; i>=0; i--)
printf("%d ",S.Data[i]);
printf("\n");
}
int main()
{
Stack S;
Init(S);
Input(S);
Output(S);
int lua_chon;
printf("Moi ban chon phep toan voi DS LKD:");
printf("\n1: Kiem tra Stack rong");
printf("\n2: Kiem tra Stack day");
printf("\n3: Them phan tu vao Stack");
printf("\n4: Xoa phan tu trong Stack");
printf("\n5: Xuat Stack");
printf("\n6: Thoat");
do
{
printf("\nBan chon: ");
scanf("%d",&lua_chon);
switch (lua_chon)
{
case 1:
{
if (Isempty(S)) printf("Stack rong !");
else printf ("Stack khong rong !");
break;
}
case 2:
{
if (Isfull(S)) printf("Stack day !");
else printf ("Stack chua day !");
break;
}
case 3:
{
item x;
printf ("Nhap phan tu can chen vao DS: ");
scanf("%d",&x);
Push(S,x);
break;
}
case 4:
{
Pop(S);
break;
}
case 5:
{
Output(S);
break;
}
case 6: break;
}
}while (lua_chon !=6);
return 0;
}
2. Stack cài đặt trên con trỏ
Stack trên con trỏ vẫn là stack bình thường nhưng link hoạt hơn vì nó dùng con trỏ để cấp phát và quản lý, không bị thừa hoặc thiếu gì cả.
2.1 Xây dựng cấu trúc
typedef int item; //kieu du lieu
struct Node
{
item Data; //du lieu
Node *Next; //link
};
typedef struct Stack
{
Node *Top;
};
2.2 Khởi tạo danh sách rỗng, kiểm tra danh sách rỗng, độ dài danh sách
void Init (Stack &S) //khoi tao Stack rong
{
S.Top = NULL;
}
int Isempty(Stack S) //kiem tra Stack rong
{
return (S.Top == NULL);
}
int Len (Stack S)
{
Node *P = S.Top;
int i=0;
while (P != NULL) //trong khi chua het Stack thi van duyet
{
i++;
P = P->Next;
}
return i;
}
2.3 Tạo 1 Node
Node *MakeNode(item x) //tao 1 Node
{
Node *P = (Node*) malloc(sizeof(Node));
P->Next = NULL;
P->Data = x;
return P;
}
2.4 Chèn phần tử vào Stack (Push)
Để chèn phần tử vào Stack thì chỉ cần cho con trỏ Note đó trỏ và Top, rồi Top trỏ lại nó là xong
void Push(Stack &S, item x) //them phan tu vao Stack
{
Node *P = MakeNode(x);
P->Next = S.Top;
S.Top = P;
}
2.5 Lấy dữ liệu tại Top nhưng không xóa (Peak)
int Peak(Stack S) //Lay phan tu o dau Stack nhung khong xoa
{
return S.Top->Data;
}
2.6 Xóa và lấy dữ liệu tại Top (Pop)
Ta chỉ cần cho con trỏ Top trỏ đến vị trí thứ 2 thôi.
int Pop(Stack &S) //Loai bo phan tu khoi Stack
{
if (!Isempty(S))
{
item x = S.Top->Data; //luu lai gia tri
S.Top = S.Top->Next; //Xoa phan tu Top
return x;
}
}
2.7 Chương trình hoàn chỉnh (full code)
#include <stdlib.h>
#include <stdio.h>
typedef int item; //kieu du lieu
struct Node
{
item Data; //du lieu
Node *Next; //link
};
typedef struct Stack
{
Node *Top;
};
void Init (Stack &S); //khoi tao Stack rong
int Isempty(Stack S); //kiem tra Stack rong
int Len (Stack S); //Do dai Stack
void Push(Stack &S, item x); //them phan tu vao Stack
int Peak(Stack S); //Lay phan tu o dau Stack nhung khong xoa
int Pop(Stack &S); //Loai bo phan tu khoi Stack
void Input (Stack &S); //Nhap Stack
void Output(Stack S); //Xuat Stack
Node *MakeNode(item x); //Tao 1 Node
void Init (Stack &S) //khoi tao Stack rong
{
S.Top = NULL;
}
int Isempty(Stack S) //kiem tra Stack rong
{
return (S.Top == NULL);
}
int Len (Stack S)
{
Node *P = S.Top;
int i=0;
while (P != NULL) //trong khi chua het Stack thi van duyet
{
i++;
P = P->Next;
}
return i;
}
Node *MakeNode(item x) //tao 1 Node
{
Node *P = (Node*) malloc(sizeof(Node));
P->Next = NULL;
P->Data = x;
return P;
}
void Push(Stack &S, item x) //them phan tu vao Stack
{
Node *P = MakeNode(x);
P->Next = S.Top;
S.Top = P;
}
int Peak(Stack S) //Lay phan tu o dau Stack nhung khong xoa
{
return S.Top->Data;
}
int Pop(Stack &S) //Loai bo phan tu khoi Stack
{
if (!Isempty(S))
{
item x = S.Top->Data; //luu lai gia tri
S.Top = S.Top->Next; //Xoa phan tu Top
return x;
}
}
void Input (Stack &S) //nhap danh sach
{
int i=0;
item x;
do
{
i++;
printf ("Nhap phan tu thu %d : ",i);
scanf("%d",&x);
if (x != 0) Push(S,x);
} while(x != 0); //nhap 0 de ket thuc
}
void Output(Stack S)
{
Node *P = S.Top;
while (P != NULL)
{
printf("%d ",P->Data);
P = P->Next;
}
printf("\n");
}
int main()
{
Stack S;
Init(S);
Input(S);
Output(S);
int lua_chon;
printf("Moi ban chon phep toan voi DS LKD:");
printf("\n1: Kiem tra Stack rong");
printf("\n2: Do dai Stack");
printf("\n3: Them phan tu vao Stack");
printf("\n4: Xoa phan tu trong Stack");
printf("\n5: Xuat Stack");
printf("\n6: Thoat");
do
{
printf("\nBan chon: ");
scanf("%d",&lua_chon);
switch (lua_chon)
{
case 1:
{
if (Isempty(S)) printf("Stack rong !");
else printf ("Stack khong rong !");
break;
}
case 2:
{
printf("Do dai Stack: %d",Len(S));
break;
}
case 3:
{
item x;
printf ("Nhap phan tu can chen vao DS: ");
scanf("%d",&x);
Push(S,x);
break;
}
case 4:
{
Pop(S);
break;
}
case 5:
{
Output(S);
break;
}
case 6: break;
}
}while (lua_chon !=6);
return 0;
}
3. Sử dụng Stack có sẵn trong C++
Trong C++ đã xây dựng sẵn các phương thức (hàm) liên quan đến Stack, ta chỉ việc khai báo và sử dụng
#include <iostream> // io
#include <stack> // use stack
using namespace std;
int main() {
stack <int> S; // khai bao Stack voi kieu du lieu la int
for (int i = 0; i < 10; i++) {
S.push(i*78 + 26); // chen cac phan tu vao stack
}
cout << "Do dai stack: " << S.size() << "\n";
// xuat tat ca phan tu trong stack
while (!S.empty()) { // trong khi stack chua trong
int x = S.top(); // lay gia tri top
S.pop(); // loai bo khoi stack
cout << x << " ";
}
cout << "\n";
return 0;
}
4. VÍ dụ về ứng dụng của Stack
Stack có nhiều ứng dụng, sau đây là 1 ứng dụng trong chuyển đổi cơ số. Code sau sẽ chuyển số cơ số 10 sang cơ số x nhập từ bàn phím
#include <iostream> // io
#include <stack> // use stack
using namespace std;
int main() {
char num[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
stack <char> S; // khai bao Stack voi kieu du lieu la int
int coSo, so, du;
cout << "Nhap so can chuyen: ";
cin >> so;
cout << "Nhap co so can chuyen: ";
cin >> coSo;
// chuyen doi bang cach dua vao Stack
while(so) {
du = so % coSo;
S.push(num[du]);
so /= coSo;
}
// Xuat ra
while(!S.empty()) {
cout << S.top();
S.pop();
}
return 0;
}
[rps-include post=”2703″ shortcodes=”false”]
Hello nguyenvanquan7826,
Nhờ bạn giải thích giùm mình là vì sao các hàm như:
void Init (Stack &S)
int Pop(Stack &S)
void Push(Stack &S, item x)
lại dùng toán tử lấy địa chỉ “&”.
Còn các hàm như:
int Isempty(Stack S)
int Isfull(Stack S)
int Peak(Stack S)
thì không dùng toán tử “&”
Thank you.
Toán tử & nói một cách đơn giản là để khi thoát khỏi hàm thì biến đó có thể thay đổi. Nếu trong hàm ko làm thay đổi biên đó thì không cần.
mình hơi thắc mắc, tại sao lại phải dùng
—–
typedef int item;
struct Stack
{
int Top;
item Data[Max];
};
—–
sao không dùng:
—–
struct Stack
{
int Top;
intData[Max];
};
—–
typedef có tác dụng gì vậy?
Nó dùng để định nghĩa một kiểu dữ liệu. mình dùng item để cho dễ. Ví dụ giờ bạn muốn kiểu dữ liệu của bạn là int, nhưng vài hôm lại muốn chuyển sang float, hoặc 1 struct, khi đó sửa sẽ rất nhiều, định nghĩa thế này thì mình chỉ cần sửa ở đây thôi.
Tốt hơn nữa thì nên xây dựng thêm hàm nhập và xuất item, như thế dù sửa kiểu dữ liệu thế nào thì ko liên quan nữa, chỉ cần sửa nhập xuất nữa là xong.
a Quân cho e hỏi tí.cái chỗ hàm lấy dữ liệu nhưng k xóa ấy thì mình lấy dữ liệu tại đỉnh top thì phải là return(S.data[S.top]) tại sao lại lại return(S.data[S.top-1]) .Anh giải thích cho e hiểu với được không ạ?
thì nó là mảng. các phần từ là từ 0->n-1 mà bạn. Do đó cái đầu tiên trong Stack (tức cái cuối cùng trong mảng) là [top-1]
a giúp e câu này nữa nhé: giá trị của các phần tử chèn vào không phụ thuộc vào giá trị của i.vậy mục đích của dùng các vòng for này là để làm gi hả a?a giải thích giúp e với .e không hiểu 🙁
for (int i = 0; i < 10; i++) {
S.push(i*78 + 26); // chen cac phan tu vao stack
}
Thì tức là các giá trị cho vào là ngẫu nhiên đó bạn.
a Quân cho e hỏi.ví dụ e có 1 ds : 2 3 4 5 6 7 8
e bỏ phần tử thứ 3 đi.thì e in ra ds con lại nó lại là: 2 3 20 5 6 7 8
tại sao nó lại thay phần tử thứ 3 bang giá trị khác ạ.cách khac phục như thế nào a???
Vậy là em code sai thôi.
đâu là hàm xóa phần tử thứ n của e.a xem giúp e với ạ:
void pop_n(stack* s,int n)
{
int dem=1;
stackNode *p=s->top;
stackNode *temp;
int m;
if(n>len(s))
{
return;
}
else
{
while(demtop=s->top->next;
free(p);
return;
}
if(dem==n)
{
temp=p->next;
free(p);
return;
}
temp=p;
p=p->next;
dem++;
}
}
return;
}
Mình không rõ cái demtop của bạn là gì?
Bạn nào có Code viết theo chuẩn C về stack này cho mình tham khảo học theo được ko ạ.
Bài viết của bạn Nguyễn Văn Quân lưu đuôi .cpp thi dc , chứ đuôi .C thi ko chạy dc 🙁 . Mình đang muốn học theo chuẩn C. hix
a cho e hỏi s.top và s->top có gì khác nhau ạ???
s.top là dùng khi s là 1 struct bình thường
s->top là dùng khi s là con trỏ cấu trúc.
bạn ơi ctrinh đổi cơ số sao mình k chạy đc nhờ,có code viết bằng c k cho mình vs
Nếu bạn dùng code bên trên thì hãy lưu file là *.cpp
Còn code bằng C mình không có. 🙂 Bạn dựa vào stack đã xây dựng để code cũng được mà.
Thầy ơi, ngăn xếp lưu trữ trong danh sách liên kết kép trong C thì như thế nào ạ?
Cái này mình chưa làm bào giờ, cũng chưa thấy ai làm Ngăn xếp bằng ds liên kết kép cả. Bạn có thể tìm bài danh sách liên kết kép để xem thêm nhé. https://www.cachhoc.net/2014/12/21/lap-trinh-c-bai-14-danh-sach-lien-ket-kep/
sao chỗ lấy giá trị tại vị trí top :
int Peak(Stack S) //Lay phan tu o dau Stack nhung khong xoa
{
return S.Data[S.Top-1]; //Lay du lieu tai Top
}
int Pop(Stack &S) //Loai bo phan tu khoi Stack
{
if (!Isempty(S))
{
S.Top –; //Giam Top
return S.Data[S.Top]; //Lay du lieu tai Top
}
}
sao lúc là s.data[s.top] lúc thì lại là s.data[s.top-1]
Vì trong TH thứ 2 ta đã Top– đi rồi bạn
sao mình làm tương tự demo nhưng kết quả ra sai ý nhỉ. lúc nào kiểm tra thì stack cũng “rỗng” và “không đầy”.
mặc dù mình cho max =3 nhập vào 3 thì phải đầy chứ. bạn admin có cho code chạy test thử từng phần chưa vậy. bạn xem lãi hộ mình nhe ;v
Bạn cố gắng kiểm tra lại từng bước xem nhé. Có thể lỗi ở phần nào đó. Code của mình chạy ổn rồi bạn có thể test thử code 🙂
Chào bạn. Bạn ơi bạn có thể thêm hàm Peek. Tức là viết chương trình con lấy nội dung của phần tử tại đỉnh của Stack được không ạ?
Mình có thấy bạn có viết hàm Peak nhưng sao chưa thấy sử dụng nó vậy bạn nhỉ?
Viết ra là 1 chuyện, trong bài toàn có cần dùng không là chuyện khác. Mình cứ viết ra cho đủ để các bạn dùng thôi.
Mình có rồi đó bạn.
Mình có ý kiến về code.
1/cái struct Stack{…. không cần typedef đâu
2/hàm peak cũng cần phải kiểm tra stack có rỗng hay không chứ
3/hàm pop lỡ stack rỗng thì nó trả về cái gì, bạn chưa cover qua trường hợp này
Cảm ơn bạn đã góp ý.
Nếu không có typedef thì mọi nơi bạn đều phải viết “struct Stack” còn khi đã dùng typedef (định nghĩa 1 kiểu dữ liệu) thì không cần lôi cái struct đi theo
– 2 hàm peak và pop thì đúng như bạn nói. Mình sẽ chỉnh sửa lại.
typedef struct Stack
{
Node *Top;
};
anh cho em hỏi cái này là khai báo cái gì ạ
khai bao struct thoi ban, struc nay co 1 con tro Top kie Note.
anh cho em hỏi tại sao khi khai báo hàm này Init (Stack &S) lại khai báo stack &S còn khi khai báo hàm Isempty(Stack S) lại khai báo stack S ạ
Khi có & thì ra khỏi hàm S sẽ giữ nguyên giá trị sau khi thay đổi. Còn ko có & thì trước và sau hàm giá trị của nó ko đổi
#12h20m 10/6/2016
Hôm nay đi thi về, gặp Stack
làm đc…. nhưng bị lỗi là output. output viết như trên ko đúng bản chất của stack…
Thầy bắt output thì dùng hàm pop(), ko phải duyệt trên xuống.
Duyệt thế thì viết Display().
Mong anh xem lại để sửa code cho các bạn sau này.
muốn xóa 1 dữ liệu BẤT KÌ trong Stack thì code ntn ạ??
Bạn xem ở đây nhé
https://www.google.com.vn/search?q=delete+item+from+stack&oq=delete+item+stack&aqs=chrome.1.69i57j0.8935j0j4&client=ms-android-samsung&sourceid=chrome-mobile&ie=UTF-8#xxri=0
Anh Quân cho em hỏi tại sao khi làm danh sách liên kết đơn thì anh có đoạn
typedef Node *List; //List la mot danh sach cac Node
Còn ở phần stack thì không có, mặc dù theo bản chất stack cũng mà một loại danh sách liên kết
Nó chính là ở đoạn này nhé
typedef struct Stack
{
Node *Top;
};
ở phần stack cài đặt trên con trỏ, trong hàm pop e nghĩ anh nên xóa đi node top của stack nữa vì khi cấp phát con trỏ trên vùng nhớ heap như thế thì vùng nhớ của con trỏ đó vẫn sẽ tồn tại đến suốt chương trình, nếu ko xóa node đó đi thì khi ứng dụng stack rất dễ bị stack overflow
a ơi cho e hỏi e dùng code::block . mà sao e chạy chương trình = c lại ko sử dụng được tham chiếu vậy ạ. ecasm ơn
Chưa hiểu lắm, bạn hỏi thế chung chung quá.
Trong C không có tham chiếu đâu b, code::block không chạy được là đúng rồi, DevC chạy được là do trình biên dịch C++ bla bla.. (đoạn này m kb giải thích thế nào)
Cho e hỏi là ngăn xếp tạo bằng con trỏ rất giống với danh sách liên kết đơn tạo bằng con trỏ phải không ạ
cho em hỏi hàm isfull isempty đều là int nhưng return lại là 1 mệnh đề thì kết quả trả về là như thế nào ạ?
mệnh đề đó có giá trị là 1 hoặc 0 bạn nhé. VD L == NULL thì sẽ có giá trị 1 nếu đúng, 0 nếu sai.
ad cho e hỏi:
push(): để thêm dl
peek(): lấy dl ra và ko xóa
pop(): xóa và lấy dl
“lấy dl ra và ko xóa” thì e thấy hợp lý để phục vụ cho pop() sau này. Vậy ở pop() có”xóa” rồi là xong, còn “lấy dl” để làm gì nữa thế ạ?
anh ơi viết thêm hàm thêm xóa vào vị trí k đi anh
Stack ko có cái đó nhé. Bạn tự tư duy để làm nếu cần.
viết hàm Input_stack bằng ds đặc. làm sao vậ thầy